二叉树 三种递归遍历、已知前序中序rebulidBinaryTree

 

# include<iostream>
# include<string>
# include<vector>
# include<algorithm>
# include<cmath>
# include<cstdio>
# include<map>
# include<stack>
using namespace std;

//Binary Tree Node
typedef struct BTNode {
    char data;
    struct BTNode* pLeftChild;
    struct BTNode* pRightChild;
} BTNode, * PBTNode;

void visit(PBTNode pT) {
    cout << (*pT).data << " ";
}




void preOrder(PBTNode pT) {
    if (pT == NULL) {
        return ;
    }
    visit(pT);
    preOrder(pT->pLeftChild);
    preOrder(pT->pRightChild);
}

void inOrder(PBTNode pT) {
    if (pT == NULL) {
        return ;
    }
    inOrder(pT->pLeftChild);
    visit(pT);
    inOrder(pT->pRightChild);
}

void postOrder(PBTNode pT) {
    if (pT == NULL) {
        return ;
    }
    postOrder(pT->pLeftChild);
    postOrder(pT->pRightChild);
    visit(pT);
}




PBTNode rebulidBinaryTree(string pre, string in, int s1, int e1, int s2, int e2) {
    if (s1 > e1) {
        return NULL;
    }
// pre: 根 左 右
// in: 左 根 右
// post: 左 右 根

    PBTNode pT = (PBTNode)malloc(sizeof(BTNode));
    pT -> pLeftChild = NULL;
    pT -> pRightChild = NULL;
    pT -> data = pre[s1];

    int mid;
    for (int i = s2; i <= e2; i++) {
        if (in[i] == pre[s1]) {
            mid = i;
            break;
        }
    }

    int k1 = mid - s2;
    int k2 = e2 - mid;

    pT -> pLeftChild = rebulidBinaryTree(pre, in, s1 + 1, s1 + k1, s2, mid - 1);
    pT -> pRightChild = rebulidBinaryTree(pre, in, s1 + k1 + 1, e1, mid + 1, e2);

    return pT;
}

int main() {

    string pre, in, post;
    cin >> pre;
    cin >> in;
    PBTNode pT = rebulidBinaryTree(pre, in, 0, pre.size() - 1, 0, in.size() - 1);
    postOrder(pT);
}