isbst.cpp

判断一棵二叉树是否为二叉搜索树的算法

#include"BinaryTree.h"
#include<iostream.h>
#include<queue>
template<class T>
bool IsBST(BinaryTree<T>* tree);
void main()
{
int n;
int data[1000];
/*
程序主函数部分仅用来检测函数的正确性，与函数体无关
主函数中规定构造的二叉树为一完全二叉树，节点存储的
数据类型为整型，个数小于1000，构建顺序为广度周游顺
序。IsBST函数本身可以对任意二叉树进行判断
*/
cout<<"程序主函数部分仅用来检测函数的正确性，与函数体无关\n";
cout<<"主函数中规定构造的二叉树为一完全二叉树，节点存储的\n";
cout<<"数据类型为整型，个数小于1000，构建顺序为广度周游顺\n";
cout<<"序。IsBST函数本身可以对任意二叉树进行判断\n";
cout<<"\n\n请输入要加入的节点个数： ";
cin>>n;
if (n==0)return;
for (int i=0;i<n;i++)
{
cout<<"Node "<<i+1<<": ";
cin>>data[i];
}
BinaryTree<int> tree(data,n);
int result=IsBST(&tree);
if (result==1)cout<<"该树是二叉搜索树"<<endl;
else cout<<"该树不是二叉搜索树"<<endl;

}
template<class T>
bool IsBST(BinaryTree<T>* tree)
{
	if (NULL==tree->Root())return false;
	using std::queue;//使用队列保存要插入的节点
	queue<BinaryTreeNode<T>*> aQueue;
	BinaryTreeNode<T>* pointer;
	BinaryTreeNode<T>* temp;//用来和pointer的孩子进行比较
	BinaryTreeNode<T>* tempparent;//temp的父结点
	pointer=tree->Root();//令pointer指向根节点
	if (pointer)
		aQueue.push(pointer);//将根节点放入队列
	while (!aQueue.empty())
	{
		pointer=aQueue.front();//处理首个节点
		if(pointer->leftchild())
		{//判断当前节点是否小于左孩子,小于则不满足BST
			temp=pointer;
			tempparent=pointer->Parent(tree->Root(),temp);
			if(temp->value()<=pointer->leftchild()->value())
					return false;
			/*
			判断当前的左孩子是否满足BST要求的与其全部父结点的关系
			相当与一个（temp与tempparent比较）和（tempparent与左孩子比较）
			的同或
			*/
			while(tempparent!=NULL)
			{//同或关系用两个if实现
				if(temp->value()<=tempparent->value()&&tempparent->value()<=pointer->leftchild()->value())
					return false;
				if(temp->value()>=tempparent->value()&&tempparent->value()>=pointer->leftchild()->value())
					return false;
				temp=tempparent;
				tempparent=pointer->Parent(tree->Root(),tempparent);

			}
			aQueue.push(pointer->leftchild());
		//满足BST时讲左孩子放入队列,待处理
		}
		if(pointer->rightchild())
		{//对右孩子做相同处理
			temp=pointer;
			tempparent=pointer->Parent(tree->Root(),temp);
			if(temp->value()>=pointer->rightchild()->value())
					return false;
			while(tempparent!=NULL)
			{
				if(temp->value()<=tempparent->value()&&tempparent->value()<=pointer->rightchild()->value())
					return false;
				if(temp->value()>=tempparent->value()&&tempparent->value()>=pointer->rightchild()->value())
					return false;
				temp=tempparent;
				tempparent=pointer->Parent(tree->Root(),tempparent);
			}
			aQueue.push(pointer->rightchild());
		}
	aQueue.pop();//弹出首元素
	}
	return true;//直至队列置空仍不返回错误则是BST

}