如何通过后序遍历和中序遍历

职业培训 培训职业 2025-01-08
前序遍历: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 (规律:根在后;子树在根前且左子树比右子树靠前);其它例子:前

前序遍历: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. 由右子树的后序序列和中序序列建立右子树。

另外,站长团上有产品团购,便宜有保证

标签

版权声明:本文由哟品培原创或收集发布,如需转载请注明出处。

本文链接:http://www.yopinpei.com/i/2/1307782

猜你喜欢
其他标签