判断某个二叉树是不是二分搜索树

题目

给出一个二叉树，判断它是不是一个二分搜索树(BST).二分搜索树的定义如下:

        一、节点的左子树所包含的值小于此节点的值。

        二、节点的右子树所包含的值大于此节点的值。

        三、节点的左右子树均为二分搜索树。

lnput: [5,1,4,null,null,3,6] Output: false	Input: [2,1,3] output: true

解析

按照数组的索引构建一颗二叉树如下所示：

注意：为了方便查找索引规律，数组索引是从1开始的。

可以看出此一维数组中的索引值有以下关系：

        1、左子树的索引值是父节点的索引值乘2。

        2、右子树的索引值是父节点的索引值乘2加1。

        3、按照二分搜索树的规律，二分搜索树的节点应该是对称的，不存在只有左子树或者只有右子树的节点

        因此二分搜索数的节点必须是奇数。

实现判断步骤

1.求数组中的数据在二叉树中分几层

思路：

   1、已知数据总个数，求层数

    数组按1生2 2生4 4生8 生成二叉树

    数据总个数 = 2^0 + 2^1+2^2+...2^n = 2^(n+1) - 1

    层数 = 向下取整( log2(数据个数) )

        2、每一层每个节点的左右子树和根节点进行对比        

思路：
搜索结果  二分搜索树判断函数(数组，长度)
{
	如果长度为奇数
	{
		返回 -1
	}

	求二叉树总层数

	循环开始每一层的比较 -- 循环变量为i
	{
		求第i层的数据总个数
		求第i层第一个数据的数组索引

		循环获取这一层上的左右子树对应的数组数据
		{
			如果 当前索引 > 数组长度 或者 左子树数组数据为NULL 或者 右子树数组数据为NULL
			{
				结束或者本组数据不用判断继续下一组
			}
			否则
			{
				// 对比对应下标数据，
				如果 左子树数组数据 > 父节点数据 或者 右子树数组数据 < 父节点数据
				{
					不满足二分搜索树条件，返回0
				}
			}
		}
	}

	// 如果对比了所有节点都满足二分搜索树条件，没有结束函数
	二分搜索树条件，返回1
}

3、代码实现

#include<stdio.h>
#include<math.h> 

// 先将二叉树按照层次放入数组中 
int isBinaryTree(int arr[],int size)
{
	// 如果数据是偶数则 有节点缺少左子树或者右子树 
	if(size % 2 == 0) return -1;  
	// 先求二叉树的层次,已知数组的长度求层数
	// 数组按1生2 2生4 4生8 生成二叉树， 
	// 	
	int fNum = (int)floor(log2(size));
	
	int i;   // 层次循环变量 
	int j;   // 每一层的数据循环变量 
	int num; // 每一层的数据总个数 
	int firstNum; // 每一层第一个数据的索引 
	int a;   // 存放每一次对比的左子树索引 
	
	// 从第1层开始对比到最后一层，顶层只有一个不用比较 
	for(i=1;i<fNum;i++)
	{		
		// 第i层的数据个数为：2^i 
		num = (int)pow(2,i);
		
		// 第i层的第一个数的索引为2^i
		firstNum = (int)pow(2,i);		
		
		// 第i层的第j个数据，j和j+1对应的数据是一个节点的左右子树 
		for(j=0;j<num;j+=2)
		{
			// 序号  对应数组的下标应该是a-1和a
			a = firstNum + j;   
			
			if(a > size || arr[a-1] == NULL || arr[a] == NULL)
			{
				// 如果该层的节点没有了或者数组中的数据已经是NULL了就继续后面的对比 
				continue;
			} 
			else
			{
				// 如果  数组中对应左子树上的数据 > 根节点的数据 
				// 或者  数组中对应右子树上的数据 < 根节点的数据 
				// 则 该二叉树不是二分搜索树--直接返回0 
				if(arr[a-1] > arr[a/2-1]  ||  arr[a] < arr[a/2-1])
				{
					return 0;
				}
			}
		}
		 
	} 
	
	// 如果对比了所有节点都满足  数组中对应左子树上的数据 < 根节点的数据 
	// 同时  数组中对应右子树上的数据 < 根节点的数据
	// 则 该二叉树不是二分搜索树--直接返回1 
	return 1; 
} 

int main()
{
	// int a[] = {2,1,3};
	// int a[] = {5,1,8,NULL,NULL,6,10};
	int a[] = {5,1,4,NULL,NULL,3,6};
	int len = sizeof(a) / sizeof(int);

	int res = isBinaryTree(a,len);
	
	if(res == 1)
	{
		printf("yes");
	}
	else if(res == 0) 
	{
		printf("no"); 
	}
	else if(res == -1)
	{
		printf("数组数据必须保持奇数个"); 
	}
	return 0;
}