如何从后序遍历求原二叉树？

~

1、先求原始二叉树，后序遍历中最后出现的是根，所以A是整棵树的根，在结合中序遍历来看

BDCE是A的左子树，而FHG是A的右子树；

2、BDCE序列中B是整个序列根，因为后序遍历中B最后出现。此时再看中序中根B左端没有左子

树，右端有DCE,所以DCE是B的右子树 ；

3、再看D、C、E在后序遍历中C结点最后出现，所以C是根，此时再到中序遍历看可以看到C的左

端是D，右端是E，所以C的左子树是D，右子树是E；

4、再看F、H、G三个结点，后序遍历序列F最后出现，所以F是根结点，再回去看中序HG在F右

端，所以HG是F的右子树；

5、由于H、G在后序遍历序列G最后出现，所以G是H, G中的根，再看 中序中G左端只有一个H，

所以H是G的左子树，得到最终原始二叉树。

需要注意的几点：

1、根是相对的，对于整棵树而言只有一个根，但对于每棵子树而言，又有自己的根。

2、前序遍历时，一棵树的根永远在左子树前面，左子树又永远在右子树前面。

3、二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序一样。

---

甘南县19851379490： 求二叉树的后序遍历 - ？
务侄创灼： 因为二叉树前序遍历为:ABCDEFGHI,所以这棵树的根结点为A; 又因为中序遍历为:BCAEDGHFI,所以这棵树的左子树为BC,右子树为EDGHFI; 现在先看左子树中序遍历:BC,由前序遍历ABCDEFGHI,所以B为左子树的根结点; 现看右子树中序遍历:EDGHFI,由前序遍历DEFGHI,得D为右子树的根结点; 依些递推就可以将各个子树化出来,结果为:CBEHGIFDA

甘南县19851379490： 二叉树的前、中、后三种遍历的解答方法? - ？
务侄创灼： 二叉树的遍历: (1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树; (2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树; (3)后序遍历(LRD)首先遍历左子树,然后访问遍历右子树,最后访问根结点.

甘南县19851379490： c语言后序遍历二叉树 - ？
务侄创灼： /*=========================================================*//* 二叉树的中序(前序,后序)遍历 *//*========================================================*/# include <stdio.h># include <malloc.h> struct tree { int ...

甘南县19851379490： 已知二叉树的后序序列怎么求二叉树 - ？
务侄创灼： 1、确定树的根.树根是当前树中所有元素在后序遍历中最后出现的元素.2、求解树的子树.找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树.若根节点左边或右边为空,则该方向子树为空;若根...

甘南县19851379490： 怎么根据先序遍历,后序遍历结果画出二叉树 - ？
务侄创灼： ,这个问题我以前回答过了 凑合着看吧 很显然你还不懂的遍历一棵二叉树的原理 当你拿到一棵二叉树,无论它的形状如何的千奇百怪 我们都可以将它按照如下的方式划分 根 / \ 左子树 右子树 一棵有很多个节点的二叉树可以划分为以上的形式 ...

甘南县19851379490： 怎样根据先序和后序遍历确定二叉树 - ？
务侄创灼： #include <stdio.h>#define N 100typedef struct node{ char data;struct node *lchild,*rchild;}BTNode; /*---二叉树的建立---*/BTNode *createbintree(){BTNode *t;char x;scanf(＂%c＂,&x);if (x=='#') t=NULL;else{t=(BTNode *)malloc(...

甘南县19851379490： 求二叉树如何前序、中序、后序遍历？
务侄创灼： 先、中、后都是针对父节点何时被遍历来说的. 先序就是先遍历父节点,再遍历左子节点,再遍历右子节点. 中序先遍历左子节点,第二个遍历父节点,再遍历右子节点. 后序先遍历左子节点,再遍历右子节点,最后遍历根节点. 还不懂的话可以下一个这个: http://download.csdn.net/source/287152

甘南县19851379490： 写出按后序遍历对称序线索二叉树的算法 - ？
务侄创灼： 无需建立二叉树:获取当前前序序列的第一个元素并输出(按层次遍历) 从对应的中序序列中找到该元素,该元素此时将二分中序序列中的元素 依据划分出的两个序列,在前序序列中找到这两个序列(按照中序中序列的元素个数即可划分) 对...

甘南县19851379490： 后序遍历二叉树 - ？
务侄创灼： #include typedef struct BiTNode{//二叉树结构体 char item; struct BiTNode * lchild,*rchild; }BiTNode,*BiTree; typedef struct Stack{//链栈栈的存储结构体 BiTree data; struct Stack *next; }Stack,*st; BiTree CreateTree() {BiTree T; char ch; ch=getchar(); ...

甘南县19851379490： 求c#前中后序遍历二叉树的算法及思想 - ？
务侄创灼： 下面简单介绍一下几种算法和思路: 先序遍历: 1. 访问根结点 2. 按先序遍历左子树; 3. 按先序遍历右子树; 4. 例如:遍历已知二叉树结果为:A->B->D->G->H->C->E->F 中序遍历: 1. 按中序遍历左子树; 2. 访问根结点; 3. 按中序遍历右子...