二叉树的后序序列 题解：
- #include<bits/stdc++.h>
- using namespace std;
- typedef struct node{
- char data;
- struct node *lchild, *rchild;
- }*BitTree;
- string in_str, pre_str;
- // 构建二叉树的递归函数
- // pre_l, pre_r: 当前子树在先序序列中的起始和结束下标
- // in_l, in_r: 当前子树在中序序列中的起始和结束下标
- BitTree build(int pre_l, int pre_r, int in_l, int in_r){
- if(pre_l > pre_r) return NULL;
- BitTree root = new node();
- root->data = pre_str[pre_l];//先序的第一个是根
- //找到根节点的位置
- int k;
- for(k = in_l; k <= in_r; k++){
- if(in_str[k] == root -> data) break;
- }
- int numLeft = k - in_l;
- root -> lchild = build(pre_l + 1, pre_l + numLeft, in_l, k - 1);
- root -> rchild = build(pre_l + numLeft + 1, pre_r, k + 1, in_r);
- return root;
- }
- void postOrder(BitTree T){
- if(T == NULL) return;
- postOrder(T -> lchild);
- postOrder(T -> rchild);
- cout << T -> data;
- }
- int main(){
- cin >> in_str >> pre_str...
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发