蔡子经数据结构6.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108


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

typedef struct node node;
struct node
{
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("%d\n",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;//1表示为平衡树,0表示不是平衡树
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("%d\n",mark);
}