蔡子经数据结构6.3

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

#include <stdio.h>
#include <stdlib.h>
typedef struct node node;
struct node
{
int val;
node *lchild,*rchild;
};
#define MAXN 100

node* createNodeWithVal(int val)
{
node *rt = (node*)malloc(sizeof(node));
rt->lchild = rt->rchild = NULL;
rt->val = val;
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);
return rt;
}


//判断一棵二叉树是否是查找树
//这里假设树中存储的键值全为正整数,则这里用0来当作无穷小,9999当作无穷大
int flag = 1;//flag = 1表示是查找树
//flag为0表示不是查找树
int Judge(node *rt,int mark)
{
if(rt == NULL) return mark ? 9999 : 0;
int lc = Judge(rt->lchild, 0);//0表示左孩子
int rc = Judge(rt->rchild, 1);//1表示右孩子
if(rt->val <= lc || rt->val >= rc)
flag = 0;
if(rc == 9999) rc = 0;//忽略掉这个额外添加的最大值,不然就把这个虚无的最大值算进返回值里了
int mm = lc > rc ? lc : rc;
return rt->val > mm ? rt->val : mm;
}

int main()
{
node *root = createTree();
Judge(root,0);
printf("%d\n",flag);
return 0;
}