您的位置: 网站首页 > 程序开发 > 数据结构 > 第5章 树与二叉树 > 【5.5 确定唯一的二叉树】

5.5 确定唯一的二叉树

 

5.5  确定唯一的二叉树

每一棵二叉树都有唯一的一对中序与前序次序,也有唯一的中序与后序次序。换句话说,给予一对中序与前序或中序与后序即可决定一棵二叉树。然而给定前序和后序次序并不能决定唯一的二叉树,可能会产生两棵不同的二叉树。

如给定中序次序是FDHGIBEAC,而前序次序是ABDFGHIEC。由前序次序可知,A是树根,且由中序次序可知CA的右子节点,如图5-11所示。

由前序可知BFDHGIE的父节点,并从中序次序可知EB的右子节点,如图5-12所示。

                  

5-11  判断出节点AC性质的示意图              5-12  判断出节点BE性质的示意图

再由前序次序可知DFHGI的父节点,由中序可知FD的左子节点,HGID的右子节点,如图5-13所示。

最后由前序次序可知GHI的父节点,并从中序次序可知HG的左子节点,IG的右子节点,如图5-14所示。

         

5-13  判断出节点DF性质的示意图           5-14  判断出节点GI性质的示意图

由中序与后序也可得到唯一的二叉树。

中序:BCDAFEHIG

后序:DCBFIHGEA

由后序可知A为树根,再由中序得知其二叉树如图5-15所示。

由后序可知BCD的树根,再由中序得知CD节点为B节点的右节点,而FEHIG的树根为E,如图5-16所示。

                 

5-15  判断出节点A性质的示意图               5-16  判断出节点BE性质的示意图

CD的树根,GHI的树根,再由中序得知HI节点应为G的左节点,如图5-17所示。

由前序遍历得知HI的树根,而由中序遍历可知IH节点的右边,故二叉树如     5-18所示。

           

5-17  判断出节点CDG性质的示意图           5-18  判断出节点HI性质的示意图

但是由前序和后序遍历无法得到所对应的二叉树。