数据结构【二叉排序树实现和应用】

前言

此程序是数据结构课程设计（运气好抽了个最简单的emmm^^）,但是从这个相对简单的课设也学到了不少东西，下面做下记录

1、C++中指针的指针和引用

（1）首先再次深入了解指针和指针的指针

实际上，指针保存的就是我们存放数据的存储空间地址，指针的指针就是保存的存放指针的存储空间地址，通过指针保存的地址，我们通过*p能够对该指针指向的地址的空间的内容进行操作

由此，我们能够得到一个结论1、实际上指针的指针也是归于指针变量的范畴，他不是多层概念，指针是我们希望通过地址对一个数据进行操作而引入的，指针和指针指向的数据就是一个两层概念，指针的指针只不过是我们希望通过地址对指针变量进行修改而创建的 ，以此类推我们希望通过地址对指针的指针进行修改，就需要创建相应类型的指针的指针的指针。。。。往后也一样。

（2）引用

我们都知道引用就是变量的别名，操作一个变量的引用也就相当于操作变量本身

但是引用是在编译的过程中被处理的，实际上就是在编译层面对程序员进行的一个比较友好的语法，而在实现上是由编译器完成了地址的传递，实质上还是指针

讲人话，第二个结论：使用一个引用变量操作，就相当于使用一个指向原数据的指针来对原数据进行操作，只不过过程被隐藏了，同时创造引用的人封装这个过程的同时还增加了一些，引用不能为空，引用不能更改等等的规定，防止使用中不必要的错误”

例如：

#include<iostream>
using namespace std;
void test1(int *a)
{
	*a=2;
}
void test2(int &a){
	a=3;
}
int main(){
	int b=0;
	cout<<b<<endl;
	test1(&b);//因为通过上一部分，我们知道指针就是存储数据存储单元的地址的，这里我们直接使用&取地址
	cout<<b<<endl;
	test2(b);
	cout<<b<<endl;
}
/*输出为：
0
2
3*/

也就是说，使用引用变量a=b,就是*a=b，但是创建指针，使用时带星花，都省略了，表面理解就是“起了个别名”

规定引用不能为空，也是为了概念上契合“起个别名”，没有赋值，去给谁起别名操作呢？，引用不能改变，“别名”强制绑定一个对象，不能更改。

这里再添加一个误区说明，在C++中NULL的设定不是我们理解上的“空”而是：

#if defined(__cplusplus)
# define NULL 0    // C++中使用0作为NULL的值
#else
# define NULL ((void *)0)    // C中使用((void *)0)作为NULL的值
#endif

所以一般来说NULL就是地址为0的概念，不是“空”，而大多机器中地址0中的内容一般是不准许用户更改的。一般用于系统或者硬件调用。所以NULL可以赋予给引用变量，编译通过但是一般不要对其进行操作

（3）函数返回引用值

问题：函数内部创建的变量都是局部变量，即私有的，作用域就在函数之内，为什么却可以把值传出去呢呢？根本就在于实现机制中，类似于形式参数，函数结束返回时，将局部变量值拷贝给一个临时变量，然后将这个临时变量返回给调用函数，这样即使局部变量在返回时已经释放内存，也不影响返回的变量值

既然类似于形式参数，那么我们返回值能不能类似的使用引用呢？

答案是肯定可以的

一个函数的返回值定义为引用形式，就相当于真的“返回了它本身”没有副本的概念。

然而实际上，它的实现依旧是指针。实际上封装的的操作就是用指针接受返回的&a，再用这个指针去操作其对应值。所以对应的，我们想要使用这个引用值，必须要使用引用变量，否则和返回非引用效果相同。同时，我们也明确到，这个引用返回必须不能是局部变量，否则函数结束，释放空间，我们引用返回封装中本质上返回的地址所存储的值也就不明确了。虽然编译可以通过只是给予警告，有时该局部空间也没有被重新分配保持原值，但是这样是没有保障的，风险极大，故我们一般不能使用。

当然如果非要返回一个局部变量的引用，可以new 类型(初值) 申请一个堆内存的临时变量，这样只要不delete释放，那么在程序退出之前内存就不会被释放，直到不再使用时便可delete掉.

通常情况下，我们希望做到通过一个函数，真的对外部原数据进行操作，而不是局部数据，这样使用引用参数或者指针参数是足够的，但是，若我们想对函数得到的返回值结果再次进入一个函数进行操作，且仍然实际上是操作这个返回值（前提已经是这个返回值变量不是局部变量了），那么我们就必须使用返回引用同时使用引用变量接受或者返回地址同时使用指针接受，然后再进入另一个参数为引用或者指针的函数进行操作才可以

例如本次的二叉排序树的查询和插入操作：

我们希望使用查询的结果作为插入的输入，进行对以root为根的树的操作，我们查找不到某数据后必定为结果NULL，这也是我们希望插入的位置，但是NULL是我们希望插入节点的父节点的指针域，我们希望链接上父节点，即将父节点的NULL修改后指向我们新插入的节点，就必须使用返回指针的指针或者返回指针引用（前面讲过，这是两层概念，而非多层，我们希望对指针内容原数据修改，就使用指针的指针），这样再进入插入函数操作我们才能真正意义上的做到父节点链接新节点，否则我们只是创建副本接受了NULL的这个值，做不到真正的使用父结点的指针域

使用指针：

template <class T>
Node<T>** BSTree<T>::search(T data,Node<T> *&ptr){
	if(ptr==NULL) return &ptr;	//指针为空，说明没有找到该节点 返回&ptr。此时ptr的值为NULL而&ptr不为NULL; 
	else if(data<ptr->data) search(data,ptr->left);//查找数据小于该节点数据，进入左子树查找 
	else if(data>ptr->data) search(data,ptr->right);//查找数据大于该节点数据，进入右子树查找 
	else return &ptr;								//查找数据等于该节点数据，返回指向该节点的指针的指针。 
}
template <class T>
bool BSTree<T>::insertMain(T data,Node<T> *&ptr){
	Node<T> **p=search(data,ptr);//使用search函数，根据查找原理，可以查找到该节点的插入位置 
	if(*p==NULL){				//若为*p为空则说明找到了插入位置 
		*p=new Node<T>;			//申请空间 
		(*p)->data=data;		//存储数据 
	}else return false;
}

使用引用：

template <class T>
Node<T>*& BSTree<T>::search(T data,Node<T> *&ptr){
	if(ptr==NULL) return ptr;	//指针为空，说明没有找到该节点 返回&ptr。此时ptr的值为NULL而&ptr不为NULL; 
	else if(data<ptr->data) search(data,ptr->left);//查找数据小于该节点数据，进入左子树查找 
	else if(data>ptr->data) search(data,ptr->right);//查找数据大于该节点数据，进入右子树查找 
	else return ptr;								//查找数据等于该节点数据，返回指向该节点的指针的引用。 
}
template <class T>
bool BSTree<T>::insertMain(T data,Node<T> *&ptr){
	Node<T> *&p=search(data,ptr);//使用search函数，根据查找原理，可以查找到该节点的插入位置 
	if(p==NULL){				//若为p为空则说明找到了插入位置 
		p=new Node<T>;			//申请空间 
		p->data=data;		//存储数据 
	}else return false;
}

（4）总结：

1、引用其实本质就是地址

2、当函数返回值类型为引用时，一般就用引用类型去接收，或者就使用了引用的作用，如果用非引用类型接受，就等于将函数返回的引用的数据值，复制给了该接收对象，和函数返回非引用类型是一样的效果。
3、当函数返回值类型为引用时，如果不考虑接收问题，则有一个特性，则是可以直接操作该函数返回的引用，如放在=左面 +=等.

4、错象:当在函数内部定义了局部变量(本质就是为一段内存取了一个名字，并占用)，出了这个函数，这个局部变量不可再使用，也就是这个局部变量并不指向 任何一个内存了，但是这个局部变量原来所指的内存如果没有被系统重新分配，里面的值仍然没有变,如果有一个引用指向该局部变量，在局部变量被释放内存以 后，如果没有被系统重新将这段内存分配，那么其值仍可用。

5、不可以将常引用当作函数返回值返回.

6、用引用作函数参数和返回值类型的好处。直接是地址操作，不需要将值一一复制给形参，

7、返回值不需要有临时变量的存在，也不需要调用任何构造函数。节省了开销

8、一般当函数形参需要复杂类型的数据时，最好用引用，可以节省系统开销，

9、能用常引用的地方尽量用常引用。

10、如果非要返回一个局部变量的引用，可以new 类型(初值) 申请一个堆内存的临时变量，这样只要不delete释放，那么在程序退出之前内存就不会被释放，直到不再使用时便可delete掉.

推荐详细阅读：

总结选自：https://blog.csdn.net/tlxxm/article/details/8860760

C++引用的实现

2、封装一棵树

我们希望“定义一棵树”，真的就是定义一棵树，它的操作就是默认对本树操作，所以我们将很多递归程序或者具有使用根节点的程序分成两部分，主实现函数放入private域，不予公开，而添加调用函数，内容就是使用主实现函数，但是我们认为固定设定参数，例如树根指针就是本树的root

类似的操作我们在本次二叉树封装中进行了很多：

主实现函数：

private:
		//节点数 
		Node<T>* root; //根节点	
		bool insertMain(T data,Node<T> *&ptr); //插入节点主函数 
		void destroyTreeMain(Node<T> *p);//销毁树主函数 
		int deepthMain(Node<T> *p);//计算树的高度主函数 
		void inOrderMain(Node<T> *ptr);//中序遍历主函数 
		void outputLevelMain(Node<T> *p);//层次遍历主函数
		void outPutTreeByGraphMain(Node<T> *t,int h);//可视化遍历主函数;
		void sortedArrayToLowestBST_Main(T data[],int min,int max);//根据一有序序列创建高度最小的BSTree主函数
		void getPNumInEvrDeepth(int deepth,int num[],Node<T> *ptr); //获取每一层次的节点个数存入数组num中，方便计算AVL；

调用函数：

public:		
		bool insert(T data){insertMain(data,root);}; //插入节点调用函数 	 	 		
		void sortedArrayToLowestBST();//根据一有序序列创建高度最小的BSTree调用函数
		void inOrder(){inOrderMain(root);cout<<endl;};//中序遍历调用函数 
		void outputLevel(){outputLevelMain(root);cout<<endl;};		//层次遍历调用函数
		int deepth(){return deepthMain(root);};//计算树的高度调用函数 
		void destroyTree(){destroyTreeMain(root);root=NULL;};//销毁树调用 
		void outPutTreeByGraph(){outPutTreeByGraphMain(root,0);}; //树的图像输出调用

这样从外部看，我们定义一个二叉排序树，对其进行创建、增删改查都是默认对这一个树进行操作，不再需要树根指针等参数了。

3、图形化输出一棵树

其实很简单：就是利用了右子树—>父结点—>左子树遍历，根据结点所处的层数和指针域状况中间夹杂着一些符合的判断添加

template<class T>
void BSTree<T>::outPutTreeByGraphMain(Node<T> *t,int h){
	if(t!=NULL){
		outPutTreeByGraphMain(t->right,h+1);//右子树输出，h变量说明深度控制之后的空格输出 
		for(int i=0;i<h;i++)				//根据深度说明输出层数相适应的空格，使每一层节点在一竖列 
		cout<<"   ";
		cout<<t->data;						//空格输出完才输出数据 
		if(t->left!=NULL&&t->right!=NULL)	//输出完才输出数据，根据子节点，左右都有则输出'<' +换行 
		cout<<"<"<<endl;
		else if(t->left==NULL&&t->right!=NULL)//只有右子树则输出'/' +换行 
		cout<<"/"<<endl;
		else if(t->left!=NULL&&t->right==NULL)//只有左子树则输出'\' +换行 
		cout<<"\\"<<endl;						
		else cout<<endl;						//左右子树为空则输出换行
		outPutTreeByGraphMain(t->left,h+1);		//输出左子树 
	}
}

这样我们就能横向打印一个树了（结点数少的时候慢清晰的，能够直观根据树形判断自己的树功能是否正确，代码也不复杂，挺实用的）

4、本树的模板类的进一步封装体会

功能较多，为了使用更方便，于是在main函数中设计了一个菜单功能，但是，在这个设计中，不同类型的树，对于停止标记符号也不同，因为停止符号也设计成了模板T类符号，没有进行统一化，这样相关函数中输入才好设计，否则若设计了固定停止符号为‘#’，在一个int型的树中，我们万一有数据就是‘#’代表的ASCII码，就会停止，所以这样设计不是很好。而固定输入数据个数，万一个数打错了又要从新来过。最好还是设计一个停止标记，每种树设计一种对应类型的停止标记。而这样设计带来了一个问题，那就是菜单中是固定的调用，我们如何确认是哪种树呢？只是为了不同类型树使用不同标记而再次复制粘贴修改一两句代码显然是不合理的。

于是，我们将这个菜单功能也进行模板化，参数就是类型树和对应的停止标志，这样就合理了！

最终，我们的主函数只有寥寥几句

int main()
{
	BSTree<int> intTree;
	BSTree<char> charTree;
	BSTree<double> floatTree; 
	function(intTree,-1);
	function(charTree,'#');
	function(floatTree,-1.0); 
}

不同的树使用不同的模板类型的function即可，封装的很漂亮

5、switch case和{}

总结一句话：只要case中带变量不带括号，编译器都会报错，使用switch case的时候建议每个匹配选项后的执行区域推荐使用{}括起来，或者干脆不要将变量带入case中。

6、其他小坑

找合法序列时候使用单个读取而不是真的读取一个序列，导致有时一个序列中途就判断是错误的，那么后续的字符会被输入流读入菜单选项中，尽管使用了非正确功能序号不予相应的循环，但是若万一系列中多余的数据就符合菜单功能序号，就会出现非法调用功能的严重BUG，所以最终还是使用了动态数组存储然后删除

7、最终代码

#include<iostream>
#include <algorithm> 
using namespace std;
template <class T>
//创建节点 
struct Node{
	T data;
	Node<T>* left=NULL;
	Node<T>* right=NULL; 
};
//创建BSTree类 
template <class T>
class BSTree{
	public:
		BSTree();
		Node<T>* getRoot(){return root;};
		Node<T>** search(T data,Node<T> *&ptr);//在以ptr为根的二叉排序树中查询节点返回指向该节点的指针的指针					
		void creatBSTree(T stopSign);//以root为根创建BSTree；		 
		bool remove(T data);	//删除节点		 
		double getAVL();//获取查询的平均查找长度		 
		bool judgeLegalSequence(T stopSign);//判断某序列是否是合法查找序列
		
		bool insert(T data){insertMain(data,root);}; //插入节点调用函数 	 	 		
		void sortedArrayToLowestBST();//根据一有序序列创建高度最小的BSTree调用函数
		void inOrder(){inOrderMain(root);cout<<endl;};//中序遍历调用函数 
		void outputLevel(){outputLevelMain(root);cout<<endl;};		//层次遍历调用函数
		int deepth(){return deepthMain(root);};//计算树的高度调用函数 
		void destroyTree(){destroyTreeMain(root);root=NULL;};//销毁树调用 
		void outPutTreeByGraph(){outPutTreeByGraphMain(root,0);}; //树的图像输出调用
	private:
		//节点数 
		Node<T>* root; //根节点	
		bool insertMain(T data,Node<T> *&ptr); //插入节点主函数 
		void destroyTreeMain(Node<T> *p);//销毁树主函数 
		int deepthMain(Node<T> *p);//计算树的高度主函数 
		void inOrderMain(Node<T> *ptr);//中序遍历主函数 
		void outputLevelMain(Node<T> *p);//层次遍历主函数
		void outPutTreeByGraphMain(Node<T> *t,int h);//可视化遍历主函数;
		void sortedArrayToLowestBST_Main(T data[],int min,int max);//根据一有序序列创建高度最小的BSTree主函数
		void getPNumInEvrDeepth(int deepth,int num[],Node<T> *ptr); //获取每一层次的节点个数存入数组num中，方便计算AVL；
};
template <class T>
BSTree<T>::BSTree(){
	root=NULL;
}
template <class T>
Node<T>** BSTree<T>::search(T data,Node<T> *&ptr){
	if(ptr==NULL) return &ptr;	//指针为空，说明没有找到该节点 返回&ptr。此时ptr的值为NULL而&ptr不为NULL; 
	else if(data<ptr->data) search(data,ptr->left);//查找数据小于该节点数据，进入左子树查找 
	else if(data>ptr->data) search(data,ptr->right);//查找数据大于该节点数据，进入右子树查找 
	else return &ptr;								//查找数据等于该节点数据，返回指向该节点的指针的指针。 
}
template <class T>
bool BSTree<T>::insertMain(T data,Node<T> *&ptr){
	Node<T> **p=search(data,ptr);//使用search函数，根据查找原理，可以查找到该节点的插入位置 
	if(*p==NULL){				//若为*p为空则说明找到了插入位置 
		*p=new Node<T>;			//申请空间 
		(*p)->data=data;		//存储数据 
	}else return false;
}
template <class T>
void  BSTree<T>::creatBSTree(T stopSign){
	destroyTree();			//摧毁原有的树
	T data;
	cin>>data;
	while(data!=stopSign){
		insert(data);	//创建一个BSTree的过程就是从空树开始不断插入节点的过程 
		cin>>data;
	}
}
template <class T>
bool BSTree<T>::remove(T data){
	Node<T> **p=search(data,root);
	if(*p!=NULL){				//若*p不为空，则查找该节点成功，准备删除该节点 
		if((*p)->left!=NULL&&(*p)->right!=NULL){	//对左右子树都不为空的情况进行删除 
			Node<T> *temp=(*p)->right;
			while(temp->left!=NULL)	//找到右子树的中序遍历的第一个节点 
			temp=temp->left;
			T data=temp->data; //保存该值，否则删除右子树的中序遍历的第一个节点后，该值会消失，无法赋给*p节点 
			remove(temp->data);//由于右子树的中序遍历的第一个节点一定无左子树，我们可以直接用右子树链接，remove函数中已经定于了该操作，我们直接调用，提高代码复用率 
			(*p)->data=data;//右子树的中序遍历的第一个节点的值替换该节点的值		
		}else{
			Node<T> *temp=*p;		//备份该节点
			if((*p)->left==NULL) *p=(*p)->right;//如果该需要删除的节点左子树为空，则删除后使用该节点的右子树替代； 
			else *p=(*p)->left;					//如果该需要删除的节点右子树为空，则删除后使用该节点的左子树替代； 并且这种处理方式包含了都为空的处理，即赋值NULL 
			delete temp;			//删除该节点 
			return true;
		}
	}else return false; 		//若*p为空，则查找该节点失败 ，返回false 
}//实际上，删除一个点，若是左右子树至少有一个为空，则备份被删除的节点的指针，然后直接子树链接上其父节点指向删除节点的指针（，
// 判左空则使用右子树链接，判右空则使用左子树链接，这样就包括了双空的情况了。）最后使用备份指针释放空间即可。
//若是该左右子树全不是空则实际上转为使用 右子树的中序遍历的第一个节点 或者左子树中序遍历最后一个节点的值替换该节点的值
//然后删除只有右子树（或者左子树，取决于使用哪个作为替换节点）的替换节点，而这种删除左右子树至少有一个为空的操作，直接在此调用remove就可以完成，提高代码复用率 
template <class T>
void BSTree<T>::getPNumInEvrDeepth(int deepth,int num[],Node<T> *ptr){
	if(ptr!=NULL){
		num[deepth]++;//该节点不为空，则该层数节点数+1；								
		getPNumInEvrDeepth(deepth+1,num,ptr->left);//本层深度+1进入左子节点， 
		getPNumInEvrDeepth(deepth+1,num,ptr->right);//本层深度+1进入右子节点，
	}
}
template <class T>
double BSTree<T>::getAVL(){
	int *num=new int[20];//创建数组用于存储各个层次的节点数 
	int sum=0,pointNumber=0;//sum用于存储各个层次的节点数×层数，pointNumber存储节点个数； 
	for(int i=0;i<20;i++)//初始化数组全为0 
	num[i]=0;
	getPNumInEvrDeepth(1,num,root);//使用 getPNumInEvrDeepth函数获取每一层次的节点个数存储到num数组中；
	cout<<"("; 
	for(int i=1;i<20;i++)
	if(num[i]!=0){
		sum+=num[i]*i;		//加和各个层次的节点数×层数
		cout<<num[i]<<"×"<<i;
		if(num[i+1]!=0)
		cout<<"+"; 
		pointNumber+=num[i];//加和各个层次的节点数
	}
	cout<<")"<<"×1/"<<pointNumber<<"=";
	delete num;				//删除辅助数组 
	if(pointNumber==0) return 0;//若 pointNumber==0，则为空树，我们选择AVL置0 
	return (double)sum/pointNumber;//根据AVL的定义可以推算出，成功查找的AVL= (double)sum/pointNumber; 
} 
template <class T>
bool BSTree<T>::judgeLegalSequence(T stopSign){	//该方法判断一个序列，查找该序列最后一个数据所形成的通路是否正好是该序列 
	T *data=new T[20];
	for(int i=0;i<20;i++){
		cin>>data[i];
		if(data[i]==stopSign)
		break;
	}
	Node<T> *ptr=root;	
	int t=0;
	while(data[t]!=stopSign&&root!=NULL){//data[t]!=stopSign用来判断空序列，ptr！=NULL来判断序列超长情况的错误序列 
		if(data[t++]!=ptr->data)	//如果数据不等于该节点的数据则不是合法序列。直接跳出判断循环，进入非正确查找序列处理阶段 ,若正确相当于执行了t++进入下一个判断； 
		break;
		if(data[t]==stopSign){	//遇到终止标志，序列判断结束，到这里说明没有不合法数据，进入正确找序列处理阶段，删除动态存储数组并return true。
		delete data;
		return true; 
	}
		if(data[t]<ptr->data)	//没有遇到终止标志进入下一个数据判断，数据比本节点数据小，则进入左节点判断 
		ptr=ptr->left;
		else					//数据比本节点数据大，则进入左节点判断 ，这里必不可能等于，因为上一个节点等于ptr->data,而二叉排序树无相同节点 
		ptr=ptr->right; 		
	}
	delete data;//失败时的删除data动态数组 
	return false;//说明为空序列或者序列超长或序列数据的确非正确的查找序列，返回错误序列			
}
template <class T>
void  BSTree<T>::sortedArrayToLowestBST(){
	destroyTree();			//摧毁原有的树 
	int n;
	cout<<"输入有序序列包含的数据个数："; 
	cin>>n;
	cout<<"依次输入"<<n<<"个数据："; 
	T *data=new T [n];		//动态创建存储数据的数组，创建树后之后可以删除节省空间； 
	for(int i=0;i<n;i++)
	cin>>data[i];			//存入数据 
	sortedArrayToLowestBST_Main(data,0,n-1);//进入根据有序序列建立高度最小的二叉排序树主函数 
	delete data;			//建立完成删除存储数组 
}
template <class T>
void BSTree<T>::sortedArrayToLowestBST_Main(T data[],int min,int max){
	if(min<=max){
		insert(data[(max+min)/2]);		//若min<max则取下标mid=(max+min)/2即区间的中间值进行插入树操作。 
		sortedArrayToLowestBST_Main(data,min,(max+min)/2-1);//再从mid往左的区间进行递归 
		sortedArrayToLowestBST_Main(data,(max+min)/2+1,max);//从mid的往右的区间进行递归 
	}
}
template <class T>
void BSTree<T>::inOrderMain(Node<T> *ptr){
	if(ptr!=NULL)
	{
		inOrderMain(ptr->left);
		cout<<ptr->data<<" ";
		inOrderMain(ptr->right);
	}
}
template <class T> 
void BSTree<T>::outputLevelMain(Node<T> *p)
{
	Node<T> *Queue[100];			//建立一个容量100的结点指针数组作为队列 
	int front=0,rear=0;				//建立队首和队位指针 
	if(root!=NULL)					//判空 
	{
		Queue[rear++]=p;						//1、先将根入队
		while(front!=rear)						//2、设置队列非空循环条件 
		{
			cout<<Queue[front]->data<<" ";		//3、输出结点的值 
			if(Queue[front]->left!=NULL)		//4、若该结点左子树不为空则入队列
			{
				Queue[rear]=Queue[front]->left;	//补充:注意先存数据再将尾指针加1 
				rear=(rear+1)%100;		//5、为了充分使用空间，我们使用循环队列，队尾+1取余 
			}		
			if(Queue[front]->right!=NULL)		//6、若该结点右子树不为空则入队列
			{
				Queue[rear]=Queue[front]->right; 
				rear=(rear+1)%100;		//7、同理队尾+1取余 
			}
			front=(front+1)%100;		//8、将输出过的结点出队列 
		} 				
	} 	
} 
template <class T> 
int  BSTree<T>::deepthMain(Node<T> *p){
	if(p==NULL) return 0;
    int leftDeepth=deepthMain(p->left);		//计算左子树高度 
    int rightDeepth=deepthMain(p->right);	//计算右子树高度			
    return max(leftDeepth,rightDeepth)+1;	//取左右子树的最高高度再+1，max()函数需要头文件#include <algorithm> 
}
template <class T> 
void BSTree<T>::destroyTreeMain(Node<T> *p){
	if(p!=NULL){
		destroyTreeMain(p->left);	//若有左子树则进入摧毁左子树递归 
		destroyTreeMain(p->right);	//若有右子树则进入摧毁右子树递归  
		delete p;					//删除该节点 
	} 
}
template<class T>
void BSTree<T>::outPutTreeByGraphMain(Node<T> *t,int h){
	if(t!=NULL){
		outPutTreeByGraphMain(t->right,h+1);
		for(int i=0;i<h;i++)
		cout<<"   ";
		cout<<t->data;
		if(t->left!=NULL&&t->right!=NULL)
		cout<<"<"<<endl;
		else if(t->left==NULL&&t->right!=NULL)
		cout<<"/"<<endl;
		else if(t->left!=NULL&&t->right==NULL)
		cout<<"\\"<<endl;
		else cout<<endl;
		outPutTreeByGraphMain(t->left,h+1);
	}
}
void menu(){
	cout<<"应用选择:"<<endl;
	cout<<"			0:退出"<<endl; 
	cout<<"			1*:创建：输入待排序序列,创建排序二叉树"<<endl; 
	cout<<"			2*:删除：输入一个数据,在本树中查找该数据,若查找到则删除,若没有查找到则输出提示信息"<<endl; 
	cout<<"			3*:求AVL：计算本树的平均成功查找长度"<<endl; 
	cout<<"			4*:判断合法查找序列：输入一个序列,判断该序列是否是二叉排序树的合法查找序列"<<endl; 
	cout<<"			5*:输入一个有序序列,创建高度最小的二叉排序树"<<endl; 
	cout<<"			6:查找：输入数据,在本树中查询是否含有该数据"<<endl;
	cout<<"			7:插入：输入数据,在本树中插入数据为该数据的新结点"<<endl; 
	cout<<"			8:中序遍历输出"<<endl; 
	cout<<"			9:层次遍历输出"<<endl; 
	cout<<"			10:树的高度输出"<<endl; 
	cout<<"			11:销毁树"<<endl;
	cout<<"			12:图像打印本树"<<endl;
	cout<<"			13:调出菜单"<<endl;
}
template<class T>
void function(BSTree<T> tree,T stopSign){
		menu();
		int option;
		bool select=true;
		while(select){
		cout<<"请输入正确选择功能序号，非正确功能信号不会响应："; 
		while(1){
			cin>>option;
			if(option>=0&&option<=13)
			break;
		}		
		switch(option){
			case 0 :{
				select=false;
				break;
			} 				
			case 1 :{
				cout<<"输入数据序列,以"<<stopSign<<"为结束标志：" ; 
				tree.creatBSTree(stopSign);
				cout<<"创建完毕"<<endl;
				break;
			}			
			case 2 :{
				cout<<"输入待删除数据：" ;
				T t1;
				cin>>t1;
				if(tree.remove(t1))
				cout<<"删除成功"<<endl;
				else
				cout<<"删除失败,树中无该数据"<<endl;
				break;
			}
			case 3 :{
				if(tree.getRoot()==NULL){
					cout<<"空树！AVL=0"<<endl;
				}else{
					cout<<"本树的平均成功查找长度为："<<endl;
					cout<<tree.getAVL()<<endl;
				}	 
				break;
			}			
			case 4 :{
				cout<<"输入序列,以"<<stopSign<<"为结束标志：";
				if(tree.judgeLegalSequence(stopSign))
				cout<<"该查找序列合法"<<endl;
				else
				cout<<"该查找序列不合法"<<endl;
				break;
			} 			
			case 5:{
				cout<<"该操作会摧毁之前的树,进行重新建树,继续请输入1,取消输入0：";
				int t;
				cin>>t;
				if(t==1){
					tree.sortedArrayToLowestBST();
					cout<<"创建成功";
					break;			
				}
				cout<<"创建失败"<<endl; 		
				break;
			} 				
			case 6 :{
				cout<<"输入待查找数据：" ;
				T t2;
				cin>>t2;
				Node<T> *root=tree.getRoot();
				Node<T> **p=tree.search(t2,root);
				if(*p!=NULL)
				cout<<"查找成功"<<endl;
				else
				cout<<"查找失败,树中无该数据"<<endl;
				break; 
			} 				
			case 7 :{
				cout<<"输入待插入数据：" ;
				T t3;
				cin>>t3;
				if(tree.insert(t3))
				cout<<"插入结点成功"<<endl;
				else
				cout<<"已有该节点，插入失败"<<endl;
				break;
			}				
			case 8 :{
				tree.inOrder();
				cout<<"输出完毕"<<endl;
				break;
			}				
			case 9 :{
				tree.outputLevel();
				cout<<"输出完毕"<<endl;
				break;
			}				
			case 10 :{
				cout<<"本树的高度为："<<tree.deepth()<<endl;
				break;
			}
			case 11 :{
				tree.destroyTree();
				cout<<"摧毁完毕"<<endl;
				break;
			}
			case 12:{
				if(tree.getRoot()==NULL)
				cout<<"空树！打印失败"<<endl;
				else
				tree.outPutTreeByGraph();
				break;
			}
			case 13:{
				menu();
				break;		
			}			
		}
	}
	cout<<"该树的功能调用程序结束"<<endl;
} 
int main()
{
	BSTree<int> intTree;
	BSTree<char> charTree;
	BSTree<double> floatTree; 
	function(intTree,-1);
	function(charTree,'#');
	function(floatTree,-1.0); 
}
/*
测试数据：
建树序列：25 18 46 2 53 39 32 4 74 67 21 -1
判断合法1：25 46 39 -1
判断合法2：25 14 53  -1
有序序列建立高度最低的树：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
*/