判断树是否是二叉排序树

基本数据结构

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

typedef struct Node{
	int data;
	struct Node *lchild,*rchild;
}Node,*PNode;

一、创建二叉排序树：

指针s 和 p 的先后关系要注意，p 最后会为 NULL。

//创建二叉排序树 
PNode CreateBiTree(int a[],int n){
	int i,j,k,flag;
	PNode p,q,s,t;
	if(n<=0)
		return NULL;
	t=(PNode)malloc(sizeof(Node));
	t->data=a[0];
	t->lchild=NULL;
	t->rchild=NULL;
	printf("%d 进树\n",a[0]);
	for(i=1;i<n;i++)
	{
		flag = 0;
		p = t;
		while(p)
		{
			s = p;	//保存要加子节点的节点，因为 p 之后会为 NULL 
			if(a[i] > p->data)
			{
				p = p->rchild;
				flag = 2;
			}
			else
			{
				p = p->lchild;
				flag = 1;
			}
		}
		q=(PNode)malloc(sizeof(Node));
		q->data=a[i];
		q->lchild=NULL;
		q->rchild=NULL;	
		printf("%d 进树\n",a[i]);
		if(flag == 1)
			s->lchild = q; 
		else
			s->rchild = q;
	}
	return t;
}

二、判断树是否是二叉排序树：

有4种情况：
1、空树。
2、左孩子存在，右孩子不存在。
3、右孩子存在，左孩子不存在。
4、左右孩子都存在。

bool JudgeBiTree(PNode t)
{
	if(!t)
		return true;
	//左孩子存在，右孩子不存在，判断左孩子和父节点大小是否正常 
	if(t->lchild && t->rchild==NULL	&& t->data < t->lchild->data)	 
		return false;
	//右孩子存在，左孩子不存在，判断右孩子和父节点大小是否正常
	if(t->rchild && t->lchild==NULL	&& t->data > t->rchild->data) 	 
		return false;
	//左孩子存在，右孩子存在，判断左、右孩子和父节点大小是否正常 
	if(t->rchild && t->lchild && (t->data < t->lchild->data || t->data > t->rchild->data))	 
		return false;
	return JudgeBiTree(t->lchild) && JudgeBiTree(t->rchild);	//递归遍历子树是否正常 
}