考研专业课之统考计算机蓝宝书(20)

来源：跨考网 2009-01-03 21:32

3.2.3 二叉树的遍历

1.二叉树的遍历方法及其递归实现

二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。也就是说，遍历操作使非线性结构线性化。

由二叉树的定义可知，一棵由根结点、根结点的左子树和根结点的右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。限定先左后右，只有前三种方式，即DLR（称为先序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。

(1). 先序遍历（DLR）

先序遍历的递归过程为：若二叉树为空，遍历结束。否则，
1 访问根结点；
2 先序遍历根结点的左子树；
3 先序遍历根结点的右子树。

(2). 中序遍历（LDR）

中序遍历的递归过程为：若二叉树为空，遍历结束。否则，
1 中序遍历根结点的左子树；
2 访问根结点；
3 中序遍历根结点的右子树。

订阅收藏考研专业课之统考计算机蓝宝书

(3). 后序遍历（LRD）

后序遍历的递归过程为：若二叉树为空，遍历结束。否则，
1 后序遍历根结点的左子树；
2 后序遍历根结点的右子树。
3 访问根结点；

(4). 层次遍历

所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。

下面讨论层次遍历的算法。
由层次遍历的定义可以推知，在进行层次遍历时，对一层结点访问完后，再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先访问，这与队列的操作原则比较吻合。因此，在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取一个元素，执行下面两个操作：
1 访问该元素所指结点；
2 若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩
子指针和右孩子指针顺序入队。
此过程不断进行，当队列为空时，二叉树的层次遍历结束。

2. 二叉树遍历的非递归实现

(1). 先序遍历的非递归实现

在下面算法中，二叉树以二叉链表存放，一维数组stack[MAXNODE]用以实现栈，变量top用来表示当前栈顶的位置。
(2). 中序遍历的非递归实现

中序遍历的非递归算法的实现，只需将先序遍历的非递归算法中的Visite(p->data)移到p=stack[top]和p=p->rchild之间即可。