数据结构ＢＦＳ层次遍历二叉树【C语言版本】

Myth丶恋晨 2022-06-12 11:26 125阅读 0赞

//案例输入（其中的“\#”表示空，并且输入过程中不要加回车)

输入序列ABC\#\#DE\#G\#\#F\#\#\#

输入序列ABD\#\#E\#\#CF\#G\#\#\#

输入序列ABD\#\#\#C\#\#

#include <stdio.h>	//测试OK，可以运行 
    #include <stdlib.h>
    
    typedef struct BiTNode      //定义树的结构
    {
        char data;
        struct BiTNode *Lchild;
        struct BiTNode *Rchild;
    } BiTNode,*BiTree;
    
    BiTree Create(BiTree T)   //建立二叉树（先序）               //改的这个地方
    {
        char ch;
        ch=getchar();
        if(ch=='#')
            T = NULL;
        else
        {
            if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
                printf("Error!");
            T->data=ch;
            T->Lchild = Create(T->Lchild);
            T->Rchild = Create(T->Rchild);
        }
        return T;
    }
    typedef BiTree QueueElementType ;
    
    typedef struct Node{
        QueueElementType data;
        Node *next;
    }LinkQueueNode;
    
    typedef struct {
        LinkQueueNode *Front;
        LinkQueueNode *Rear;
    }LinkQueue;
    
    //链 队列 初始化
    int init_Queue(LinkQueue *Q)
    {
        Q->Front = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
        if(Q->Front !=NULL){
            Q->Rear = Q->Front;
            Q->Front->next = NULL;
            return 1;
        }
        else
            return 0;  //溢出
    }
    //链 队列 入队
    int EnterQueue(LinkQueue *Q,QueueElementType x)
    {
        LinkQueueNode *NewNode;
        NewNode = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
        if(NewNode !=NULL){
            NewNode->data = x;
            NewNode->next = NULL;
            Q->Rear->next =NewNode;
            Q->Rear =NewNode;
            return 1;
        }
        else
            return 0;
    }
    //链队列 出队
    int Delete_Queue(LinkQueue *Q,QueueElementType *x)
    {
        if(Q->Front == Q->Rear){
            return 0;
        }
        LinkQueueNode *p;
    
        p = Q->Front->next;
        Q->Front->next = p->next;
        if(Q->Rear == p){
            Q->Rear = Q->Front;
        }
        *x = p->data;
        free(p);
        return 1;
    }
    //判断 队列是否为空
    int Is_empty(LinkQueue *Q)
    {
        if(Q->Front == Q->Rear)
            return 1;
        return 0;
    }
    //层次 遍历树 （OK） 
    void BFS_Queue(BiTree T)
    {
        if(T == NULL)
            return;
        LinkQueue LQ;
        init_Queue(&LQ);
    
        EnterQueue(&LQ,T);
    
        BiTree temp;
        while( !Is_empty(&LQ) )
        {
            if( Delete_Queue(&LQ,&temp) )
                printf("%c ",temp->data);
            if(temp->Lchild) EnterQueue(&LQ,temp->Lchild); //这个位置原来都是  T->Lchild 怪不得呢 
            if(temp->Rchild) EnterQueue(&LQ,temp->Rchild);
        }
    	printf("\n");
    }
    int main()
    {
    　　printf("下面用先序遍历创建二叉树：");
    　　printf("请输入树 的内容，形式如ABD##E##CF#G###('#'代表空): \n\n"); 
        BiTree T=Create(T); //创建树
        printf("\n\n下面输出 层次遍历的结果 （每一层的结点都是从左向右的顺序输出）:\n");
        BFS_Queue(T); //层次 遍历 树
        return 0;
    }