根据二叉树的前序和中序遍历获取链表的后序遍历

例：树A

前序遍历：根-左-右，就是遍历树的时候，先遍历根节点然后再遍历左子节点最后遍历根节点的右子节点。（树A的前序A-B-C-D-E-F）

中序遍历：左-根-右，就是遍历树的时候，先遍历左子节点，然后再遍历其根节点，最后在遍历树的右子节点。（树A的中序C-B-A-E-D-F）

后序遍历：左-右-根，就是遍历树的时候，先遍历左子节点，然后再遍历其右子节点，最后在遍历这棵树的根节点。(树A的后序C-B-E-F-D-A)

注：前序，中序，后序是相对于根节点来说的（根在前，根在中间，根在后），其中左右子节点的顺序不会变。

下面回到正题，如何通过一个二叉树的前序和中序遍历推算出二叉树的后序遍历

前序：A-B-C-D-E-F

中序：C-B-A-E-D-F

首先，前序遍历的第一个元素一定是整棵树的根节点，而在中序遍历中，输出在根节点前面的，一定是根节点的左子树所包含的节点，输出在根节点后面的一定是根节点右子树所包含的节点。

可以得出：

根节点：A

左子树节点：C,B 右子树节点：E,D,F

分别把左子树和右子树看做一颗树按照上面的方法查找其根节点和其左子树和右子树，循环这个过程，直到树中只有一个根节点。

按照上面的分析流程可以得到：

第一次：

根节点：A 左子树节点：C,B 右子树节点：E,D,F

根据二叉树的前序和中序遍历获取链表的后序遍历

第二次：

把C，B看成一棵树，发现前序遍历中是B是先出现的，所以B是根节点，而在中序遍历中C出现在B的前面，所以C是B的左子节点。

在E,D,F树中，D是根节点，E是D的左节点，F是D的右节点。

根据二叉树的前序和中序遍历获取链表的后序遍历

所以整颗二叉树就是树A的样子。根据树那么后序遍历相信自己也可以得出了。

//下面是实现这个功能的代码：
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
struct TreeNode
{
    struct TreeNode *left;
    struct TreeNode *right;
    char elem;
};
TreeNode * BinaryTreeFromOrderings(char *pre,char *mid,int length)
{
    if(length<=0)
    {
        return NULL;
    }
    TreeNode *A=new TreeNode();
    A->elem=*pre;//找到根节点
    int n=0;
    while(n<=length&&mid[n]!=A->elem)//找到根节点在中序遍历中的位置，依次来区分左子树节点和右子树节点
    {
        n++;
    }
    A->left=BinaryTreeFromOrderings(pre+1,mid,n);
    A->right=BinaryTreeFromOrderings(pre+n+1,mid+n+1,length-n-1);
    cout<<A->elem<<endl;//因为是后序遍历，所以最后打印出本节点元素
    return A;
}
int main()
{
    char pre[]="GDAFEMHZ";
    char mid[]="ADEFGHMZ";
    struct TreeNode *root=BinaryTreeFromOrderings(pre,mid,8);
    cout<<endl;
}
//最后main函数得到的root节点就是整颗二叉树的根节点，如果用linux，QT执行你在调试过程中能通过root看到整棵树的情况。

根据二叉树的前序和中序遍历获取链表的后序遍历

相关推荐