二叉排序树(BST)的判定(其实不容易)

Biegral 2020/11/25 9:11:02 12448

      对于BST，一定要理解透彻，下面，我们给出一个有错误的BST判定程序：

 

// 程序中的isBST函数的逻辑是有错误

#include <iostream>
#define N 7
using namespace std;

// BST的结点
typedef struct node
{
	int key;
	struct node *lChild, *rChild;
}Node, *BST;

// 在给定的BST插入element, 使之称为新的BST
bool BSTInsert(Node * &p, int element)
{
	if(NULL == p) // 空树
	{
		p = new Node;
		p->key = element;
		p->lChild = p->rChild = NULL;
		return true;
	}

	if(element == p->key) // BST中不能有相等的值
		return false;

	if(element < p->key)  // 递归
		return BSTInsert(p->lChild, element);

	return BSTInsert(p->rChild, element); // 递归
}

// 建立BST
void createBST(Node * &T, int a[], int n)
{
	T = NULL; 
	int i;
	for(i = 0; i < n; i++)
	{
		BSTInsert(T, a[i]);
	}
}

// 生成一个结点
Node *createNode(int i)
{
	Node * q = new Node;
	q->lChild = NULL;
	q->rChild = NULL;
	q->key = i;

	return q;
}

// 建立一棵非BST树(这是之前的代码，直接复制过来的)
Node *createNotBST()
{
	Node *p[N] = {NULL};
	int i;
	for(i = 0; i < N; i++)
		p[i] = createNode(i + 1);

	for(i = 0; i < N/2; i++)
	{
		p[i]->lChild = p[i * 2 + 1];
		p[i]->rChild = p[i * 2 + 2];
	}

	return p[0];
}

// 判断是否为BST
bool isBST(BST T)
{
	// 空树是BST
	if(NULL == T)
		return true;

	// 只有一个结点的数是BST树
	if(NULL == T->lChild && NULL == T->rChild)
		return true;

	// 左子树为空(右子树不为空)
	if(NULL == T->lChild)
	{
		if(T->key < T->rChild->key && isBST(T->rChild))
			return true;

		return false;
	}
		
	// 右子树为空(左子树不为空)
	if(NULL == T->rChild)
	{
		if(T->key > T->lChild->key && isBST(T->lChild))
			return true;

		return false;
	}
	
	// 左右子树都非空
	if(T->lChild->key < T->key &&
		T->key < T->rChild->key &&
		isBST(T->lChild) &&
		isBST(T->rChild)
		)
		return true;

	return false;
}

void printJudge(Node *T)
{
	if(isBST(T))
		cout << "yes" << endl;
	else
		cout << "no" << endl;
}

int main()
{
	int a[10] = {4, 5, 2, 1, 0, 9, 3, 7, 6, 8};
	int n = 10;

	BST T = NULL;
	printJudge(T); // yes

	// 并非所有的a[]都能构造出BST,所以，最好对createBST的返回值进行判断
	createBST(T, a, n);
	printJudge(T); // yes

	T = createNotBST();
	printJudge(T); // no

	return 0;
}

       运行程序，发现结果是对的，但isBST函数在逻辑上是有硬伤的，不信请看isBST对下面这棵树的验证(结果为这棵非BST判为BST)：

 

 

// 程序中的isBST函数的逻辑是有错误

#include <iostream>
using namespace std;

// BST的结点
typedef struct node
{
	int key;
	struct node *lChild, *rChild;
}Node, *BST;


// 生成一个结点
Node *createNode(int i)
{
	Node * q = new Node;
	q->lChild = NULL;
	q->rChild = NULL;
	q->key = i;

	return q;
}

/*
	* 下面这棵树并非BST, 但程序中的isBST将其判为BST, 故isBST函数逻辑有误
	* 该树为：
	     3        // 根节点为3
       2          // 3的左孩子结点为2, 没有右孩子结点
	  1 4         // 2的左孩子结点为1, 右孩子结点为4
*/
Node *createTree()
{
	Node *p1 = createNode(1);
	Node *p2 = createNode(2);
	Node *p3 = createNode(3);
	Node *p4 = createNode(4);

	p3->rChild = NULL;
	p3->lChild = p2;

	p2->lChild = p1;
	p2->rChild = p4;

	p1->lChild = p1->rChild = NULL;
	p4->lChild = p4->rChild = NULL;

	return p3;
}

// 判断是否为BST
bool isBST(BST T)
{
	// 空树是BST
	if(NULL == T)
		return true;

	// 只有一个结点的数是BST树
	if(NULL == T->lChild && NULL == T->rChild)
		return true;

	// 左子树为空(右子树不为空)
	if(NULL == T->lChild)
	{
		if(T->key < T->rChild->key && isBST(T->rChild))
			return true;

		return false;
	}
		
	// 右子树为空(左子树不为空)
	if(NULL == T->rChild)
	{
		if(T->key > T->lChild->key && isBST(T->lChild))
			return true;

		return false;
	}
	
	// 左右子树都非空
	if(T->lChild->key < T->key &&
		T->key < T->rChild->key &&
		isBST(T->lChild) &&
		isBST(T->rChild)
		)
		return true;

	return false;
}

void printJudge(Node *T)
{
	if(isBST(T))
		cout << "yes" << endl;
	else
		cout << "no" << endl;
}

int main()
{

	BST T = NULL;
	printJudge(T); // yes

	T = createTree();
	printJudge(T); // yes (isBST将该树错判为BST)

	return 0;
}

       上述程序之所以有错，主要是因为对BST的定义理解有误，看看isBST函数就知道错在何方。

 

 

        下面，我们给出正确的程序（该程序没有考虑结点值为INT_MIN的情形）：

 

#include <iostream>
#define N 7
using namespace std;

int g_min = INT_MIN;

// BST的结点
typedef struct node
{
	int key;
	struct node *lChild, *rChild;
}Node, *BST;

// 生成一个结点
Node *createNode(int i)
{
	Node * q = new Node;
	q->lChild = NULL;
	q->rChild = NULL;
	q->key = i;

	return q;
}


/*
	* 下面这棵树并非BST, 但程序中的isBST将其判为BST, 故isBST函数逻辑有误
	* 该树为：
	     3        // 根节点为3
       2          // 3的左孩子结点为2, 没有右孩子结点
	  1 4         // 2的左孩子结点为1, 右孩子结点为4
*/
Node *createTree()
{
	Node *p1 = createNode(1);
	Node *p2 = createNode(2);
	Node *p3 = createNode(3);
	Node *p4 = createNode(4);

	p3->rChild = NULL;
	p3->lChild = p2;

	p2->lChild = p1;
	p2->rChild = p4;

	p1->lChild = p1->rChild = NULL;
	p4->lChild = p4->rChild = NULL;

	return p3;
}


// 建立一棵非BST树
Node *createNotBST()
{
	Node *p[N] = {NULL};
	int i;
	for(i = 0; i < N; i++)
		p[i] = createNode(i + 1);

	for(i = 0; i < N/2; i++)
	{
		p[i]->lChild = p[i * 2 + 1];
		p[i]->rChild = p[i * 2 + 2];
	}

	return p[0];
}


// 在给定的BST插入element, 使之称为新的BST
bool BSTInsert(Node * &p, int element)
{
	if(NULL == p) // 空树
	{
		p = new Node;
		p->key = element;
		p->lChild = p->rChild = NULL;
		return true;
	}

	if(element == p->key) // BST中不能有相等的值
		return false;

	if(element < p->key)  // 递归
		return BSTInsert(p->lChild, element);

	return BSTInsert(p->rChild, element); // 递归
}


// 建立BST
void createBST(Node * &T, int a[], int n)
{
	T = NULL; 
	int i;
	for(i = 0; i < n; i++)
	{
		BSTInsert(T, a[i]);
	}
}


// 判断是否为BST
bool isBST(BST T)
{
	if(NULL != T)
	{
		isBST(T->lChild);

		if(T->key <= g_min)
			return false;

		g_min = T->key;
		isBST(T->rChild);
	}

	return true;
}

void printJudge(Node *T)
{
	if(isBST(T))
		cout << "yes" << endl;
	else
		cout << "no" << endl;
}

int main()
{
	int a[10] = {4, 5, 2, 1, 0, 9, 3, 7, 6, 8};
	int n = 10;

	BST T = NULL;
	g_min = INT_MIN;
	printJudge(T); // yes

	T = createTree();
	g_min = INT_MIN;
	printJudge(T); // no

	T = createNotBST();
	g_min = INT_MIN;
	printJudge(T); // no

	createBST(T, a, n);
	g_min = INT_MIN;
	printJudge(T); // yes

	return 0;
}

       上面这个程序的原理是什么呢？怎么感觉有点类似于中序遍历呢？确实如此，其实就是中序遍历，原理是：

       (1) 空二叉树是BST

       (2) 对于非空二叉树而言：中序遍历为严格递增数列 《==》该树为BST.

      

 

 

 

本文转载:CSDN博客

阅读排行

分类

归档