Linux上的二叉树借助Stack非递归遍历

Linux下的二叉树借助Stack非递归遍历
这个不好说，直接上代码：

C/C++ code

#define TRUE 1#define ERROR 0#define OK    1#define FALUSE 0#define OVERFLOW    -1typedef int Status;typedef char TElemType;typedef struct BiTNode{    TElemType  data;    struct BiTNode *lchild,*rchild;}*BiTree;BiTree *CreateBiTree(BiTree *T);//Status CreateBiTree(BiTree &T);Status PreOrderTraverse(BiTree T);Status InOrderTraveerse(BiTree T);Status PostOrderTravaerse(BiTree T);//---------------------------#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct Stack{    BiTree *top;    BiTree *base;    int stacksize;}*SqStack;SqStack InitStack(SqStack S);//struct Stack *ClearStack(SqStack S);int StackEmpty(SqStack S);//void StackLength(SqStack S);BiTree  GetTop(SqStack S);SqStack Push(SqStack S,BiTree T);BiTree Pop(SqStack S);void Print(SqStack S);

C/C++ code

//BiTree.c#include<stdio.h>#include"BiTree.h"#include<stdlib.h>SqStack InitStack(SqStack S){    S=(SqStack)malloc(sizeof(struct Stack));    S->base =(struct BiTNode **)malloc(STACK_INIT_SIZE*sizeof(struct BiTNode**));    if(!S->base) exit(1);    S->top=S->base;    S->stacksize =STACK_INIT_SIZE;        return S;}BiTree GetTop(SqStack S){        BiTree e;    BiTree *p;    p=S->top;    if(S->top == S->base) return 0 ;    p=p-1;    e=*p;    return e;    }SqStack Push(SqStack S,BiTree e){        if((S->top)-(S->base)>=(S->stacksize)){        S->base =(BiTree*)realloc(S->base,(S->stacksize + STACKINCREMENT)*sizeof(struct BiTNode**));                S->top=S->base+S->stacksize;        S->stacksize+=STACKINCREMENT;        }    *(S->top)=e;    S->top++;    return S;}BiTree Pop(SqStack S){    BiTree e;    if(S->top ==S->base) return NULL;    S->top=S->top-1;    e=*S->top;    return e;}int StackEmpty(SqStack S){    if(S==NULL||(S->base == S->top))    {        return 1;    }    else    {        return 0;    }}//void Print(SqStack S)//{    //    BiTree p;//    p=S->top-1;//    while(p!=S->base)//    {//        printf("%4c",*p);//        p=p-1;//    }//    printf("%4c",*S->base);//}BiTree *CreateBiTree(BiTree *T)//????¶þ²æÊ÷{    char ch;    ch=getchar();        if(ch=='#') T=NULL;        else        {             if(!((*T)=(BiTree)malloc(sizeof(struct BiTNode))))   exit(FALUSE);            (*T)->data=ch;            CreateBiTree(&(*T)->lchild);            CreateBiTree(&(*T)->rchild);//?Ë?äûÓÐÖ?ÐÐ        }        //scanf("%c",&ch);        return (*T);    }/*Status CreateBiTree(BiTree &T)//????¶þ²æÊ÷{    char ch;        ch=getchar();        if(ch=='#') T=NULL;        else        {             if(!(T=(BiTree)malloc(sizeof(struct BiTNode))))   exit(FALUSE);            T->data=ch;            CreateBiTree(T->lchild);            CreateBiTree(T->rchild);//?Ë?äûÓÐÖ?ÐÐ        }        //scanf("%c",&ch);            return OK;}*/Status PreOrderTraverse(BiTree T)//ÏÈÐò±éÀú{    //µÝ¹é    //if(T)    //{     //        printf("%c",T->data);     //        PreOrderTraverse(T->lchild);     //        PreOrderTraverse(T->rchild);     //}     //·ÇµÝ¹é    return OK;}Status InOrderTraveerse(BiTree T)//ÖÐÐò±éÀú{        //µÝ¹é        //if(T)        //{         //        InOrderTraveerse(T->lchild);         //        printf("%c",T->data);         //        InOrderTraveerse(T->rchild);         //}         //·ÇµÝ¹é        SqStack S=NULL;        S=InitStack(S);        BiTree p=NULL;        p=T;        while(p||!StackEmpty(S))        {            if(p){S=Push(S,p); p=p->lchild;}            else            {                p=Pop(S);                printf("%4c",p->data);                p=p->rchild;            }        }    return OK;}//Status PostOrderTravaerse(BiTree T)//ºóÐò±éÀú{    //µÝ¹é    //if(T)    //{     //    PostOrderTravaerse(T->lchild);     //    PostOrderTravaerse(T->rchild);     //    printf("%c",T->data);     //}     //·ÇµÝ¹é    return OK;} 
 

C/C++ code

//main.c#include"BiTree.h"#include<stdlib.h>#include<stdio.h>int main(){    BiTree root=NULL;    printf("Begin create the BinaryTree..");    root=CreateBiTree(&root);    printf("\nCreate has Done!");    printf("InOrderTraverse..");    InOrderTraveerse(root);    printf("\nDone!!!!\n");    return 0;    }

我在linux下用gdb是真的不怎么会用，我把这段代码弄到vs2010下输入ABC##D##G##后出错，但是我在CreateBiTree中一步步的执行后返回的（*T）没有问题阿，然后我把里面的参数换成CreateBiTree（BiTree &T）后，程序能正常运行并且输出也正确阿
这是怎么回事？我知道在linux下编程和在windows下不一样，但是就是找不到原因！各位大大给看看，指点迷津，谢谢拉～我只有40分可以散了，不好意识。。

[解决办法]
貌似要if(ch=='#') *T=NULL;
还有参数传地址了，就不用再返回数据，类似void CreateBiTree(BiTree *T)即可...

查看更多 下一篇