终身教育平台
6.4 二叉树的遍历
结合视频讲解，掌握二叉树先序、中序、后序递归遍历算法和中序遍历非递归算法的思想，能够根据二叉树的图形表示熟练写出其先序、中序、后序遍历的序列。
1.二叉树遍历的概念
（1）遍历
二叉树的遍历是指按照一定次序访问树中所有结点，并且每个结点的值仅被访问一次的过程。
（2）遍历的三个子问题及三种访问方式
访问根结点，遍历左子树、遍历右子树
先左后右，即先遍历左子树，再遍历右子树，并以根结点访问的次序划分先序、中序、后序
先序遍历：先访问根结点，然后遍历左子树，再遍历右子树
中序遍历：先遍历左子树，然后访问根结点，最后遍历右子树
后序遍历：先遍历左子树，然后遍历右子树，最后访问根结点
想一想：如果一个叶子结点是某二叉树中序遍历序列的最后一个结点，那么它也是该二叉树的先序遍历序列的最后一个结点，这种说法对吗？
解题分析：
正确。因为二叉树中序遍历的最后一个结点，一定位于二叉树的右子树上最右端，无论先序遍历或中序遍历，右子树上的最右端的叶子结点肯定最后访问。
2.二叉树的递归遍历算法
（1）先序遍历算法
【算法6-1】 先序遍历算法
void Preorder(struct BTreeNode* BT)
{
if(BT!=NULL) {
printf("%c",BT->data); /*访问根结点*/
Preorder(BT->left); /*先序遍历左子树*/
Preorder(BT->right); /*先序遍历右子树*/
}
}
（2） 中序遍历算法
【算法6-2】 中序遍历算法
void Inorder(struct BTreeNode* BT)
{
if(BT!=NULL) {
Inorder(BT->left); /*中序遍历左子树*/
printf("%c",BT->data); /*访问根结点*/
Inorder(BT->right); /*中序遍历右子树*/
}
}
（3） 后序遍历算法
【算法6-3】 后续遍历算法
void Postorder(struct BTreeNode* BT)
{
if(BT!=NULL) {
Postorder(BT->left); /*后序遍历左子树*/
Postorder(BT->right); /*后序遍历右子树*/
printf("%c ",BT->data); /*访问根结点*/
}
}
在这三种遍历算法中，访问根结点进行何种操作可视具体应用情况而定，这里暂以打印根结点的值代之。当然若结点的值为用户定义的记录类型，则还必须依次输出结点值对象中的每个域的值。
（4）递归遍历算法的执行过程
下面以中序递归遍历算法为例，结合图6-9的二叉树，分析其执行过程。
图6-9 二叉树递归遍历举例
当从其他函数调用（此次称为第0次递归调用）中序遍历算法时，需要以指向树根A结点的指针Ap作为实参，把它传递给算法中的值参BT，调用递归算法时系统自动建立的工作栈应包括BT域和返回地址r域，假定进行第0次递归调用后的返回地址为r0，中序遍历左子树后的返回地址（即printf语句的开始地址）为r1，中序遍历右子树后的返回地址（即算法结束的地址）为r2，并假定指向每个结点的指针用该结点的值后缀小写字母p表示，如指向B结点的指针就用Bp表示，则每次进行递归调用时工作栈中的数据变化情况如图6-10所示。
图6-10 二叉树中序递归遍历时工作栈的变化情况
由上述分析中序递归遍历算法的执行过程可知，结点的访问序列为：
C，B，D，A，E，G，F
类似地，若按照先序递归遍历算法和后序递归遍历算法遍历图6-9所示的二叉树，则结点的访问序列分别为：
A，B，C，D，E，F，G和C，D，B，G，F，E，A
（5）递归遍历算法的时空复杂度分析
在二叉树的三种递归遍历算法中，都访问到了每个结点的每一个域，并且每个结点的每一个域仅被访问一次。所以三种递归遍历算法的时间复杂度均为O，n表示二叉树中结点的个数。另外在执行每个递归遍历算法时，系统都要使用一个栈，栈的最大深度等于二叉树的深度加1，而二叉树的深度视其具体形态决定，若二叉树为理想二叉树或接近理想二叉树，则二叉树的深度大致为log2n，所以其空间复杂度为O(log2n)，若二叉树退化为一棵单支树（即最差的情况），则空间复杂度为O
，n同样为二叉树中的结点数。
3.二叉树的非递归遍历算法
二叉树的遍历算法也可以编写为非递归的形式，这需要在算法中使用栈结构，利用栈后进先出的特性保存稍后待访问的每个子树的根指针。下面以中序遍历为例，讨论二叉树的非递归算法。
算法简述
p=根指针；p非空转（b），p为空结
（a）p（指针）进栈，访问左子树，p=p-> left ;若p非空重复（a），若为空转（b）；
（b）（出栈）p=栈顶指针；得到树（子树）的根指针，打印，访问右子树，p=p->right; p非空转（a）；若p为空且栈非空重复（b）。若p和栈皆空则结束。
在此算法中需要首先定义一个元素类型为结点指针类型（struct BTreeNode*）的一个数组，当做保存树根指针的栈使用，该栈的最大深度（即数组长度）要大于待遍历的整个二叉树的深度；同时要定义一个整型变量当做栈顶指针使用，并赋初值为-1表示空栈。算法开始时，定义一个指针变量并初始指向待中序遍历的整个二叉树，接着若栈不等于空或者指针变量不为空就执行一个循环。在循环体内，首先只要指针变量不为空，就令其进栈，并接着使指针变量指向左子树；当指针变量为空时，表明已经访问到左子树为空的结点，应接着输出栈顶元素所指向结点的值并退栈，再使指针变量指向被输出结点的右子树。
根据以上分析，编写出中序遍历的非递归算法如下。
【算法6-4】 二叉树中序遍历的非递归算法
void InorderN(struct BTreeNode* BT) /*对二叉树进行中序遍历的非递归算法*/
{
struct BTreeNode* s[10]; /*定义用于存储结点指针的栈*/
int top=-1; /*定义栈顶指针并赋初值使s栈为空*/
struct BTreeNode* p=BT; /*定义指针p并使树根指针为它的初值*/
while(top!=-1 || p!=NULL)
{ /*当栈非空或p指针非空时执行循环*/
while(p!=NULL) { /*依次向下访问左子树并使树根指针进栈*/
top++;
s[top]=p;
p=p->left;
}
if(top!=-1) { /*树根指针出栈并输出结点的值，接着访问右子树*/
p=s[top];
top--;
printf("%c ",p->data);
p=p->right;
}
}
}
在此算法的整个执行过程中，指向整个树根结点的指针和所有结点的指针域的值都要各进行一次进栈和出栈的操作，每次进栈或出栈的时间复杂度为O(1)，整个算法共需要进行2n+1次进栈和出栈的操作，其中n表示结点数，所以此算法的时间复杂度为O。此算法的空间复杂度取决于作为栈使用而定义的数组的长度，数组长度应大于等于待遍历的二叉树的深度加1，若二叉树接近理想二叉树，则二叉树的空间复杂度为O(log2n)。
4.二叉树的按层遍历算法
上面所述的二叉树的遍历是按二叉树的递归结构进行的，另外，还可以按照二叉树的层次结构进行遍历，即按照从上到下、同一层从左到右的次序访问各结点。如对于图6-9所示的二叉树，按层遍历各结点的次序为：
A, B, E, C, D, F, G
按层遍历算法需要使用一个队列，开始时把整个树的根结点的指针入队，然后每从队列中删除一个元素并输出所指向结点的值时，都接着把它的非空的左、右孩子结点的指针入队，这样依次进行下去，直到队列空时算法结束。
此算法为一个非递归算法，具体描述如下。
【算法6-5】 二叉树的按层遍历算法
void Levelorder(struct BTreeNode* BT)
{ /*按层遍历由BT指针所指向的二叉树*/
/*定义队列所使用的数组空间，元素类型为指向结点的指针类型*/
struct BTreeNode* q[MS]; /*MS为事先定义的符号常量*/
/*定义队首指针和队尾指针，初始均置0表示空队*/
int front=0, rear=0;
/*将树根指针进队*/
if(BT!=NULL) {
rear=(rear+1)% MS;
q[rear]=BT;
}
/*当队列非空时执行循环*/
while (front!=rear) {
struct BTreeNode* p; /*定义指针变量p*/
/*使队首指针指向队首元素*/
front=(front+1)%MS;
/*删除队首元素，输出队首元素所指结点的值*/
p=q[front];
printf("%c ",p->data);
/*若结点存在左孩子，则左孩子结点指针进队*/
if(p->left!=NULL) {
rear=(rear+1)%MS;
q[rear]=p->left;
}
/*若结点存在右孩子，则右孩子结点指针进队*/
if(p->right!=NULL) {
rear=(rear+1)%MS;
q[rear]=p->right;
}
}
}
在这个算法中，队列的最大长度不会超过二叉树中一层上的最多结点数，在定义队列数组时，要使数组的长度大于队列的最大长度，这样在结点进队时肯定不会发生溢出，因此也就不需要判断是否队满了。此算法需要使指向树中每个结点的指针进队和出队，进队和出队的时间复杂度为O(1)，所以此按层遍历算法的时间复杂度为O，n表示二叉树中结点的个数。
最后修改: 2019年09月10日 Tuesday 13:41
终身教育平台