[阿里巴巴2015研发工程师B] 二叉树已知前序中序遍历，求后序
已知一个二叉树的前序遍历结果是（ACDEFHGB） ，中序遍历结果是（DECAHFBG）,请问后续遍历结果是 __
A.HGFEDCBAB.EDCHBGFAC.BGFHEDCAD.EDCBGHFAE.BEGHDFCAF.BGHFEDCA
感谢您为本话题评分。
共有3个回答
先补充点基础知识吧。
前序遍历（DLR）是二叉树遍历的一种，也叫做先根遍历、先序遍历。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
比如以下二叉树：
它的前序遍历结果为：ABDECF
而后序遍历首先遍历左子树，然后遍历右子树，最后遍历访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。
还是上面的二叉树，它的后序遍历结果：DEBFCA
而中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。
中序遍历结果：DBEAFC。
基础补完之后，我们来讲解解题步骤：前序遍历：ACDEFHGB中序遍历：DECAHFBG
第一步，根据前序遍历的特点，我们知道根结点为A。
第二步，观察中序遍历DECAHFBG，可知，其中root节点A左侧的DEC必然是root的左子树，A右侧的HFBG必然是root的右子树。
第三步，观察左子树DEC，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为C（前序的CDE的首字母）。
然后DE为C的右子树。
同样的道理，root的右子树节点HFBG中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。
FHGB中，F为首字母，所以必定是右子树的根节点。
观察中序里的HFBG，H为F的左子树，BG为右子树。
观察前序里的GB，G在前面，所以G为节点，B的树。
至此，整棵树已分析完毕。
& & & & & &A& & & &C & & & & F& & D & & & & &H & & &G&E & & & & & & & & & & & &B
具体图就不画了，大概就像上面一样。所以后序遍历为：EDC H BG FA
所以这道题 选B
如果你认为此话题有广告、灌水的嫌疑，请给此话题评一颗星。平均分低的话题将不会再显示。
良好的讨论氛围由大家共同维护。这种题一般有二种形式，共同点是都已知中序序列。如果没有中序序列，是无法唯一确定一棵树的。
一、已知二叉树的前序序列和中序序列，求解树。
<span style="color:#、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。
<span style="color:#、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。
<span style="color:#、递归求解树。将左子树和右子树分别看成一棵二叉树，重复<span style="color:#、<span style="color:#、<span style="color:#步，直到所有的节点完成定位。
二、已知二叉树的后序序列和中序序列，求解树。
<span style="color:#、确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。
<span style="color:#、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。
<span style="color:#、递归求解树。将左子树和右子树分别看成一棵二叉树，重复<span style="color:#、<span style="color:#、<span style="color:#步，直到所有的节点完成定位。
举例说明：根据已知求解二叉树
中序序列 HLDBEKAFCG
后序序列 LHDKEBFGCA
<span style="color:#、在后序序列LHDKEBFGCA中最后出现的元素为A，HLDBEK|A|FCG
2、在后序序列LHDKEB中最后出现的元素为B，HLD|B|EK|A|FCG
3、在后序序列LHD中最后出现的元素为D，HL|D|B|EK|A|FCG
<span style="color:#、在后序序列LH中最后出现的元素为H，H|L|D|B|EK|A|FCG
5、在后序序列KE中最后出现的元素为E，H|L|D|B|E|K|A|FCG
<span style="color:#、在后序序列FGC中最后出现的元素为C，H|L|D|B|E|K|A|F|C|G
6、所有元素都已经定位，二叉树求解完成。
#include &iostream&
#include &cstring&
char pre[50] = &ABDHLEKCFG&;
//前序序列
char mid[50] = &HLDBEKAFCG&;
//中序序列
char post[50] = &LHDKEBFGCA&;
//后序序列
typedef struct _Node
struct _Node *
struct _Node *
_Node():left(NULL),right(NULL){}
//每次初始化左右子树指针
}Node, *PN
void PostTravelTree(PNode pn);
//树的后序递归遍历
void PreTravelTree(PNode pn);
//树的前序递归遍历
void PreMidCreateTree(PNode &pn, int i, int j, int len);
//利用前序中序序列创建树
void PostMidCreateTree(PNode &pn, int i, int j, int len);
//利用后序中序序列创建树
int Position(char c);
//确定c在中序序列mid中的下标,假设树的各个节点的值各不相同
int main()
PNode root1 = NULL, root2= NULL;
PreMidCreateTree(root1, 0, 0, strlen(mid));
PostTravelTree(root1); cout&&
PostMidCreateTree(root2, strlen(post)-1, 0, strlen(mid));
PreTravelTree(root2); cout&&
system(&pause&);
int Position(char c)
return strchr(mid,c)-
利用前序中序序列创建树,参考了/sulipol/blog/item/f01a20011dcce31a738b6524.html
*的实现,代码十分简洁,竟然只有短短的&令人发指&的8行,递归实在太彪悍了!!!!!!!!!!!!!!!!!!!!!
i: 子树的前序序列字符串的首字符在pre[]中的下标
j: 子树的中序序列字符串的首字符在mid[]中的下标
len: 子树的字符串序列的长度
void PreMidCreateTree(PNode &pn, int i, int j, int len)
if(len &= 0)
pn = new N
pn-&v = pre[i];
int m = Position(pre[i]);
PreMidCreateTree(pn-&left, i+1, j, m-j);
//m-j为左子树字符串长度
PreMidCreateTree(pn-&right, i+(m-j)+1, m+1, len-1-(m-j));
//len-1-(m-j)为右子树字符串长度
利用后序中序序列创建树
i: 子树的后序序列字符串的尾字符在post[]中的下标
j: 子树的中序序列字符串的首字符在mid[]中的下标
len: 子树的字符串序列的长度
void PostMidCreateTree(PNode &pn, int i, int j, int len)
if(len &= 0)
pn = new N
pn-&v = post[i];
int m = Position(post[i]);
PostMidCreateTree(pn-&left, i-1-(len-1-(m-j)), j, m-j);//注意参数:m-j左子树的长度,len-1-(m-j)右子树的长度
PostMidCreateTree(pn-&right, i-1, m+1, len-1-(m-j));
void PostTravelTree(PNode pn)
//后序递归遍历
PostTravelTree(pn-&left);
PostTravelTree(pn-&right);
cout&&pn-&v&&& &;
void PreTravelTree(PNode pn)
//前序递归遍历
cout&&pn-&v&&& &;
PreTravelTree(pn-&left);
PreTravelTree(pn-&right);
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：445364次
积分：6722
积分：6722
排名：第1064名
原创：231篇
转载：103篇
评论：54条
(4)(5)(1)(2)(59)(40)(21)(22)(32)(36)(35)(26)(9)(1)(15)(1)(13)(12)已知一颗二叉树的后序遍历_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
2页1下载券7页1下载券28页1下载券3页&#165;1.005页免费 6页免费14页4下载券1页2下载券8页1下载券6页免费
喜欢此文档的还喜欢5页1下载券47页免费43页1下载券6页1下载券85页1下载券
已知一颗二叉树的后序遍历|
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢1、假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
1页1下载券2页免费6页免费2页1下载券1页2下载券 8页1下载券6页免费7页1下载券6页1下载券5页免费
1、假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历|
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢2254人阅读
已知二叉树后序遍历序列是DBCEFGHA，中序遍历序列EDCBAHFG，它的前序遍历的序列是?麻烦再画下这二叉树.
后续遍历的顺序是左右根，中序遍历的顺序是左根右 这点应该懂吧 由后续访问序列可以看出最后一个被访问的必定是这个树的根 而中序遍历的序列可以看出，一棵树当根确定后，在根前面被访问的是他的左子树，后边的是他的右子树元素 弄懂了上边两点就开始做题吧 由后序遍历序列是DBCEFGHA 为了方便，我写小写字母了啊 可以看出整棵树的根节点是a 再看中序遍历序列EDCBAHFG a是根节点 左子树由a左边的元素EDCB构成 右子树由a右边的元素HFG构成 也就是 a /----/ EDCB--HFG 到这里应该都懂吧 那接下来就着重讲一下左子树的确定 右子树同理可得了 看左子树有4个元素EDCB 后序遍历序列是DBCE 最后访问e 可以确定a下边连接的是e 根据中序遍历序列EDCB 最先访问e 由于中序遍历e前面没有元素 可以确定e左子树为空 即下面的样子 a // e / dbc 也就是还剩下dbc的顺序没理好 后序遍历序列是dbc 最后访问c 则c为根节点 连接e 中序遍历序列dcb c前边有d 后边有b 哪么可以确定dcb这棵树为 c // d b 哪么整棵树的左子树就确定了 为 e / c // d b 同理 右子树应为 h / g / f 则整棵树就出来了 为下图所示 得出整棵树 前序遍历自然不在话下 为aecdbhgf ------------------------晕了，想偷下懒都不行呵同理就是要你自己照着刚才的方法再推右边啊左边在上边已经说了那我们来看右边右边剩下HFG后序遍历序列是fghh最后被访问可以确定h是右子树的根也就是与a连着的是h接下来看中序遍历顺序是HFGh前面没有元素说明h的左子树为空剩下的g和f都是他的右子树的元素再看后续遍历序列FGg最后被访问可以确定g是根节点连接h然后看中序遍历序列fgf在前哪么f应该为g的左子树整棵树就出来了再不懂我也不知道怎么解释了额------------------------- 好久没做类似的题 有点生疏了 若果有错 欢迎指出
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：21648次
排名：千里之外
转载：33篇
(4)(9)(9)(13)}