二叉树先序中序问题

一个二叉树，前序为abcdefghij 中序cbaefdihjg
画出图并求后序

转身离开吹散 · 2018-4-30 02:07:24

画图不好画，我跟你说一遍，你自己按照我说的画一遍，a 的左孩子是 b右孩子是 d,b的左孩子是c,d的左孩子是e,右孩子是g,e的右孩子是f,g的左孩子是h,h的左孩子是i,右孩子是j,后序是cbafeijhgda

gkapt71 · 2018-4-30 02:07:25

后序最后一个是A，所以A是先序的第一个得到：
先序序列 ABC_EF__
中序序列 BDE_AG_H
后序序列 _DC_GH_A
_____________(A)____________
____________/___\___________
________(BDE_)_(G_H)________

先序的第二个元素是B，所以B是A的左子树根节点
由中序B在最前，知道其他元素都在B的右子树上
所以，后序序列为(DE_)B(G_H)A，对比已有的后序序列_DC_GH_A
得后序序列为：EDCBGHFA，中序序列为：BDECAGFH
先序序列 ABC_EF__
中序序列 BDECAGFH
后序序列 EDCBGHFA
所以，二叉树为：
_____________(A)_____________
____________/___\____________
__________(B)____(F)_________
___________\_____/_\_________
___________(C)_(G)_(H)_______
___________/_________________
_________(D)_________________
__________\__________________
__________(E)________________
如果还没解决你的问题，可以加我百度HI账号。

二叉树先序中序问题

2 个回复

浏览过的版块