沪江网店
考研专业课之统考计算机蓝宝书(20)
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之间即可。
-
1987-2009考研真题专辑
沉淀历史，最全考研历年真题... -
2009暑期考研复习全攻略
这个暑期，我在考研的复习之路上... -
2010考研书籍推荐专题
考研前辈们事半功倍的经典选择... -
新东方网络课程免费试听
只买对的，不买贵的，先试听后购买… -
陈冠希CNN专访谈艳照门
CNN专访视频报道，附全文文本... -
俞敏洪寄语2010年考研学生
新东方俞敏洪寄语今年考研学生... -
2010任汝芬政治复习指导
任汝芬先生亲自指导你的政治复习... - 查看所有近期热点专题
