数据结构利用循环队列层次遍历一棵二叉树递归实现

淩亂°似流年 2022-08-21 08:46 93阅读 0赞

利用循环队列层次遍历一棵二叉树 递归实现

代码实现：

#include <iostream> ///循环队列实现层次遍历二叉树
    #include <stdio.h>
    #include <stdlib.h>
    
    #define Maxsize 100
    #define OK 1
    #define OVERFLOW -2
    
    using namespace std;
    
    typedef char CElemType;
    
    typedef struct BiNode
    {
        CElemType data;
        struct BiNode*lchild,*rchild;
    } BiNode,*BiTree;
    
    typedef BiTree ElemType; ///存放二叉树地址的循环队列 吧
    
    typedef struct
    {
        ElemType *base;
        int front;
        int rear;
    } SeqQueue;
    
    int InitQueue(SeqQueue &Q)
    {
        Q.base=(ElemType *)malloc(Maxsize*sizeof(ElemType));
        if(!Q.base)
            exit(OVERFLOW);
        Q.front = Q.rear =0;
        return OK;
    }
    
    int EnQueue(SeqQueue &Q,ElemType e)
    {
        if((Q.rear+1)%Maxsize==Q.front)
        {
            cout<<"Queue Full"<<endl;
            return 0;
        }
        Q.rear = (Q.rear+1)%Maxsize;
        Q.base[Q.rear]=e;
        return 1;
    }
    
    int DeleQueue(SeqQueue &Q,ElemType &e)
    {
        if(Q.front==Q.rear)
        {
            cout<<"Queue Empty"<<endl;
            return 0;
        }
        Q.front=(Q.front+1)%Maxsize;
        e=Q.base[Q.front];
        return 1;
    }
    
    int Empty(SeqQueue Q)
    {
        if(Q.rear==Q.front)
            return 1;
        else return 0;
    }
    
    void CreateBiTree2(BiTree &t)  ///引用实现创建一棵二叉树
    {
        char ch;
        scanf("%c",&ch);
        if(ch==' ')
            t=NULL;
        else
        {
            t=(BiTree)malloc(sizeof(BiNode));
            t->data=ch;
            CreateBiTree2(t->lchild);
            CreateBiTree2(t->rchild);
        }
    }
    
    void Cengci(BiTree t)
    {
        BiTree p=t;
        SeqQueue Q;
        int flag=InitQueue(Q);
        EnQueue(Q,p);
        while(!Empty(Q))
        {
            DeleQueue(Q,p);
            cout<<p->data<<" ";
            if(p->lchild)
                EnQueue(Q,p->lchild);
            if(p->rchild)
                EnQueue(Q,p->rchild);
        }
    }
    
    int main()
    {
        BiTree T;
        cout<<"Please Input One BiTree :"<<endl;
        CreateBiTree2(T);
        cout<<"Cengci Order Output :"<<endl;
        Cengci(T);
        return 0;
    }