首页 > 程序开发 > 软件开发 > 其他 >

通过前序遍历和中序遍历得到后续遍历

2017-02-18

通过前序遍历和中序遍历得到后续遍历:思想很简单,前序遍历,第一个节点一定是当前树的根节点,而这个节点在中序遍历中,分割了左右子树。

通过前序遍历和中序遍历得到后续遍历:思想很简单,前序遍历,第一个节点一定是当前树的根节点,而这个节点在中序遍历中,分割了左右子树。

假如前序:

root left1 left2 left3 right1 right2

中序一定是:

left left left root right right

虽然left在中序的顺序不能直接通过前序得到,但是一定知道的是,在中序遍历中,root分割了左右子树。然后递归得到左右子树的遍历,就可以得到整个树了。

代码如下:

#include 
#include 
#include 
using namespace std;

string res;

void postOrder(string preorder, string midorder, int sp, int se, int ms, int me){
    if(sp > se || ms > me) return;
    res = preorder[sp] + res;
    int mid = ms;
    for(mid = ms; mid <= me; mid++){
        if(midorder[mid] == preorder[sp]) break;
    }
    postOrder(preorder, midorder, mid-ms+sp+1, se, mid+1, me);//这里是先右孩子
    postOrder(preorder, midorder, sp+1, mid-ms+sp, ms, mid-1); //然后左孩子
}

int main(){
    string str1, str2;
    while(cin>>str1>>str2){
        postOrder(str1, str2, 0, (int)str1.length()-1, 0, (int)str2.length()-1);
        cout<

上面是返回后续遍历的序列的,假如想重构这棵树,思想就是:

consTree(preSe, midSe, ps, pe, ms, me){
    node = new node(preSe[ps]); //构造当前节点
    node->left = consTree(preSe,midSe, ps+1, mid-ms+ps, ms, mid-1);//节点做孩子等于左子树的根节点
    node->right = consTree(mid-ms+ps+1, pe, mid+1, me);//同理
    return node;
}

完整代码如下:


struct TreeNode{
    int val;
    TreeNode * left, *right;
    TreeNode(int x): val(x), left(NULL), right(NULL){}
};

TreeNode* constTree(string preorder, string midorder, int sp, int se, int ms, int me){
    if (sp > se || ms > me) {
        return NULL;
    }
    TreeNode * node = new TreeNode(preorder[sp]);
    int mid = ms;
    for(mid = ms; mid <= me; mid++){
        if(midorder[mid] == preorder[sp]) break;
    }
    node->left = constTree(preorder, midorder, sp+1, mid-ms+sp, ms, mid-1);
    node->right = constTree(preorder, midorder, mid-ms+sp+1, se, mid+1, me);
    return node;
}

同理其实可以得到通过后续遍历和中序遍历得到前序遍历的。但是不能通过前序遍历和后续遍历得到中序遍历,会有歧义的。

相关文章
热点推荐