二叉树的层次遍历

「爱情、让人受尽委屈。」 2022-06-14 23:56 260阅读 0赞

/*二叉树的层次遍历*/
    #include<stdio.h>
    #define MAX 1000
    typedef char datatype;
    typedef struct Binnode{
        datatype data;                  /*数据域*/
        struct BinNode* lchild,*rchild;  /*指向左、右孩子的指针*/
    }BinNode,*Bintree;
    /*按先序创建二叉树*/
    Bintree CreateTree(Bintree T)
    {
        char ch;
        scanf("%c",&ch);
        if(ch=='#')
            return 0;
        else
        {
            T=(Bintree)malloc(sizeof(BinNode));
            T->data=ch;
            T->lchild=CreateTree(T->lchild);/*创建左子树*/
            T->rchild=CreateTree(T->rchild);/*创建右子树*/
            return T;
        }
    }
    /*层次遍历二叉树*/
    void Levelorder(Bintree T)
    {
        Bintree p;
        Bintree qu[MAX];            /*定义循环队列，存放节点指针。*/
        int front,rear;             /*定义队头和队尾指针*/
        front=rear=0;               /*置队列为空队*/
        rear++;
        qu[rear]=T;                 /*根节点指针进队*/
        while(front!=rear)          /*队列不为空*/
        {
            front=(front+1)%MAX;
            p=qu[front];            /*队头出队*/
            printf("%c ",p->data);  /*访问节点*/
            if(p->lchild!=NULL)     /*有左孩子时将其进队*/
            {
                rear=(rear+1)%MAX;
                qu[rear]=p->lchild;
            }
            if(p->rchild!=NULL)     /*有右孩子时将其进队*/
            {
                rear=(rear+1)%MAX;
                qu[rear]=p->rchild;
            }
        }
    }
    main()
    {
        Bintree t;
        printf("请按先序的方式输入二叉树的结点元素（注：#表示节点为空）:");
        t=CreateTree(t);
        printf("按层次遍历输出:");
        Levelorder(t);
    }

![二叉树的层次遍历][SouthEast]

[SouthEast]: /images/20220615/5f57881f03054aaa8f4b64292a103cef.png