兰秋葭月 2021-10-18 20:57 采纳率: 85.7%
浏览 635
已结题

编写按层次顺序遍历二叉树的算法 ;实验要求:以二叉链表作为存储结构

我基本是按王道数据结构书里的代码敲的,但是运行不了,还有两个警告,请求指点

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef char ElemType;
//二叉树 
typedef struct BSTNode{
    ElemType data;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
//队列节点 
typedef struct{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
//queue
typedef struct{
    LinkNode *front,*rear;
}LinkQueue;
//初始化队列 
void InitQueue(LinkQueue Q){
    Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}
//判空 
bool IsEmpty(LinkQueue Q){
    printf("\nisempty");
    if(Q.front==Q.rear)    return true;
    else
        return false;
}
//入队 
void EnQueue(LinkQueue Q,BSTree T){
    LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
    s->data=T->data;
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}
//出队 
bool DeQueue(LinkQueue Q,BSTree p){
    if(Q.front==Q.rear)    return false;
    LinkNode *t=Q.front->next;
    p->data=t->data;
    Q.front->next=t->next;
    if(Q.rear==t)
        Q.rear=Q.front;
    free(t);
    return true;
}
//按先序遍历的顺序创建二叉树 
BSTree Create(){
    BSTree T=NULL;
    ElemType ch;
    scanf("%c",&ch);
    if(ch=='#')    T=NULL;
    else{
        T=(BSTree)malloc(sizeof(BSTNode));
        T->data=ch;
        T->lchild=Create();
        T->rchild=Create();
    }
    return T;
}
//层次遍历 
void LevelOrder(BSTree T,LinkQueue Q){
    InitQueue(Q);
    BSTree p;
    EnQueue(Q,T);//根节点入队 
    while(!IsEmpty(Q)){
        DeQueue(Q,p);//队头节点出队 
        printf("%c",p->data);//访问出队节点 
        if(p->lchild!=NULL)
            EnQueue(Q,p->lchild);
        if(p->rchild!=NULL)
            EnQueue(Q,p->rchild);
    }
}
int main(){
    BSTree T;
    LinkQueue Q;
    T=Create();
    LevelOrder(T,Q);
    return 0;
}

img

  • 写回答

1条回答 默认 最新

  • qzjhjxj 2021-10-19 00:31
    关注

    修改如下,供参考:

    #include<stdio.h>
    #include<stdlib.h>
    //#include<stdbool.h>
    //二叉树
    typedef struct BSTNode{
        char data;  //ElemType data;
        struct BSTNode *lchild,*rchild;
    }BSTNode,*BSTree;
    
    typedef BSTree ElemType;//修改
    
    //队列节点
    typedef struct LinkNode{//修改
        ElemType data;      //修改
        struct LinkNode *next;
    }LinkNode;
    //queue
    typedef struct{
        LinkNode *front,*rear;
    }LinkQueue;
    //初始化队列 
    void InitQueue(LinkQueue & Q){
        Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode));
        Q.front->next=NULL;
    }
    //判空 
    bool IsEmpty(LinkQueue Q){
                              //printf("\nisempty");
        if(Q.front==Q.rear)
            return true;
        else
            return false;
    }
    //入队
    void EnQueue(LinkQueue & Q,BSTree T){ //修改 &Q  引用
        LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
        s->data = T;  //s->data=T->data;
        s->next=NULL;
        Q.rear->next=s;
        Q.rear=s;
    }
    //出队 
    bool DeQueue(LinkQueue & Q,BSTree & p){//修改 &Q 引用
        if(Q.front==Q.rear)return false;
        LinkNode *t=Q.front->next;
        p = t->data;
        Q.front->next=t->next;
        if(Q.rear==t)
           Q.rear=Q.front;
        free(t);
        return true;
    }
    //按先序遍历的顺序创建二叉树 
    BSTree Create()
    {
        BSTree T=NULL;
        char ch;       //ElemType ch;
        scanf("%c",&ch);
        getchar();
        if(ch=='#')    T=NULL;
        else{
            T=(BSTree)malloc(sizeof(BSTNode));
            T->data=ch;
            T->lchild=Create();
            T->rchild=Create();
        }
        return T;
    }
    //层次遍历 
    void LevelOrder(BSTree T,LinkQueue Q){
        InitQueue(Q);
        BSTree p;
        EnQueue(Q,T);//根节点入队 
        while(!IsEmpty(Q)){
            DeQueue(Q,p);//队头节点出队
            printf("%c ",p->data);//访问出队节点
            if(p->lchild!=NULL)
                EnQueue(Q,p->lchild);
            if(p->rchild!=NULL)
                EnQueue(Q,p->rchild);
        }
    }
    int main()
    {
        BSTree T;
        LinkQueue Q;
        T=Create();
        LevelOrder(T,Q);
    
        return 0;
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 10月27日
  • 已采纳回答 10月19日
  • 创建了问题 10月18日

悬赏问题

  • ¥60 最新ukb数据下载方法
  • ¥15 关于#python#的问题:您好可以加您一下联系方式吗,在复现的时候确实有点问题难以解决
  • ¥15 联想电脑重装系统时无法发现硬盘
  • ¥15 MATLAB与UR10e实体机械臂建立通讯
  • ¥15 c++题需要快一点不用opencv
  • ¥15 关于#java#的问题:想要咨询Flowable流程引擎框架的问题
  • ¥15 vscode里面怎么用plaformio强调串口啊
  • ¥20 针对计算后数据做一致性检验可以用Bland Altman法吗
  • ¥15 win32如何自绘编辑框的背景图片(语言-c++|操作系统-windows)
  • ¥15 微信夜间被转走了1w对,当天手机剪切板里就出现了这个乱码,有铁子可以看看是啥吗可以