克己ovo 2021-10-13 18:05 采纳率: 90%
浏览 56
已结题

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


#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;
}
  • 写回答

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;
}
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题？

问题事件

  • 系统已结题 10月23日
  • 已采纳回答 10月15日
  • 创建了问题 10月13日

悬赏问题

  • ¥15 import arcpy出现importing _arcgisscripting 找不到相关程序
  • ¥15 onvif+openssl，vs2022编译openssl64
  • ¥15 iOS 自定义输入法-第三方输入法
  • ¥15 很想要一个很好的答案或提示
  • ¥15 扫描项目中发现AndroidOS.Agent、Android/SmsThief.LI!tr
  • ¥15 怀疑手机被监控，请问怎么解决和防止
  • ¥15 Qt下使用tcp获取数据的详细操作
  • ¥15 idea右下角设置编码是灰色的
  • ¥15 全志H618ROM新增分区
  • ¥15 在grasshopper里DrawViewportWires更改预览后，禁用电池仍然显示