现在的位置: 首页 > 综合 > 正文

如何根据两个遍历建立二叉树

2013年12月13日 ⁄ 综合 ⁄ 共 577字 ⁄ 字号 评论关闭

前序遍历:1 2 4 8 9 10 11 5 3 6 7 (规律:根在前;子树在根后且左子树比右子树靠前); 

中序遍历:8 4 10 9 11 2 5 1 6 3 7 (规律:根在中;左子树在跟左边,右子树在根右边);

后序遍历:8 10 11 9 4 5 2 6 7 3 1 (规律:根在后;子树在根前且左子树比右子树靠前); 

其它例子:

 前序遍历:ABDECFG

 中序遍历:DBEAFCG

 后序遍历:DEBFGCA

 前序遍历:1 2 4 3 5 7 6 

中序遍历:2 4 1 5 7 3 6 

后序遍历:4 2 7 5 6 3 1 

做类似的题目,你可以先由两个遍历画出二叉树。通过形象的二叉树来写出另一个遍历,写的方法如上(递归)。画出二叉树的方法如下: 已知一棵二叉树的前序序列和中序序列,构造该二叉树的过程如下:

 1. 根据前序序列的第一个元素建立根结点;

 2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列;

 3. 在前序序列中确定左右子树的前序序列;

 4. 由左子树的前序序列和中序序列建立左子树; 

5. 由右子树的前序序列和中序序列建立右子树。

 已知一棵二叉树的后序序列和中序序列,构造该二叉树的过程如下: 

1. 根据后序序列的最后一个元素建立根结点;

 2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列;

 3. 在后序序列中确定左右子树的后序序列; 

4. 由左子树的后序序列和中序序列建立左子树; 

5. 由右子树的后序序列和中序序列建立右子树。 

抱歉!评论已关闭.