有没有看看层序遍历二叉树的时候为什么会异常输出


#include<stdio.h>
#include<stdlib.h>
#define ElemType TreeNode 
//定义树的结点
typedef struct node{ //树的结点
    int data;    //数据域 
    struct node* left;  //左儿子 
    struct node* right; //右儿子 
} Node,*TreeNode;
//利用树的结点类型指针指向根结点
typedef struct { 
     TreeNode root;        //树根
}*TreeFirstNode,FirstNode; 

//定义栈的存储类型 //新的数据类型 
typedef struct Nodestack *ListStack;
struct Nodestack{
    TreeNode p;           //存树的结点指针 
    struct Nodestack *next; //下一个栈元素指针 
}Stack;

//树的中序遍历
void Show(TreeNode tree)
{
    TreeNode temp = tree;
    if ( temp!= NULL)     //工作指针 
    {
        Show(temp->left);
        printf("%d ",temp->data);
        Show(temp->right);
    }
}

//树的先序遍历 
void Show1(TreeNode treeroot)
{
    TreeNode temp = treeroot;     //工作指针 
    if (temp!= NULL)
    {
        printf("%d ",temp->data);
        Show1(temp->left);
        Show1(temp->right);
    }
}
//树的后序遍历 
void Show2(TreeNode treeroot)
{
    TreeNode temp = treeroot;     //工作指针 
    if ( temp!= NULL)
    {
        Show2(temp->left);
        Show2(temp->right);
        printf("%d ",temp->data);
    }
}

//非递归中序遍历 

//栈的初始化 
void InitStack(ListStack &S){
    S = (ListStack)malloc(sizeof(Stack));
    S->next = NULL;
    //printf("初始化成功！\n");
}

//判断是否为空栈
bool ListStackEmpty(ListStack S){
    if(S->next == NULL)
    return true;
    return false;
} 

//将数据压入栈内 
/* 用头插法更合适 出栈的时候只需弹出第一个节点即可*/
bool Push(ListStack &S ,ElemType data){
    ListStack r;
    ListStack t;
    t = S;                                    //防止s指向发生改变 
    r = (ListStack)malloc(sizeof(Stack));
    r->p= data;
    r->next = t->next;
    t->next = r;
    //printf("入栈成功\n");
    return true;
}

//将数据弹出栈
bool Pop(ListStack &S,ElemType& t){
    if(S->next==NULL){
        printf("栈空\n");
        return false;
    }else{
    ListStack r;
    r=S->next;
    t=r->p;
    S->next=r->next;
    free(r);
    //printf("弹出成功/n"); 
    } 
    return true;
} 

//读取栈顶元素
bool GetTop(ListStack s,ElemType &x){
    if(s->next==NULL){
        return false;
    }
    s=s->next;
    x=s->p;
    return true;
}

//树的非递归中序遍历 
void InOrder2(TreeFirstNode tree,ListStack S){
    TreeNode p=tree->root;
    InitStack(S);
    while(p||!ListStackEmpty(S)){    //栈不空的时候 是FALSE 
        if(p){
            Push(S,p);
            p=p->left;
        }
        else{
            printf("%d ",S->next->p->data);
            Pop(S,p);
            p=p->right;
        }
    }
}

//树的非递归先序遍历
void InOrder1(TreeFirstNode tree,ListStack L){
    TreeNode p=tree->root;
    InitStack(L);
    while(p||!ListStackEmpty(L)){    //栈不空的时候 是FALSE 
        if(p){
            printf("%d ",p->data);
            Push(L,p);
            p=p->left;
        }
        else{
            Pop(L,p);
            p=p->right;
        }
    }
}

//树的非递归后序遍历
void InOrder3(TreeFirstNode tree,ListStack L){
    TreeNode p=tree->root;
    TreeNode r = NULL;//辅助指针 判断是否已被访问 
    InitStack(L);
    while(p||!ListStackEmpty(L)){    //栈不空的时候 是FALSE 
        if(p){
            Push(L,p);
            p=p->left;
        }
        else{
            GetTop(L,p);
            if(p->right && p->right!=r){
                p=p->right; 
            }
            else{
                Pop(L,p);
                printf("%d ",p->data);
                r=p;
                p=NULL;
            } 
        } 
    }
} 

//创建根 
void Init( TreeFirstNode &tree, int value)//创建树  
{
    TreeNode node=(TreeNode)malloc(sizeof(Node));//创建一个节点
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    tree->root = node;//创建根结点   
    printf("初始化成功\n");
}

//插入结点（二叉排序树） 
void Insert(TreeFirstNode &tree,int value){ 
    TreeNode temp = tree->root;//工作从树根开始
    TreeNode node=(TreeNode)malloc(sizeof(Node));//创建一个节点
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    while (temp!= NULL)
    {
        if (value < temp->data)       //小于就进左子树 
        {
            if (temp->left == NULL)
            {
                temp->left = node;
                printf("插入成功\n"); 
                return;
            }
            else
            {                   //不空继续判断
                temp = temp->left;
            }
        }
        else{                      //否则进右子树 

            if(temp->right == NULL)
            {
                temp->right = node;
                printf("插入成功\n"); 
                return;
            }
            else{                  //不空继续判断
                temp = temp->right;
            }
        }
    }
}

 
//定义队列储存类型
typedef struct qnode{
    TreeNode ptrl;
    struct qnode *next;    
}LinkNode;
typedef struct{
    LinkNode *front,*rear;
}LinkQueue; 


//初始化队列
bool InitQueue(LinkQueue &q){            //传引用更加方便 
    q.front=q.rear = (LinkNode*)malloc(sizeof(struct node));
    q.front->next=NULL;//是首结点置空 
    //printf("初始化成功！\n"); 
    return true;
}

//判断队列是否为空
bool QueueEmpty(LinkQueue q){
    if(q.front==q.rear)
    return true;
    return false; 
} 


//入队操作

bool EnterQueue(LinkQueue &q,TreeNode x){
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->ptrl = x;
    s->next = NULL;
    q.rear->next = s;
    q.rear = s;
    return true;
} 


//出队操作
bool OutQueue(LinkQueue &q,ElemType &j){   //j用来保存出队数据 引用传递 
    if(q.front==q.rear)
    return false;
    LinkNode *p = q.front->next;
    j = p->ptrl;
    q.front->next = p->next;
    if(q.rear==p)
    q.front=q.rear;
    free(p); 
    return true; 

} 

//层遍历二叉树

void LevelOrder(TreeNode TreeRoot,LinkQueue &q){
    InitQueue(q);
    TreeNode temp = TreeRoot;
    EnterQueue(q,TreeRoot);
    while(!QueueEmpty(q)){
        OutQueue(q,temp);
        printf("%d ",temp->data);
        if(temp->left!=NULL){
            EnterQueue(q,temp->left);
        }
        if(temp->right!=NULL){
            EnterQueue(q,temp->right);
        }
    }
    
}
int main(){
    int value;
    int N,i; 
    ElemType t;
    ListStack S,L;
    LinkQueue q;
    printf("请输入根结点的值:\n");
    scanf("%d",&value);
    TreeFirstNode tree=(TreeFirstNode)malloc(sizeof(FirstNode));
    Init(tree,value);
    printf("请输入要插入树的数据个数（N）:"); 
    scanf("%d",&N);
    for(i=1;i<N+1;i++){
        printf("请输入第%d个数:",i);
        scanf("%d",&value);
        Insert(tree,value); 
    }
    printf("递归中序遍历二叉排序树:\n");
    Show(tree->root);
    printf("\n");
    printf("非递归中序遍历二叉排序树:\n");
    InOrder2(tree,S);
    printf("\n");
    printf("递归先序遍历二叉排序树:\n");
    Show1(tree->root);
    printf("\n");
    printf("非递归先序遍历二叉排序树:\n"); 
    InOrder1(tree,S); 
    printf("\n");
    printf("递归后序遍历二叉排序树:\n");
    Show2(tree->root);
    printf("\n");
    printf("非递归后序遍历二叉排序树:\n");
    InOrder3(tree,S);
    printf("\n");
    printf("层遍历二叉树：\n");
    LevelOrder(tree->root,q);
    return 0;
}

写回答
好问题 0 提建议
追加酬金
关注问题
分享
邀请回答
编辑收藏删除
收藏举报

1条回答默认最新

qzjhjxj 2021-10-14 01:35

关注

修改见注释处，供参考：

#include<stdio.h>
#include<stdlib.h>
#define ElemType TreeNode
//定义树的结点
typedef struct node{ //树的结点
    int data;    //数据域
    struct node* left;  //左儿子
    struct node* right; //右儿子
} Node,*TreeNode;
//利用树的结点类型指针指向根结点
typedef struct {
     TreeNode root;        //树根
}*TreeFirstNode,FirstNode;
//定义栈的存储类型 //新的数据类型
typedef struct Nodestack *ListStack;
struct Nodestack{
    TreeNode p;           //存树的结点指针
    struct Nodestack *next; //下一个栈元素指针
}Stack;
//树的中序遍历
void Show(TreeNode tree)
{
    TreeNode temp = tree;
    if ( temp!= NULL)     //工作指针
    {
        Show(temp->left);
        printf("%d ",temp->data);
        Show(temp->right);
    }
}
//树的先序遍历
void Show1(TreeNode treeroot)
{
    TreeNode temp = treeroot;     //工作指针 
    if (temp!= NULL)
    {
        printf("%d ",temp->data);
        Show1(temp->left);
        Show1(temp->right);
    }
}
//树的后序遍历 
void Show2(TreeNode treeroot)
{
    TreeNode temp = treeroot;     //工作指针 
    if ( temp!= NULL)
    {
        Show2(temp->left);
        Show2(temp->right);
        printf("%d ",temp->data);
    }
}
//非递归中序遍历 
//栈的初始化 
void InitStack(ListStack &S){
    S = (ListStack)malloc(sizeof(Stack));
    S->next = NULL;
    //printf("初始化成功！\n");
}
//判断是否为空栈
bool ListStackEmpty(ListStack S){
    if(S->next == NULL)
    return true;
    return false;
} 
//将数据压入栈内
//用头插法更合适 出栈的时候只需弹出第一个节点即可
bool Push(ListStack &S ,ElemType data){
    ListStack r;
    ListStack t;
    t = S;                                    //防止s指向发生改变 
    r = (ListStack)malloc(sizeof(Stack));
    r->p= data;
    r->next = t->next;
    t->next = r;
    //printf("入栈成功\n");
    return true;
}
//将数据弹出栈
bool Pop(ListStack &S,ElemType& t){
    if(S->next==NULL){
        printf("栈空\n");
        return false;
    }else{
    ListStack r;
    r=S->next;
    t=r->p;
    S->next=r->next;
    free(r);
    //printf("弹出成功/n"); 
    } 
    return true;
} 
//读取栈顶元素
bool GetTop(ListStack s,ElemType &x){
    if(s->next==NULL){
        return false;
    }
    s=s->next;
    x=s->p;
    return true;
}
//树的非递归中序遍历
void InOrder2(TreeFirstNode tree,ListStack S){
    TreeNode p=tree->root;
    InitStack(S);
    while(p||!ListStackEmpty(S)){    //栈不空的时候 是FALSE 
        if(p){
            Push(S,p);
            p=p->left;
        }
        else{
            //printf("%d ",S->next->p->data);
            Pop(S,p);
            printf("%d ",p->data);
            p=p->right;
        }
    }
}
//树的非递归先序遍历
void InOrder1(TreeFirstNode tree,ListStack L){
    TreeNode p=tree->root;
    InitStack(L);
    while(p||!ListStackEmpty(L)){    //栈不空的时候 是FALSE 
        if(p){
            printf("%d ",p->data);
            Push(L,p);
            p=p->left;
        }
        else{
            Pop(L,p);
            p=p->right;
        }
    }
}
//树的非递归后序遍历
void InOrder3(TreeFirstNode tree,ListStack L){
    TreeNode p=tree->root;
    TreeNode r = NULL;//辅助指针 判断是否已被访问
    InitStack(L);
    while(p||!ListStackEmpty(L)){    //栈不空的时候 是FALSE 
        if(p){
            Push(L,p);
            p=p->left;
        }
        else{
            GetTop(L,p);
            if(p->right && p->right!=r){
                p=p->right; 
            }
            else{
                Pop(L,p);
                printf("%d ",p->data);
                r=p;
                p=NULL;
            } 
        }
    }
} 
//创建根 
void Init( TreeFirstNode &tree, int value)//创建树  
{
    TreeNode node=(TreeNode)malloc(sizeof(Node));//创建一个节点
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    tree->root = node;//创建根结点   
    printf("初始化成功\n");
}
//插入结点（二叉排序树） 
void Insert(TreeFirstNode &tree,int value){ 
    TreeNode temp = tree->root;//工作从树根开始
    TreeNode node=(TreeNode)malloc(sizeof(Node));//创建一个节点
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    while (temp!= NULL)
    {
        if (value < temp->data)       //小于就进左子树 
        {
            if (temp->left == NULL)
            {
                temp->left = node;
                printf("插入成功\n");
                return;
            }
            else
            {                   //不空继续判断
                temp = temp->left;
            }
        }
        else{                      //否则进右子树 
            if(temp->right == NULL)
            {
                temp->right = node;
                printf("插入成功\n"); 
                return;
            }
            else{                  //不空继续判断
                temp = temp->right;
            }
        }
    }
}
 
//定义队列储存类型
typedef struct qnode{
    TreeNode ptrl;
    struct qnode *next;    
}LinkNode;
typedef struct{
    LinkNode *front,*rear;
}LinkQueue;

//初始化队列
bool InitQueue(LinkQueue &q){            //传引用更加方便
    q.front = (LinkNode*)malloc(sizeof(struct node)); //修改
    q.front->next = NULL;//是首结点置空
    q.rear = q.front;                      //修改
    //printf("初始化成功！\n");
    return true;
}
//判断队列是否为空
bool QueueEmpty(LinkQueue q){
    if(q.front==q.rear)
        return true;
    return false;
} 
 
//入队操作
bool EnterQueue(LinkQueue &q,TreeNode x){
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->ptrl = x;
    s->next = NULL;
    q.rear->next = s;
    q.rear = s;
    return true;
} 
 
//出队操作
bool OutQueue(LinkQueue &q,ElemType &j){//j用来保存出队数据 引用传递
    if(q.front == q.rear)
       return false;
    LinkNode *p = q.front;//修改 *p = q.front->next;
    q.front = p->next;   //修改   q.front->next = p->next;
    j = q.front->ptrl;   //修改  j = p->ptrl;
                         //if(q.rear==p)
                         //q.front=q.rear;
    free(p);
    return true; 
} 
//层遍历二叉树
void LevelOrder(TreeNode TreeRoot,LinkQueue &q){
    InitQueue(q);
    TreeNode temp; //= TreeRoot;  修改
    EnterQueue(q,TreeRoot);
    while(!QueueEmpty(q)){
        OutQueue(q,temp);
        printf("%d ",temp->data);
        if(temp->left!=NULL){
           EnterQueue(q,temp->left);
        }
        if(temp->right!=NULL){
           EnterQueue(q,temp->right);
       }
    }
}
int main(){
    int value;
    int N,i;
    ElemType t;
    ListStack S,L;
    LinkQueue q;
    printf("请输入根结点的值:\n");
    scanf("%d",&value);
    TreeFirstNode tree=(TreeFirstNode)malloc(sizeof(FirstNode));
    Init(tree,value);
    printf("请输入要插入树的数据个数（N）:");
    scanf("%d",&N);
    for(i=1;i<N+1;i++){
        printf("请输入第%d个数:",i);
        scanf("%d",&value);
        Insert(tree,value); 
    }
    printf("递归中序遍历二叉排序树:\n");
    Show(tree->root);
    printf("\n");

    printf("非递归中序遍历二叉排序树:\n");
    InOrder2(tree,S);
    printf("\n");

    printf("递归先序遍历二叉排序树:\n");
    Show1(tree->root);
    printf("\n");

    printf("非递归先序遍历二叉排序树:\n"); 
    InOrder1(tree,S); 
    printf("\n");

    printf("递归后序遍历二叉排序树:\n");
    Show2(tree->root);
    printf("\n");

    printf("非递归后序遍历二叉排序树:\n");
    InOrder3(tree,S);
    printf("\n");

    printf("层遍历二叉树：\n");
    LevelOrder(tree->root,q);
    return 0;
}

本回答被题主选为最佳回答 , 对您是否有帮助呢?

报告相同问题？

关注问题

二叉树层序遍历不知道为什么出错数据结构
2022-09-02 14:39

回答 3 已采纳麻烦描述得更详细些，比如具体的报错信息。逻辑上没看出啥问题，可能是队列q溢出（树的大小超过1000），也可能是输出格式不符合要求（第一个元素输出前的空格）。
这种扩展先序遍历为什么不能建立二叉树，没有输出结果 c++
2021-11-16 16:09

回答 1 已采纳 create(bitree *) 改成create(Bitree* & )
请问一下各位我的这个二叉树遍历方法为啥输出的会是乱码 java 数据结构有问必答链表
2022-01-02 23:32

回答 1 已采纳 Node 类重写toString方法即可。
js代码-二叉树的层序遍历
2021-07-16 15:17

在JavaScript编程中，二叉树是一种非常重要的数据结构，它由节点组成，每个节点最多有两个子节点，通常称为左子节点和右子节点。层序遍历，又称广度优先搜索（BFS），是二叉树遍历的一种方法，按照从上到下、从左到...
为什么要遍历二叉树?遍历二叉树的算法一般能应用到哪里? java 算法
2016-04-09 02:54

回答 7 已采纳学习二叉树重点就是遍历算法，我们主要是要把遍历算法学会。随后可以应用到网络爬虫这些。
递归遍历二叉树，然后先序中序后序输出，可以看看我的代码问题出在哪吗 c语言数据结构有问必答
2022-04-21 11:42

回答 3 已采纳 CreatBiTree函数中每次都要用 T = (BinTree)malloc(sizeof(BiTNode)); 创建新的子节点你题目的解答代码如下： void CreatBiTree(Bi
进行二叉树建立遍历，但输出为空 c语言
2022-05-08 18:25

回答 1 已采纳你用的是devc++吧，如果是就把他的运行位数改一下，然后运行就可以了
算法编程-二叉树的层序遍历
2018-01-12 13:19

草根caogen的博客 层序遍历的顺序为：队列不为空进入循环 { 首元素出队，输出该首元素左孩子不为空，则左孩子入队该首元素右孩子不为空，则右孩子入队 } 代码未曾验证，请看大概思路： //定义 struct BiTree { ...
二叉链表建立二叉树 为什么不能先序遍历输出值呢 c语言数据结构有问必答
2021-05-24 13:15

回答 2 已采纳没事，一些小细节问题，给你改好了，看注释： #include<stdio.h> #include<stdlib.h> typedef struct bitnode {
二叉树理解不了怎么办？有没有什么好的教材可以看看？数据结构
2021-12-16 06:08

回答 1 已采纳 二叉树： 二叉树 —— 用递归来描述数据结构 - 知乎前言这篇文章的主要目的是讲解二叉树的一些基础概念，以及和二叉树相关的一些经典遍历算
如何用层序遍历一个普通的二叉树，并把它以完全二叉树的形式存入数组内呢？为空的地方存入null这种思路 java 数据结构算法
2021-11-21 22:41

回答 2 已采纳 import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Que
二叉树的遍历|前序、中序、后序、层序遍历
2021-08-15 20:46

有出路Coding的博客文章目录6.8　遍历二叉树6.8.1　二叉树遍历原理6.8.2　二叉树遍历方法1．前序遍历2．中序遍历3．后序遍历4．层序遍历6.8.3　前序遍历算法6.8.4　中序遍历算法6.8.5　后序遍历算法6.8.6　推导遍历结果 6.8　遍历...
二叉树的构建以及前中后序、层序遍历简单示例
2022-06-08 12:05

本示例将深入探讨二叉树的构建方法以及四种主要的遍历方式：前序遍历、中序遍历、后序遍历和层序遍历。首先，我们来看`BinaryNode.java`，这个文件通常包含二叉树节点的定义。一个简单的二叉树节点类可能如下所示...
二叉树：层序遍历登场！
2020-09-29 20:31

代码随想录的博客思路 层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。 C++代码 class Solution { public: vector rightSideView(TreeNode* root) { queue que; if...
LeetCode二叉树系列——102.二叉树的层序遍历
2022-07-30 08:58

十八岁讨厌Java的博客刚刚我们说过了二叉树有两种存储方式顺序存储，和链式存储，顺序存储就是用数组来存，这个定义没啥可说的，我们来看看链式存储的二叉树节点的定义方式。intval;};大家会发现二叉树的定义和链表是差不多的，相对于...
没有解决我的问题, 去提问

问题事件

关注

码龄粉丝数原力等级 --

被采纳

被点赞

采纳率
系统已结题 10月23日
关注

码龄粉丝数原力等级 --

被采纳

被点赞

采纳率
已采纳回答 10月15日
关注

码龄粉丝数原力等级 --

被采纳

被点赞

采纳率
创建了问题 10月13日

悬赏问题

¥15 关于#极限编程#的问题，请各位专家解答！
¥20 win11账户锁定时间设为0无法登录
¥45 C#学生成绩管理系统
¥15 VB.NET2022如何生成发布成exe文件
¥30 matlab appdesigner私有函数嵌套整合
¥15 vb6.0使用jmail接收smtp邮件并另存附件到D盘
¥30 vb net 使用 sendMessage 如何输入鼠标坐标
¥15 关于freesurfer使用freeview可视化的问题
¥100 谁能在荣耀自带系统MagicOS版本下，隐藏手机桌面图标？
¥15 求SC-LIWC词典！

有没有看看层序遍历二叉树的时候为什么会异常输出

1条回答 默认 最新

问题事件

悬赏问题

1条回答默认最新