tip
二叉树的中序遍历就是首先遍历左子树，然后访问根节点，最后遍历右子树。对于下面的二叉树，中序遍历结果如下：
image
结果：[5,10,6,15,2]
直观来看，二叉树的中序遍历就是将节点投影到一条水平的坐标上。如图：
image
image.png
-
前根序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。
ABDHECFG -
中根序遍历：先遍历左子树，然后遍历根结点，最后遍历右子树。
HDBEAFCG -
后根序遍历：先遍历左子树，然后遍历右子树，最后遍历根节点。
HDEBFGCA
已知一棵二叉树的前根序序列和中根序序列，构造该二叉树的过程如下：
- 根据前根序序列的第一个元素建立根结点；
- 在中根序序列中找到该元素，确定根结点的左右子树的中根序序列；
- 在前根序序列中确定左右子树的前根序序列；
- 由左子树的前根序序列和中根序序列建立左子树；
- 由右子树的前根序序列和中根序序列建立右子树。
已知一棵二叉树的后根序序列和中根序序列，构造该二叉树的过程如下： - 根据后根序序列的最后一个元素建立根结点；
- 在中根序序列中找到该元素，确定根结点的左右子树的中根序序列；
- 在后根序序列中确定左右子树的后根序序列；
- 由左子树的后根序序列和中根序序列建立左子树；
- 由右子树的后根序序列和中根序序列建立右子树。
网友评论