数据结构，已知遍历反推二叉树

先序遍历：GFKDAIEBCHJ
中序遍历：DIAEKFCJHBG
已知以上两个二叉树遍历，怎么样能反推出二叉树，我从二叉树推遍历可以推出来，但是反推回去始终找不到窍门，希望高手指点，我想要很详细的讲解步骤，谢谢，十分详细的还会加分

chenhaooo · 2018-4-30 01:12:49

设先序队列为X,中序队列为Y。
X中先弹出G，则G为二叉树的顶点；Y中在G左边的为G的左子树，右边的为G的右子树；
X中再弹出F，则F为G左子树的顶点，Y中在F左边的为F的左子树，F与G中间的为F的右子树；
……
就这样，一个个从X中弹出顶点；根据弹出的点在Y中的位置，来判断是左孩子还是右孩子；

百度的排版太乱了。。。是一个6层的

￠幻冰 · 2018-4-30 01:12:48

1.先序遍历：GFKDAIEBCHJ
2.中序遍历：DIAEKFCJHBG

由1知G是根结点
由于G在2的最后G左边的字母都在左子树中

再由1知F是左子树的根结点
由2知DIAEK是F的左子树,CJHB是F的右子树

依次类推......
G
F#
KB
D#C#
#A#H
IEJ#

不明白给我发信息

rypgood · 2018-4-30 01:12:47

先序遍历：GFKDAIEBCHJ
中序遍历：DIAEKFCJHBG

由前序知，g为root，f为左root，又根据中序知道，g没右支。
看f，由中序知，DIAEK为f左支，CJHB为f右支
由前序知，k为f左root，d为k左root，k无右支
又由中序知，d没左支。
那么iae为d右支，又由前序知，a为d右root，而i、e为其左右叶子
同样的道理计算出f右支cjhb的顺序，很容易就求出来啦

数据结构，已知遍历反推二叉树

3 个回复

浏览过的版块