#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW 1
#define OK 0
#define ERROR 1
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct{
    BiTree *base;
    BiTree *top;
    int stacksize;
}SqStack;
void InitBiTree(BiTree &T){
    T=NULL;
}
int CreateBiTree(BiTree &T){
    int c;
    scanf("%d",&c);
    if(c==0) T=NULL;
    else{
        if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
        exit(OVERFLOW);
        T->data=c;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

int printelemt(int e){
    printf("%d",e);
    return OK;
}
int PreorderTraverse(BiTree T,int(*visit)(int e)){
    if(T){
        visit(T->data);
        PreorderTraverse(T->lchild,visit);
        PreorderTraverse(T->rchild,visit);
        
    }
}
int InitStack(SqStack &S){
    S.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree));
    if(!S.base) exit(OVERFLOW);
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
    return OK;
}
int Push(SqStack &S,BiTree e){
    if(S.top-S.base>=S.stacksize){
        S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree));
        if(!S.base)
        printf("OVERFLOW");
        S.top=S.base+S.stacksize;
        S.stacksize+=STACKINCREMENT;
    }
    *S.top++=e;
}
int Pop(SqStack &S,BiTree &e){
    if(S.top == S.base)  
    return ERROR;  
    e =*--S.top;  
    return OK;  
}
int StackEmpty(SqStack &S)  
{  
if(S.top == S.base)  
return OK;  
else  
return ERROR;  
}  
int InorderTraverse(BiTree T,int(*visit)(int e)){
    SqStack S;
    InitStack(S);
    BiTree P=T;
    while(P||!StackEmpty(S)){
    SqStack S;
    InitStack(S);
    BiTree p;
    p = T;
    while(p || !StackEmpty(S)) {
        if(p) {
            Push(S,P);
            P= P->lchild;
        }
        else{  
            Pop(S,P);
            if(!visit(P->data)) return ERROR;
            P = P->rchild;
        }
    }
}
 return OK;}

int main()
{
    BiTree T;
    InitBiTree(T);
    CreateBiTree(T);
    PreorderTraverse(T,printelemt);
    printf("\n");
    InorderTraverse(T,printelemt);
}   

收到的鲜花

• 书生牛犊 于 2016-08-03 08:53 送鲜花  20朵  

int InorderTraverse(BiTree T, int (*visit)(int e))
{
    SqStack S;
    InitStack(S);
    BiTree p;
    p = T;
    while (p || (StackEmpty(S) == ERROR))
    {
        if (p)
        {
            Push(S, p);
            p = p->lchild;
        }
        else
        {
            Pop(S, p);
            if (visit(p->data) != OK) return ERROR;
            p = p->rchild;
        }
    }
    return OK;
}

if 条件不要乱用！
都是错的

可是这是按照书上给出的来的，也不知道为什么错的==

你看的是啥书，跟我看的不一样

Status InOrderTraverse(BiTree T,Status( *Visit)(TElemType e)){
 InitStack(S);
 Push(S,T);
 while(!StackEmpty(S)){
  while((GetTop(S,p)&&p) Push(S,p->lchild);
  Pop(S,p);
  if(!StackEmpty(S)){
   Pop(S,p);
   if(!Visit(p->data)) return ERROR;
   Push(S,p->rchild);
  }
 }
return OK;
}

[此贴子已经被作者于2016-4-23 17:24编辑过]

中序遍历二叉树的另一种非递归算法

Status InOrderTraverse(BiTree T,Status( *Visit)(TElemType e)){
 InitStack(S);
 p=T;
 while(p||StackEmpty(S)){
  if(p){
   Push(S,p);
   p=p->lchild;
  }
  else{
   Pop(S,p);
   if(!Visit(p->data)) return ERROR;
   p=p->rchild;
  }
 }
return OK;
}

你写的是树上第一种非递归算法，我写的是第二种，但是两种我都试过，可以运行，但输入结果后出现程序错误

多谢，用你的是可以得出结果的，树上出问题了，老师和我们说了