回 帖 发 新 帖 刷新版面

主题:[菜鸟求助]二叉树中序遍历问题

谁帮我改改这程序啊...
好多错误!
#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef struct
{  int* base;
   int* top;
   int stacksize;
}SqStack;      //定义栈
typedef struct BiTNode
{  char data;
   struct BiTNode *lchild,*rchild; //左右孩子
}BiTNode,*BiTree;    //定义二叉树
Status InitStack(SqStack &S)
{  //构造一个空栈
    S.base=(BiTree*)malloc(STACK_INIT_SIZE * sizeof(BiTNode));
    if(!S.base) exit(OVERFLOW);//存储分配失败
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
    return OK;
}//InitStack
Status Push(SqStack &S,BiTree e)
{  //插入元素e为新的栈顶元素
    if(S.top-S.base>=S.stacksize)
    {  //栈满,追加存储空间
        S.base=(BiTree)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTNode));
        if(!S.base) exit(OVERFLOW); //存储分配失败
        S.top=S.base+S.stacksize;
        S.stacksize+=STACKINCREMENT;
    }//if
    *S.top++=e;
    return OK;
}//Push
Status Pop(SqStack &S,BiTree  &e)
{  //若栈不空,则删除S的栈顶原定,用e返回其值,并返回OK;否则返回ERROR;
    if(S.top==S.base) return ERROR;
    e=*--S.top;
    return OK;
}//Pop
Status GetTop(SqStack S,BiTree &e)
{  //若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR;
    if(S.top==S.base) return ERROR;
    e=*(S.top-1);
    return OK;
}//GetTop
Status StackEmpty(SqStack S)
{   //若栈为空,则返回TRUE,否则返回ERROR;
    if(S.top==S.base) return OK;
    else return ERROR;
}//StackEmpty
Status CreateBiTree(BiTree &T)
{  //按先序次序输入二叉树中的结点的值,空格表示空树
    //构造二叉链表表示二叉树T.
    char ch;
    scanf("%c",&ch);
    if(ch==' ') T=NULL;
    else
    {  if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
       T->data=ch;      //生成根结点
       CreateBiTree(T->lchild);
       CreateBiTree(T->rchild);
    }
    return OK;
}//CreateBiTree
Status InOrderTraverse(BiTree T)
{  //中序遍历二叉树的非递归算法
    BiTree p;
    SqStack S;
    InitStack(S); p=T;
    while(p||!StackEmpty(S))
    {  if(p){ Push(S,p); p=p->lchild;}//根指针进栈,遍历左子树
       else
       {     //根指针退栈,访问根结点,遍历右子树
           Pop(S,p);  if(!p) return ERROR;
           p=p->rchild;
       }//else
    }//while 
    return OK;
}//InOrderTraverse
/*Status Visit(char e)
{  char* p;
   *p=e;
   if(*p)  printf("%c",*p);
   else return ERROR;
   return OK;
}*/
void main()
{  BiTree T;
   CreateBiTree(T);
   InOrderTraverse(T);
}

回复列表 (共2个回复)

沙发

这个栈写得很有问题,好好看看书,重写下。

板凳

你的那个栈里的元素类型不对,你的栈里的存的已不是你定的int 类型的了,

我来回复

您尚未登录,请登录后再回复。点此登录或注册