蔡子经数据结构5.4

#include <stdlib.h>
typedef struct  ;
struct 
{
    int val,mark;
    node *lchild,*rchild;
};
#define MAXN 100
node* Stack[MAXN];
int top;
node *root = NULL;

void InitStack(){top = 0;}//初始化栈
void Push(node *temp){Stack[top++] = temp;}//入栈
node* Pop(){return Stack[--top];}//返回栈顶元素，同时出栈
node* Top(){return Stack[top-1];}//返回栈顶元素
int IsEmpty(){return top == 0;}//判断是否为空
void visit(node *rt){printf("%d ",rt->val);}

node* createNodeWithVal(int val)
{
    node *rt = (node*)malloc(sizeof(node));
    rt->lchild = rt->rchild = NULL;
    rt->val = val;
    rt->mark = 0;
    return rt;
}
/*
      4
  2       6
1   3   5   7
*/
node* createTree()
{
    node *rt = createNodeWithVal(4);
    rt->lchild = createNodeWithVal(2);
    rt->rchild = createNodeWithVal(6);
    rt->lchild->lchild = createNodeWithVal(1);
    rt->lchild->rchild = createNodeWithVal(3);
    rt->rchild->lchild = createNodeWithVal(5);
    rt->rchild->rchild = createNodeWithVal(7);
    return rt;
}

void PostOrder(node *rt)
{
    InitStack();
    node *p = rt;
    node *r = NULL;
    while(p || !IsEmpty())
    {
        if(p != NULL)
        {
            Push(p);
            p = p->lchild;
        }
        else
        {
            p = Top();
            if(p->rchild != NULL && p->rchild != r)
            {
                p = p->rchild;
                Push(p);
                p = p->lchild;
            }
            else
            {
                p = Pop();
                visit(p);
                r = p;
                p = NULL;
            }
        }
    }
}

int main()
{
    node *root = createTree();
    PostOrder(root);
    return 0;
}