5.5 确定唯一的二叉树

5.5  确定唯一的二叉树

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

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

由前序可知B是FDHGIE的父节点，并从中序次序可知E是B的右子节点，如图5-12所示。

图5-11  判断出节点A和C性质的示意图              图5-12  判断出节点B和E性质的示意图

再由前序次序可知D是FHGI的父节点，由中序可知F是D的左子节点，HGI是D的右子节点，如图5-13所示。

最后由前序次序可知G是HI的父节点，并从中序次序可知H是G的左子节点，I是G的右子节点，如图5-14所示。

图5-13  判断出节点D和F性质的示意图           图5-14  判断出节点G和I性质的示意图

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

中序：BCDAFEHIG

后序：DCBFIHGEA

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

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

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

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

由前序遍历得知H为I的树根，而由中序遍历可知I在H节点的右边，故二叉树如     图5-18所示。

图5-17  判断出节点C、D和G性质的示意图           图5-18  判断出节点H和I性质的示意图

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