数据结构例程——二叉树的层次遍历算法

朴灿烈づ我的快乐病毒、 2022-01-27 14:11 171阅读 0赞

本文是[数据结构基础系列(6)：树和二叉树][6]中第12课时[层次遍历算法][Link 1]的例程。

【二叉树的层次遍历算法】  
　　实现二叉树的层次遍历算法，并对用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建的二叉树进行测试。  
　　请利用[二叉树算法库][Link 2]。

［参考解答］（btreee.h见[算法库][Link 2]）

#include <stdio.h>
    #include "btree.h"
    
    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;
            }
        }
    }
    
    int main()
    {
        BTNode *b;
        CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
        printf("二叉树b: ");
        DispBTNode(b);
        printf("\n");
        printf("层次遍历序列:\n");
        LevelOrder(b);
        DestroyBTNode(b);
        return 0;
    }

注：在main函数中，创建的用于测试的二叉树如下——  
![这里写图片描述][20151019153602522]

[6]: http://edu.csdn.net/course/detail/1553
[Link 1]: http://edu.csdn.net/course/detail/1553/24077
[Link 2]: http://blog.csdn.net/sxhelijian/article/details/49250581
[20151019153602522]: /images/20220127/0ed5f948fec2476ca6b16df763004248.png