decision_of_bst.cpp

试写一个判别给定二叉树是否为二叉排序树的程序。 1．1．1 此二叉树以二叉链表作存储结构； 1．1．2 树中结点的关键字均不同。 1．1．3 正、反测试用例自己设计

#include<iostream>
using namespace std;
const int listInitSize=50;//线性表空间初始分配量
const int listIncrement=10;//线性表空间分配增量

typedef struct{
	int * p;       //存储空间基址
	int length;    //当前长度
	int listsize;  //当前分配存储容量
}SqList;
void InitList(SqList &l)  //初始化空表
{l.p=new int[listInitSize];
 if(!l.p)exit(1);           //分配失败
 l.length=0;             //空表长度为0
 l.listsize=listInitSize;//初始存储容量
}
void ListInsert(SqList &L,int e)
{if(L.length>=L.listsize){
	int * p=new int[listInitSize+listIncrement];
	if(!p)exit(1);
	for(int i=0;i<L.length;i++,p++,L.p++)*p=*L.p;
	L.p=p;
	L.listsize+=listIncrement;
	}
	L.p[L.length]=e;
	L.length++;
}


typedef struct BiTree{     //二叉树
	int key;
	BiTree *lchild;
	BiTree *rchild;
}* BiNode;

int judgeRPT(int * p,int j,int e);
void CreateBiTree(BiTree *&T,SqList &l)//中序遍历建树 
{   int ch;
	cout<<"请输入结点  \n";
	cin>>ch;
	while(judgeRPT(l.p,l.length ,ch)==0 && ch!=0)
	{cout<<"数据重复请重新输入 \n";
	 cin>>ch;}
	ListInsert(l,ch);
	if(ch==0){ T=NULL; }
	 else{ 
		 BiTree *t=new BiTree; 
		 t->key=ch; 
		   T=t;
		 CreateBiTree(T->lchild,l);
		 CreateBiTree(T->rchild,l);
	      }
}
int judgeRPT(int * p,int j,int e)
{for(int i=0;i<j;i++)
	if(p[i]==e)return 0;
 return 1;
}

void Print_BiTree( BiTree *T,int i=0)//按树状打印输出二叉树的元素,i表示结点所在层次,初次调用时i=0
{ if(!T) {cout<<"空树 \n";return;}
  cout<<endl;
  if(T->rchild) Print_BiTree(T->rchild,i+1);
  for(int j=1;j<=i;j++) 
	  cout<<(" "); //打印i个空格以表示出层次
  cout<<T->key<<endl;
  //printf("%c\n",T->data); //打印T元素,换行
  if(T->lchild) Print_BiTree(T->lchild,i+1);
}//Print_BTree  

BiTree * decisionBST(BiTree * bt)     //判断是否为二叉排序树
{ BiTree * mark=NULL;                  //标记需调整的子树
  if(bt==NULL)return NULL;
  BiTree *p=bt->lchild;
  if(p){while(p->rchild)p=p->rchild;}
  BiTree *q=bt->rchild;
  if(q){while(q)q=q->lchild;}
  if((!p||bt->key > p->key) && (!q||bt->key < q->key))
	{mark=decisionBST(bt->lchild);
	 if(!mark)mark=decisionBST(bt->rchild);
	 return mark;
	}
	else return bt;
}
/*
BiTree * InsertBST(BiTree *T,int e);
SqList adjust(BiTree * bt,SqList l)
{if(!bt)return l;
 ListInsert(l,bt->key );
 adjust(bt->lchild ,l);
 adjust(bt->rchild ,l);
 return l;
}
BiTree * adjustedBST(BiTree * bt)           //调整为二叉排序树
{if(!bt)return NULL;
 SqList l;
 InitList(l);
  adjust( bt, l);
BiTree * p=NULL ;
for(int i=0;i<l.length;i++)p=InsertBST(p,l.p [i]);
return p;	

 	
}
void SearchBST(BiTree * T,int key,BiTree * &p,BiTree * f=NULL)//搜索
{if(!T)p=f;
 else if(key<T->key)SearchBST(T->lchild,key,p,T);
 else SearchBST(T->rchild,key,p,T);
}
BiTree * InsertBST(BiTree *  T,int e)   //插入
{	BiTree * p=NULL;
	SearchBST(T,e,p,NULL);
    BiTree * s=new BiTree;
	s->key=e;s->lchild=NULL;s->rchild=NULL;
	if(!p)T=s;
	else if(e < p->key)p->lchild=s;
	else p->rchild=s;
	return T;
}
*/


int main()
{  int c=1,g=1,d=0;BiTree *mark=NULL;
   BiTree * T=NULL;
   SqList l;
   cout<<"请按先序遍历输入结点 \n";
   cout<<"用0表示空结点 \n";
   while(g==1)
   {
    while(c==1)
    { InitList(l);
      T=NULL;
	  CreateBiTree(T,l);
      Print_BiTree(T);
	  cout<<"若有误按1重输 \n否则按任意数字键继续 \n";
	  cin>>c;
    }
	mark=decisionBST(T);
    if(decisionBST(T)==NULL)cout<<"是二叉排序树\n";
      else cout<<"不是二叉排序树 \n以"<<decisionBST(T)->key<<"为结点的子树不符合\n";
/*	cout<<"需要调整吗? \n需要:1 \n不需要:0 \n";
	cin>>d;
	if (d==1)T=adjustedBST(T);
    Print_BiTree(T);
*/
    c=1;
    cout<<"测试下一棵树吗? \n要:1 \n不要:0 \n";
    cin>>g;
  }

   
   return 0;
}