5.4 二叉树的遍历
5.4 二叉树的遍历
在二叉树的一些应用中，常常要求在树中查找具有某种特征的节点，或者对树中全部节点逐一进行某种处理。这就提出了一个遍历二叉树的问题，即如何按一定的规律和次序访问树中的每个节点，使得每个节点被访问一次，而且仅被访问一次。
二叉树常用的遍历有先序遍历、中序遍历、后序遍历和层次遍历。
1．先序遍历
若二叉树非空，则：
（1）访问根节点。
（2）先序遍历左子树。
（3）先序遍历右子树。
对应的递归算法如下：
void PreOrder(BTNode *bt)
{
if (bt!=NULL)
{
printf("%c ",bt->data);
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
采用先序遍历得到的访问节点序列称为先序遍历序列，先序遍历序列的特点是：其第一个元素值为二叉树中根节点的数据值。
如图5-8所示的二叉树，先序遍历序列为：ABDEGHCF。
2．中序遍历
若二叉树非空，则：
（1）中序遍历左子树。
（2）访问根节点。
（3）中序遍历右子树。
对应的递归算法如下：
void InOrder(BTNode *bt)
{
if (bt!=NULL)
{
InOrder(bt->lchild);
printf("%c ",bt->data);
InOrder(bt->rchild);
}
}
采用中序遍历得到的访问节点序列称为中序遍历序列，中序遍历序列的特点是：若已知二叉树的根节点数据值，以该数据值为界，将中序遍历序列分为两部分，前半部分为左子树的中序遍历序列，后半部分为右子树的中序遍历序列。
如图5-8所示的二叉树，中序遍历序列为：DBGEHAFC。
3．后序遍历
若二叉树非空，则：
（1）后序遍历左子树。
（2）后序遍历右子树。
（3）访问根节点。
对应的递归算法如下：
void PostOrder(BTNode *bt)
{
if (bt!=NULL)
{
PostOrder(bt->lchild);
PostOrder(bt->rchild);
printf("%c ",bt->data);
}
}
采用后序遍历得到的访问节点序列称为后序遍历序列，后序遍历序列的特点是：其最后一个元素值为二叉树中根节点的数据值。
如图5-8所示的二叉树，后序遍历序列为：DGHEBFCA。
4．层次遍历
在进行层次遍历时，对某一层的节点访问完后，再按照它们的访问次序对各个节点的左、右孩子顺序访问，这样一层一层进行，先访问的节点其左、右孩子也要先访问，这样与队列的操作原则比较吻合。因此层次遍历算法采用一个环形队列qu来实现。
层次遍历过程是先将根节点进队，在队不空时循环：从队列中出列一个节点*p，访问它；若它有左孩子节点，将左孩子节点进队；若它有右孩子节点，将右孩子节点进队。如此操作直到队空为止。对应的算法如下：
void LevelOrder(BTNode *b)
{
BTNode *p;
BTNode *qu[MaxSize]; /*定义环形队列，存放节点指针*/
int front,rear; /*定义队头和队尾指针*/
front=rear=-1; /*置队列为空队列*/
rear++;
qu[rear]=b; /*根节点指针进入队列*/
while(front!=rear) /*队列不为空*/
{
front=(front+1)%MaxSize;
p=qu[front]; /*队头出队列*/
printf("%c ",p->data); /*访问节点*/
if(p->lchild!=NULL) /*有左孩子时将其进队*/
{
rear=(rear+1)%MaxSize;
qu[rear]=p->lchild;
}
if(p->rchild!=NULL) /*有右孩子时将其进队*/
{
rear=(rear+1)%MaxSize;
qu[rear]=p->rchild;
}
}
}
采用层次遍历得到的访问节点序列称为层次遍历序列。如图5-8所示的二叉树，层次遍历序列为：ABCDEFGH。
在上述4种遍历算法设计好后，编写如下主程序调用这些算法：
void main()
{
BTNode *bt;
CreateBTree(bt,"A(B(D,E(G,H)),C(,F(I)))"); /*构造一棵二叉树*/
printf("二叉树bt:");DispBTree(bt);printf("\n");
printf("先序遍历序列:");PreOrder(bt);printf("\n");
printf("中序遍历序列:");InOrder(bt);printf("\n");
printf("后序遍历序列:");PostOrder(bt);printf("\n");
printf("层次遍历序列:");LevelOrder(bt);printf("\n");
}
上述程序的执行结果如下：
二叉树bt:A(B(D,E(G,H)),C(,F(I)))
先序遍历序列:A B D E G H C F I
中序遍历序列:D B G E H A C I F
后序遍历序列:D G H E B I F C A
层次遍历序列:A B C D E F G H I
除了以递归的方式表示外，也可以利用非递归的方式来处理，虽然较复杂，但可以更清楚地遍历每一个细节。以下是中序遍历的非递归程序段。
void inorder(struct node *T)
{
int i=-1;
for(; ;)
{
while(T !=NULL)
{
i=i+1;
if(i>n)
printf("The stack is full");
else
{
STACK[i]=T;
t=t->llink;
}
}
if(i = -1)
{
T=STACK(i);
i=i-1;
printf("%d",T->data);
T=T->rlink;
}
else
return;
}
}
程序中的node结构如图5-10所示。
图5-10 node结构图
STACK为一个数组，最大值的个数为n，i为索引，一开始i为-1，for为无穷循环，当进入while内循环时，主要将二叉树所有左边的节点一一入栈，若i的值大于n表示堆栈已满，否则将T的指针存放在STACK[i]中，并将T移到T的llink，STACK[i]为struct node*的形态。