数据结构与算法----3.2 判别二叉树是否为二叉排序树

[c++]代码库

#include <iostream>
using namespace std;
typedef int KeyType;
struct ElemType{KeyType key;};
typedef struct BiTNode
{
    ElemType data;
	BiTNode *lc,*rc;
}*BiTree;

bool realBT(BiTree T); //判断是不是二叉排序树
bool realBT(BiTree T,BiTree &pre);
void BiTreeLists(BiTree T, void visit(ElemType));
BiTree CreatNode(ElemType x);
bool InsertBST(BiTree &T, ElemType x) ;
void visit(ElemType data);
void CreatBST(BiTree &T, int n, ElemType a[]);
void inorder(BiTree T);
int main()
{
	BiTree T;int n=7;
	ElemType s[]={7,3,1,5,11,9,13};
	
	CreatBST(T,n,s);
	cout<<"二叉树(广义表形式)为：";BiTreeLists(T,visit);
	cout<<"\n二叉树的中序序列为："<<endl;
    inorder(T);
	cout<<"\n此二叉树"<<( realBT(T)?"是":"不是")<<"二叉排序树!"<<endl;
	return 0;
}
BiTree CreatNode(ElemType x)
{
	BiTree p;
	p = new BiTNode; p->data = x;
	p->lc = p->rc = NULL;
	return p;
}
void BiTreeLists(BiTree T, void visit(ElemType))
{  
	if (!T) { cout << "#"; return; }
	visit(T->data);
	if (T->lc || T->rc) {
		cout << "(";
		BiTreeLists(T->lc, visit);
		cout << ",";
		BiTreeLists(T->rc, visit);
		cout << ")";
	}
}
void CreatBST(BiTree &T, int n, ElemType a[])
{
	T = NULL;
	for (int i = 0; i < n; i++) {
		InsertBST(T, a[i]);
	}
}

void visit(ElemType data)
{
	cout << data.key;
}
bool InsertBST(BiTree &T, ElemType x) 
{
	if (!T) {
		T = CreatNode(x); return true;
	}
	else if (T->data.key == x.key) {
		return false;
	}
	else if (x.key < T->data.key) {
		return InsertBST(T->lc, x);
	}
	else {
		return InsertBST(T->rc, x);
	}
}
bool realBT(BiTree T,BiTree &pre)
{ 
	if(!T)return true;
    if(!realBT(T->lc,pre))return false;
	if(pre&&pre->data.key>=T->data.key)return false;
	pre=T;
	return realBT(T->rc,pre);
} 
bool realBT(BiTree T)
{
	BiTree pre=NULL;
	return realBT(T,pre);
}
void inorder(BiTree T)
{
	if (!T)		return;
	inorder(T->lc);
	cout<<T->data.key<<" ";
	inorder(T->rc);
}