xjh2527 2021-11-17 17:14 采纳率: 91.7%
浏览 13
已结题

二叉树的递归先序建立,非递归先序遍历,为什么遍历后总是丢失右子树


#include<stdio.h>
#include<stdlib.h>
#define stacksize 100
#define STACKINCREMENT 10 
typedef struct BiTNode//树的定义 
{
    int date;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef struct{
    BiTNode *base; 
    BiTNode *top; 
    int StackSize;   //当前已经分配的存储空间,以元素为单位 
}SqStack;

int InitStack(SqStack &S)//初始化 
{
    S.base=(BiTNode *)malloc(stacksize*sizeof(BiTNode));
    if(!S.base){
        return -2;
    }
    S.top = S.base;   
    S.StackSize=stacksize;  
    return 1;    
} 

int Push(SqStack &s,BiTNode &e)//入栈 
{
    BiTNode *p; 
    if(s.top-s.base == s.StackSize){
        p = (BiTNode *)realloc(s.base,(stacksize+STACKINCREMENT)*sizeof(BiTNode));
        if(!p){
            return -2;
        }
        s.base=p;  
        s.top = s.base + s.StackSize;
        s.StackSize+=STACKINCREMENT;
    }
    *(s.top)=e;
    s.top++;
    return 1;
}
 
BiTNode Pop(SqStack s,BiTNode *e)//出栈 
{
    if(s.top != s.base){
        s.top--;    //先将栈顶指针减 1 
        *e=*(s.top);
    }
    return *e;
}
 
int creatBiTNode(BiTree &bt)//先序创建二叉树 
{
    int ch;
    scanf("%d",&ch);
    if(ch==0)
        bt=NULL; 
    else{
        bt=(BiTNode*)malloc(sizeof(BiTNode));
        bt->date=ch;
        creatBiTNode(bt->lchild);
        creatBiTNode(bt->rchild);
    }
    return 0;
}

int preorder(BiTree bt)//顺序非递归访问二叉树 
{
    BiTNode *p;
    SqStack *st;
    InitStack(*st);
    p=bt;
    while(st->top!=st->base||p) 
    {
        while(p)
           {   
            printf("%d ",p->date);
            Push(*st,*p);
            p=p->lchild;
        }
        if(st->top!=st->base)
        {
            Pop(*st,p); 
            p=p->rchild;
        }
    }
    return 0;
}

int main()
{
    BiTNode *bt;
    creatBiTNode(bt);
    printf("先序序列为\n");
    preorder(bt); 
    return 0;
}
  • 写回答

0条回答 默认 最新

    报告相同问题?

    问题事件

    • 系统已结题 11月25日
    • 创建了问题 11月17日

    悬赏问题

    • ¥50 微信聊天记录备份到电脑提示成功了,但还是没同步到电脑微信
    • ¥15 python怎么在已有视频文件后添加新帧
    • ¥20 虚幻UE引擎如何让多个同一个蓝图的NPC执行一样的动画,
    • ¥15 fluent里模拟降膜反应的UDF编写
    • ¥15 MYSQL 多表拼接link
    • ¥15 关于某款2.13寸墨水屏的问题
    • ¥15 obsidian的中文层级自动编号
    • ¥15 同一个网口一个电脑连接有网,另一个电脑连接没网
    • ¥15 神经网络模型一直不能上GPU
    • ¥15 pyqt怎么把滑块和输入框相互绑定,求解决!