【数据结构周周练】035 利用递归判断一棵二叉树是否为二叉排序树

Bertha 。 2021-06-11 15:13 356阅读 0赞

# 一、二叉排序树 #

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

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

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

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

# 二、示例 #

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70][] 不是二叉排序树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 1][] 是二叉排序树

#  三、代码 #

#include<iostream>
    #include<malloc.h>
    
    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";
    
    }

# 四、实现效果 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 3][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70]: /images/20210516/5166ae979117418f89cfbed1de088764.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 1]: /images/20210516/bad8de618b98465ea04788c27a400211.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 2]: /images/20210516/8241c4fd2c864b21b41dc61491049f4d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 3]: /images/20210516/14afe7f61ca64587b6ab1e8fd694d59f.png