蔡子经数据结构6.5

#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)
{
    if(top == MAXN)
    {
        puts("error");
        exit(0);
    }
    Stack[top++] = temp;
}

node* pop()
{
    if(top == 0)
    {
        puts("error");
        exit(0);
    }
    return Stack[--top];
}

node* _top()
{
    if(top == 0)
    {
        puts("error");
        exit(0);
    }
    return Stack[top-1];
}

int isEmpty()
{
    return top == 0;
}

void visit(node *rt)
{
    printf("%dn",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;
}

node* createNode()
{
    node *rt = (node*)malloc(sizeof(node));
    rt->lchild = rt->rchild = NULL;
    rt->val = rt->mark = 0;
    return rt;
}

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);
    rt->lchild->lchild->lchild = createNodeWithVal(10);
    rt->lchild->lchild->lchild->rchild = createNode(20);
    return rt;
}

int mark = 1;
int CalcHeight(node *rt)
{
    if(rt == NULL) return 0;
    int lh = CalcHeight(rt->lchild) + 1;
    int rh = CalcHeight(rt->rchild) + 1;
    if(abs(rh-lh) > 1) mark = 0;
    return lh > rh ? lh:rh;
}

int main()
{
    node *root = createTree();
    int height = CalcHeight(root);
    printf("%dn",mark);
}