已知二叉树的中根序列和后根序列,确定树的结构。

已知二叉树的中根序列和后根序列,确定一个树的结构。

比如:已知二叉树的

中根序列:c,b,d,e,a,g,i,h,j,f

后根序列:c,e,d,b,i,j,h,g,f,a

求:二叉树的结构。

具体求解方法:

中序遍历:左根右。

后序遍历:左右根。

1. 由后根序列可知a为整个树的根, (c,b,d,e) 属于其左子树,(g,i,h,j,f)属于其右子树,即有:

2. 由后根序列(c, e, d, b)可知,b为a左子树的根;由中根序列(c, b, d, e)可知,c为b的左子树,(d, e)为b的右子树。由后根序列(I, j, h, g, f)可知,f为a的右子树的根;由中根序列(g, I, h, j, f)可知,(g, i, h, j)为f的左子树,f的右子树为空。即有:

3. 由后跟序列(e, d)可知,d为根;由中根序列(d, e)可知,e为d的右子树,d的左子树为空。由后根序列(i, j, h, g)可知,g为根;有中根序列(g, i, h, j)可知,(i, h, j)为g的左子树,g的右子树为空。即有:

4. 由后根序列(i, j, h)可知,h为根;由中根序列ihj可知,i为h的左子树,j为h的右子树。即有:

 

二叉树

(1)二叉树分类

一般二叉树,完全二叉树,满二叉树。

满二叉树:二叉树中除了叶节点以外的结点都有两个子节点,且叶节点位于同一层。

完全二叉树:当且仅当一颗深度为k、具有n个结点的二叉树的每个节点与深度为k的完全二叉树中编号从1~n的节点一一对应时,称该树为完全二叉树。

(2)二叉树的遍历方法

先序遍历:访问根节点->先序遍历左子树->先序遍历右子树。

中序遍历:先序遍历左子树->访问根节点->先序遍历右子树。

后序遍历:先序遍历左子树->先序遍历右子树->访问根节点