6.3 二叉树的遍历—二叉树的遍历方法及递归实现
二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。
遍历是二叉树中经常要用到的一种操作。因为在实际应用问题中，常常需要按一定顺序对二叉树中的每个结点逐个进行访问，查找具有某一特点的结点，然后对这些满足条件的结点进行处理。
通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。也就是说，遍历操作使非线性结构线性化。
由二叉树的定义可知，一棵由根结点、根结点的左子树和根结点的右子树三部分组成。
因此，只要依次遍历这三部分，就可以遍历整个二叉树。若以D、L、R 分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、DRL、RDL 和RLD。如果限定先左后右，则只有前三种方式，即DLR（称为先序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。
1．先序遍历（DLR）
先序遍历的递归过程为：若二叉树为空，遍历结束。否则，
（1）访问根结点；
（2）先序遍历根结点的左子树；
（3）先序遍历根结点的右子树。
先序遍历二叉树的递归算法如下：
void PreOrder（BiTree bt）
{/*先序遍历二叉树bt*/
if (bt==NULL) return; /*递归调用的结束条件*/
Visite（bt->data）; /*访问结点的数据域*/
PreOrder（bt->lchild）; /*先序递归遍历bt 的左子树*/
PreOrder（bt->rchild）; /*先序递归遍历bt 的右子树*/
}
算法6.5
对于图6 图6.3(b)所示的二叉树，按先序遍历所得到的结点序列为：A B D G C E F
（2）先序遍历根结点的左子树；
（3）先序遍历根结点的右子树。
先序遍历二叉树的递归算法如下：
void PreOrder（BiTree bt）
{/*先序遍历二叉树bt*/
if (bt==NULL) return; /*递归调用的结束条件*/
Visite（bt->data）; /*访问结点的数据域*/
PreOrder（bt->lchild）; /*先序递归遍历bt 的左子树*/
PreOrder（bt->rchild）; /*先序递归遍历bt 的右子树*/
}
算法6.5
对于图6 图6.3(b)所示的二叉树，按先序遍历所得到的结点序列为：A B D G C E F
2．中序遍历（LDR）
中序遍历的递归过程为：若二叉树为空，遍历结束。否则，
（1）中序遍历根结点的左子树；
（2）访问根结点；
（3）中序遍历根结点的右子树。
中序遍历二叉树的递归算法如下：
void InOrder（BiTree bt）
{/*中序遍历二叉树bt*/
if (bt==NULL) return; /*递归调用的结束条件*/
InOrder（bt->lchild）; /*中序递归遍历bt 的左子树*/
Visite（bt->data）; /*访问结点的数据域*/
InOrder（bt->rchild）; /*中序递归遍历bt 的右子树*/
}
算法6.6
对于图6.3(b)所示的二叉树，按中序遍历所得到的结点序列为：D G B A E C F
（1）中序遍历根结点的左子树；
（2）访问根结点；
（3）中序遍历根结点的右子树。
中序遍历二叉树的递归算法如下：
void InOrder（BiTree bt）
{/*中序遍历二叉树bt*/
if (bt==NULL) return; /*递归调用的结束条件*/
InOrder（bt->lchild）; /*中序递归遍历bt 的左子树*/
Visite（bt->data）; /*访问结点的数据域*/
InOrder（bt->rchild）; /*中序递归遍历bt 的右子树*/
}
算法6.6
对于图6.3(b)所示的二叉树，按中序遍历所得到的结点序列为：D G B A E C F
3．后序遍历（LRD）
后序遍历的递归过程为：若二叉树为空，遍历结束。否则，
（1）后序遍历根结点的左子树；
（2）后序遍历根结点的右子树。
（3）访问根结点；
后序遍历二叉树的递归算法如下：
void PostOrder（BiTree bt）
{/*后序遍历二叉树bt*/
if (bt==NULL) return; /*递归调用的结束条件*/
PostOrder（bt->lchild）; /*后序递归遍历bt 的左子树*/
PostOrder（bt->rchild）; /*后序递归遍历bt 的右子树*/
Visite（bt->data）; /*访问结点的数据域*/
}
算法6.7
对于图图6.3(b)所示的二叉树，按先序遍历所得到的结点序列为：G D B E F C A
4．层次遍历
所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。对于图6.3(b)所示的二叉树，按层次遍历所得到的结果序列为：A B C D E F G
下面讨论层次遍历的算法。
由层次遍历的定义可以推知，在进行层次遍历时，对一层结点访问完后，再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先访问，这与队列的操作原则比较吻合。因此，在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取一个元素，执行下面两个操作：
（1）访问该元素所指结点；
（2）若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。
此过程不断进行，当队列为空时，二叉树的层次遍历结束。在下面的层次遍历算法中，二叉树以二叉链表存放，一维数组Queue[MAXNODE]用以实现队列，变量front 和rear 分别表示当前对首元素和队尾元素在数组中的位置。
void LevelOrder（BiTree bt）
/*层次遍历二叉树bt*/
{ BiTree Queue[MAXNODE];
int front,rear;
if (bt==NULL) return;
front=-1;
rear=0;
queue[rear]=bt;
while(front!=rear)
{front++;
Visite(queue[front]->data); /*访问队首结点的数据域*/
if (queue[front]->lchild!=NULL) /*将队首结点的左孩子结点入队列*/
{ rear++;
queue[rear]=queue[front]->lchild;
}
if (queue[front]->rchild!=NULL) /*将队首结点的右孩子结点入队列*/
{ rear++;
queue[rear]=queue[front]->rchild;
}
}
}
算法6.8
下面讨论层次遍历的算法。
由层次遍历的定义可以推知，在进行层次遍历时，对一层结点访问完后，再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先访问，这与队列的操作原则比较吻合。因此，在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取一个元素，执行下面两个操作：
（1）访问该元素所指结点；
（2）若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。
此过程不断进行，当队列为空时，二叉树的层次遍历结束。在下面的层次遍历算法中，二叉树以二叉链表存放，一维数组Queue[MAXNODE]用以实现队列，变量front 和rear 分别表示当前对首元素和队尾元素在数组中的位置。
void LevelOrder（BiTree bt）
/*层次遍历二叉树bt*/
{ BiTree Queue[MAXNODE];
int front,rear;
if (bt==NULL) return;
front=-1;
rear=0;
queue[rear]=bt;
while(front!=rear)
{front++;
Visite(queue[front]->data); /*访问队首结点的数据域*/
if (queue[front]->lchild!=NULL) /*将队首结点的左孩子结点入队列*/
{ rear++;
queue[rear]=queue[front]->lchild;
}
if (queue[front]->rchild!=NULL) /*将队首结点的右孩子结点入队列*/
{ rear++;
queue[rear]=queue[front]->rchild;
}
}
}
算法6.8
