您的位置: 网站首页 > 程序开发 > 数据结构 > 第5章 树与二叉树 > 【5.4 二叉树的遍历】

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为一个数组,最大值的个数为ni为索引,一开始i-1for为无穷循环,当进入while内循环时,主要将二叉树所有左边的节点一一入栈,若i的值大于n表示堆栈已满,否则将T的指针存放在STACK[i]中,并将T移到TllinkSTACK[i]struct node*的形态。