m0_61730560 2022-08-16 13:27 采纳率: 100%
浏览 101
已结题

二叉树的中序非递归遍历


#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef char TElemType;
typedef struct BiNode{
    TElemType date;
    struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
typedef struct{
    TElemType *base,*top;
    int StackSize;
}Stack;
InitTree(BiTree *t)
{
    *t=NULL;
}
InitStack(Stack *s)
{
    s->base=(TElemType*)malloc(sizeof(TElemType)*MAXSIZE);
    if(!s->base) exit(-1);
    s->top=s->base;
    s->StackSize=MAXSIZE; 
}
int Creat(BiTree *t)
{
    TElemType ch;
    scanf("%c",&ch);
    if(ch!='#'){
        (*t)=(BiNode*)malloc(sizeof(BiNode));
        (*t)->date=ch;
        Creat(&(*t)->lchild);
        Creat(&(*t)->rchild);
    }
    else *t=NULL;
}
int visit(BiTree t)//遍历 
{
    if(t!=NULL) printf("%c ",t->date);
    return 0;
}
int Push(Stack **s,BiNode *p)
{
    if((*s)->top-(*s)->base==(*s)->StackSize){
        printf("栈满,入栈失败!");    
        return 0;
    }
    *(*s)->top++=p;
}
int Pop(Stack **s)
{
    if((*s)->top-(*s)->base==0){
        printf("栈空,出栈失败!");
        return 0;
    }
    return *(*s)->top--;
}
int InTraverse(BiTree t,Stack *s)
{
    while(s->top-s->base!=0&&t!=NULL)
        if(t!=NULL){
            Push(&(*s),t);
            t=t->lchild;
        }
        else{
            t=Pop(&(*s));
            visit(t);
            t=t->rchild;
        }
} 
int main()
{
    BiTree T;
    Stack S;
    InitTree(&T);
    InitStack(&S);
    Creat(&T);
    printf("\n中序遍历的非递归算法:");
    InTraverse(T,&S);
}
  • 写回答

2条回答 默认 最新

  • 快乐鹦鹉 2022-08-16 19:57
    关注

    改好了,主要问题还是在push函数,不能将top指向树节点,因为堆栈有自己的内存空间,只能进行内容复制
    其它也有不少问题

    #include<stdio.h>
    #include<stdlib.h>
    #define MAXSIZE 20
    typedef char TElemType;
    typedef struct BiNode{
        TElemType date;
        struct BiNode *lchild,*rchild;
    }BiNode,*BiTree;
    typedef struct{
        BiNode *base,*top;
        int StackSize;
    }Stack;
    void InitTree(BiTree *t)
    {
        *t=NULL;
    }
    void InitStack(Stack *s)
    {
        s->base=(BiNode*)malloc(sizeof(BiNode)*MAXSIZE);
        if(!s->base) exit(-1);
        s->top=s->base;
        s->StackSize=MAXSIZE; 
    }
    int Creat(BiTree *t)
    {
        TElemType ch;
        scanf("%c",&ch);
        if(ch!='#'){
            (*t)=(BiNode*)malloc(sizeof(BiNode));
            (*t)->lchild  = NULL;
            (*t)->rchild  = NULL;
            (*t)->date=ch;
            Creat(&(*t)->lchild);
            Creat(&(*t)->rchild);
        }
        else *t=NULL;
        return 0;
    }
    int visit(BiTree t)//遍历 
    {
        if(t!=NULL) printf("%c ",t->date);
        return 0;
    }
    int Push(Stack **s,BiNode *p)
    {
        if((*s)->top-(*s)->base==(*s)->StackSize){
            printf("栈满,入栈失败!");    
            return 0;
        }
        (*s)->top++;
        (*s)->top->date = p->date;
        (*s)->top->lchild = p->lchild;
        (*s)->top->rchild = p->rchild;
        return 1;
    }
    BiNode* Pop(Stack **s)
    {
        if((*s)->top-(*s)->base==0){
            printf("栈空,出栈失败!");
            return 0;
        }
        BiNode * p= (*s)->top;
        (*s)->top--;
        return p;
    }
    int InTraverse(BiTree t,Stack *s)
    {
        while((s->top-s->base!=0) || t!=NULL)
        {
            if(t!=NULL){
                Push(&s,t);
                t=t->lchild;
            }
            else{
                t=Pop(&s);
                visit(t);
                t=t->rchild;
            }
        }
        return 1;
    } 
    int main()
    {
        BiTree T;
        Stack S;
        InitTree(&T);
        InitStack(&S);
        Creat(&T);
        printf("\n中序遍历的非递归算法:");
        InTraverse(T,&S);
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
    1人已打赏
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 8月24日
  • 已采纳回答 8月16日
  • 修改了问题 8月16日
  • 修改了问题 8月16日
  • 展开全部

悬赏问题

  • ¥20 用泊松逆高斯分布拟合已知数据
  • ¥15 web课程,怎么做啊😭没好好听课 根本不知道怎么下手
  • ¥15 做一个关于单片机的比较难的代码,然后搞一个PPT进行解释
  • ¥15 python提取.csv文件中的链接会经常出现爬取失败
  • ¥15 数据结构中的数组地址问题
  • ¥15 maya的mel里,怎样先选择模型A,然后利用mel脚本自动选择有相同名字的模型B呢。
  • ¥15 Python题,根本不会啊
  • ¥15 会会信号与系统和python的来
  • ¥15 关于#python#的问题
  • ¥20 oracle RAC 怎么配置啊,配置