克己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 关于#极限编程#的问题,请各位专家解答!
  • ¥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词典!