本文共 2043 字，大约阅读时间需要 6 分钟。

一、二叉排序树

二叉排序树可以说是数据结构中相当重要的内容之一啦，前两次给大家讲了二叉排序树的创建、遍历与查找。今天给大家分享的是二叉排序树的应用，判断一个二叉树是否为一棵二叉排序树。

二叉排序树的特点大家都知道，左子树根结点值<根结点<右子树根结点值，并且中序遍历二叉排序树时，得到的序列是一个严格递增的序列。所以我们可以以此来判断二叉树是否为二叉排序树。

但是不能直接用二叉排序树的第一个特点，为什么呢？

我特别设计了第一个图片，大家会发现，每一个结点都满足左子树根结点值<根结点<右子树根结点值，但是77 > 67。所以不能单从一个结点来判断，我们要把这个原理改一下，左子树结点最大值<根结点<右子树结点最小值。这种方法更适合用来创建二叉排序树，不适合判断是否为二叉排序树，但是第二个特点非常适合用于判断。我们只需要设置一个比所有结点值最小值还小的一个值，与结点从小到大做判断即可，如果最小值比判断的值大，则说明不是二叉排序树，如果最小值比判断的值小，则接着往下做判断，直到树的最后一个结点。如果是二叉排序树，则最小值应该是最左侧的值，只要比这个值小，例如取最小值减一即可。

二、示例

利用算法判断下面的两个二叉树是否为二叉排序树。其中圆角矩形内为结点数据，旁边数字为结点编号，箭头指向的结点为箭尾的孩子结点。

 三、代码

#include
   
    #include
    
     using namespace std;typedef struct BiTNode {		int data;		int number;		struct BiTNode *parent,* lChild, * rChild;	}BiTNode,*BiTree;int number = 0;int yor = 0;int maxData;int isBST = 1;int yesOrNo[] = { 1,0,1,0,0,1,1,1,0,0,1,0,0,1,0,0 };//int numData[] = { 12,5,11,67,55,45,57,72 };int numData[] = { 12,10,11,67,55,51,77,82 };BiTree treeParent = NULL;int OperationBiTree(BiTree &BT) {	BT = (BiTree)malloc(sizeof(BiTNode));	if (!BT)	{		cout << "空间分配失败" << endl;		exit(OVERFLOW);	}	BT->number = number;	number++;	BT->data = numData[BT->number];	BT->lChild = NULL;	BT->rChild = NULL;	BT->parent = treeParent;	return 1;}void PreOrderCreatBiTree(BiTree &BT) {		OperationBiTree(BT);	treeParent = BT;	if (yesOrNo[yor++])		PreOrderCreatBiTree(BT->lChild);	treeParent = BT;	if (yesOrNo[yor++])		PreOrderCreatBiTree(BT->rChild);}void VisitBiTree(BiTree BT) {	cout << "当前结点的编号为：" << BT->number<<", 数据为：" << BT->data << ",\n";	}void InOrderBiTree(BiTree BT) {	if (BT)	{		InOrderBiTree(BT->lChild);		VisitBiTree(BT);		if (maxData < BT->data)		{			maxData = BT->data;		}		else			isBST = 0;		InOrderBiTree(BT->rChild);	}}void main() {	BiTree BT;	PreOrderCreatBiTree(BT);	BiTree p = BT;	while (p&&p->lChild)	{		p = p->lChild;	}	maxData = p->data - 1;	cout << "\n******【中序遍历二叉树】******\n";	InOrderBiTree(BT);	if (isBST)		cout << "This Binary tree is a binary sort tree.\n";	else		cout << "This Binary tree isn't a binary sort tree.\n";}
    
   

四、实现效果

转载地址：http://adyni.baihongyu.com/