cg_Amaz1ng
cg_Amaz1ng
采纳率60%
2015-10-08 04:41 阅读 2.1k
已采纳

C语言二叉树非递归遍历问题

#include"stdio.h"
#include"stdlib.h"

#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef int Status;
typedef struct LNode{
BiTree data;
struct LNode *next;
}LNode;
typedef struct{
LNode *top;
}LStack;

int main(){
Status CreateBiTree(BiTree &T);
Status Pop(LStack &S);
Status Init_Stack(LStack &S);
Status Push(LStack &S,BiTree T);
Status StackEmpty(LStack S);
Status PreOrderTraverse(BiTree T);
void visit(TElemType data);

BiTree T;
printf("创建树中...");
if(CreateBiTree(T))
    printf("创建成功\n");
PreOrderTraverse(T);
return 0;

}

Status CreateBiTree(BiTree &T){
TElemType ch;
scanf("%c",&ch);
if(ch==' ')
T=NULL;
else{
T=(BiTNode *)malloc(sizeof(BiTNode));
if(!T)
exit(OVERFLOW);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}

Status Init_Stack(LStack &S){
LNode *p;
p=(LNode *)malloc(sizeof(LNode));
if(!p)
exit(OVERFLOW);
p->next=NULL;
S.top=p;
return OK;
}

Status Push(LStack &S,BiTree T){
LNode *p;
p=(LNode *)malloc(sizeof(LNode));
if(!p)
exit(OVERFLOW);
S.top->data = T;
p->next = S.top;
S.top = p;
return OK;
}

Status StackEmpty(LStack S){
if(S.top==NULL)
return 1;
else
return 0;
}

void visit(TElemType data){
printf("%c\n",data);
}

BiTree Pop(LStack &S){
BiTree tran;
LNode *t;
tran=S.top->data;
t=S.top;
S.top=S.top->next;
free(t);
return tran;
}

Status PreOrderTraverse(BiTree T){
LStack S;
Init_Stack(S);
BiTree p;
p=T;
while(p||!(StackEmpty(S))){
if(p){
Push(S,p);
p=p->lchild;
}
else{
p=Pop(S);
visit(p->data);
p=p->rchild;
}
}
return OK;
}

//源代码如上,程序运行,我输入ABC DE G F

建立二叉树那一段可以运行,到了二叉树遍历的时候程序无法运行自动关闭,麻烦各位了!

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

1条回答 默认 最新

  • 已采纳
    cg_Amaz1ng cg_Amaz1ng 2015-10-08 08:02

    #include"stdio.h"
    #include"stdlib.h"
    #include"string.h"

    #define OK 1
    #define ERROR 0
    #define OVERFLOW -1
    typedef char TElemType;
    typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;

    typedef int Status;
    typedef struct LNode{
    BiTree data;
    struct LNode *next;
    }LNode;
    typedef struct{
    LNode *top;
    }LStack;

    int main(){
    Status CreateBiTree(BiTree &T);
    Status Pop(LStack &S);
    Status Init_Stack(LStack &S);
    Status Push(LStack &S,BiTree T);
    Status StackEmpty(LStack S);
    Status PreOrderTraverse(BiTree T);
    void visit(TElemType data);

    BiTree T;
    printf("创建树中...");
    if(CreateBiTree(T))
        printf("创建成功\n");
    PreOrderTraverse(T);
    return 0;
    

    }

    Status CreateBiTree(BiTree &T){
    TElemType ch;
    if((ch=getchar())=='\n')
    T=NULL;
    else{
    T=(BiTNode *)malloc(sizeof(BiTNode));
    if(!T)
    exit(OVERFLOW);
    T->data = ch;
    CreateBiTree(T->lchild);
    CreateBiTree(T->rchild);
    }
    return OK;
    }

    Status Init_Stack(LStack &S){
    LNode *p;
    p=(LNode *)malloc(sizeof(LNode));
    if(!p)
    exit(OVERFLOW);
    p->next=NULL;
    S.top=p;
    return OK;
    }

    Status Push(LStack &S,BiTree T){
    LNode *p;
    p=(LNode *)malloc(sizeof(LNode));
    if(!p)
    exit(OVERFLOW);
    S.top->data = T;
    p->next = NULL;
    S.top = p;
    return OK;
    }

    Status StackEmpty(LStack S){
    if(S.top->next==NULL)
    return 1;
    else
    return 0;
    }

    void visit(TElemType data){
    printf("%c\n",data);
    }

    BiTree Pop(LStack &S){
    BiTree tran;
    LNode *t;
    tran=S.top->data;
    t=S.top;
    S.top=S.top->next;
    free(t);
    return tran;
    }

    Status PreOrderTraverse(BiTree T){
    LStack S;
    Init_Stack(S);
    BiTree p;
    p=T;
    while(p||!(StackEmpty(S))){
    if(p){
    Push(S,p);
    visit(p->data);
    p=p->lchild;
    }
    else{
    p=Pop(S);
    p=p->rchild;
    }
    }
    return OK;
    }

    
    

    图片说明
    每次都只能输出ABC,求教。。

    点赞 评论 复制链接分享

相关推荐