蔡子经数据结构6.3

#include <stdlib.h>
typedef struct  ;
struct 
{
    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("%dn",flag);
    return 0;
}