二叉树遍历

未匹配的标注

@author 汪春波

遍历

二叉树遍历

树的遍历方法也同样适用于二叉树(如右图4-11所示),不过由于二叉树的自身特点,还有一种中序遍历法。

前序遍历(根左右)

前序遍历(根左右,先访问根结点,然后分别用前序分别遍历左、右子树,也称为前根遍

历)。图4-11的前序遍历结果是:1,2,4,5,7,8,3,6。

中序遍历(左根右)

中序遍历(左根右,先按中序遍历左子树,再访问根结点,然后再按中序遍历右子树,也称为

中根遍历)。图4-11的中序遍历的结果是:4,2,7,8,5,1,3,6。

二叉树遍历

首先 根为 1

最左边。2 的子树, 左4 2 ;得到遍历数字
4 2

左边有 5 的子树, 左 7 根5
但是 7 也有子树, 左 空 根 7 右 8
这里得到7 8 5
总共为 4 2 7 8 5
同理推出:右边 从1 开始(这里最右就是1开始)

1 下面 左 空 根 1 右边 3
得到 1 3

3 子节点, 左空 根 3 右 6
得到 3 6

加起来 为 1 3 6

所以全部加起来为:4,2,7,8,5,1,3,6

后序遍历

后序遍历(左右根,分别按后序遍历要左、右子树,然后再访问根结点,也称为后根遍历)。

图4-11的后序遍历的结果是:4,8,7,5,2,6,3,1。

分析:
左右根,则 根节点1 肯定最后。

左边:
4开始, 4

7开始, 8 7

5开始, 7 5

得到 4 8 7 5

从 2 开始, 4 5 2

结合推一下,得到 4 8 7 5 2

右边: 3 开始, 6 3。
1开始, 3 1。
结合为 6 3 1

上边左右全部结合为: 4 8 7 5 2 6 3 1

层次遍历(最简单的)

层次遍历(首先访问处于0层的根结点,然后从左到右访问1层上的结点,以此类推,层层向下

访问)。图4-11的层次遍历的结果是:1,2,3,4,5,6,7,8。

本文章首发在 LearnKu.com 网站上。

上一篇 下一篇
讨论数量: 0
发起讨论 只看当前版本


暂无话题~