#include<stdio.h>
#include<stdlib.h>

#define MAX 100
typedef struct BiNode//二叉树结点结构体
{
    char data;
    struct BiNode *lchild;
    struct BiNode *rchild;//左右孩子指针
}BiNode;

typedef BiNode *BiTree;//二叉树结点指针类型

typedef struct //二叉树结点栈
{
    BiTree stack[MAX+1];
    int flag[100];
    int top;
}SqStack;

typedef struct QNode//二叉树结点队列
{
    BiTree data;
    struct QNode *next;
   
}QNode;
typedef QNode *QueuePtr;

typedef struct
{
    QueuePtr *front;
    QueuePtr    *rear;
}LinkQueue;

void InitStack(SqStack *S)//初始化栈
{
    int i;
    S->top=0;
    for(i=0;i<MAX;i++)
    {
        S->stack[S->top]=NULL;
    }
}
void Push(SqStack *S,BiTree e)
{
    BiTree p;
    p=(BiTree)malloc(sizeof(BiNode));
    if(S->top==MAX-1)
    {
        printf("概栈已满!\n");
    }
    else
    {
        S->top++;
        S->stack[S->top]=p;
    }
}
void Pop(SqStack *S,BiTree e)
{
        BiTree p;
        if(S->top==0)
        {
            printf("该栈为空栈,无法弹出栈顶元素!\n");
        }
        else
        {
            p=S->stack[S->top];
            S->stack[S->top]=NULL;
            S->top--;
        }
}
int Top(SqStack *S)
{
    BiNode *p;
    if(S->stack[S->top]==NULL)
        printf("Stack is Empty!\n");
    else
         p=S->stack[S->top];
    return 0;
}
int StackEmpty(SqStack *S)
{
    if(S->top==0)
        return 1;
    else
        return 0;
}
BiTree CreateTree(BiTree t)
{
    char ch;
    //printf("please input data:\n");
    scanf("%c",&ch);
    if(ch=='#')
    {
        t=NULL;
    }
    else
    {
        t=(BiNode*)malloc(sizeof(BiNode));
        if(!t)
            exit(0);
        t->data=ch;
        t->lchild=CreateTree(t->lchild);
        t->rchild=CreateTree(t->rchild);
    }
    return t;
}
void Visit(BiTree t)
{
    printf("%c",t->data);
}
void PreOrder(BiTree t)
{
    SqStack S;
    BiNode *pre=t;
    if(t==NULL)
        exit(0);
    InitStack(&S);
    //printf("输出前序遍历序列:");
    while(!StackEmpty(&S))
    {
        //pre=Top(&S);
        //Pop(&s,c);
        if(pre!=NULL)
        {
             Visit(t);
            //S->stack[S->top++]=pre;
            Push(&S,pre);
            pre=pre->lchild;
        }
        else
        {
            Pop(&S,pre);
            pre=pre->rchild;
        }
    }
    printf("\n");

}
void InOrder(BiTree t)
{
    SqStack S;
    BiNode *pre=t;
    if(t==NULL)
        exit(0);
    InitStack(&S);
    //printf("输出中序遍历序列:");
    while(!StackEmpty(&S))
    {
        //c=top(&S);
        //Pop(&s,pre);
        if(pre!=NULL)
        {
            
            //S->stack[S->top++]=pre;
            Push(&S,pre);
            pre=pre->lchild;
        }
        else
        {
            Pop(&S,pre);
            Visit(t);
            pre=pre->rchild;
        }
    }
    printf("\n");
}
int main()
{
    BiTree bt=NULL;
    bt=CreateTree(bt);

    printf("Pre Order:\n");
    PreOrder(bt);
    printf("In Order:\n");
    InOrder(bt);
    return 0;
}

自己再 改下  堆栈函数就有问题

换成递归的成功后 再改成非递归的

自己改了一点，还是运行不出来，

递归的搞定了，

[ 本帖最后由 世界模型 于 2011-4-1 18:36 编辑 ]