数据结构

开发平台：

Visual C++

BSTree.h：源码内容

							//二叉树类模板（其中二叉树生成产生完全二叉树）。特别注意
//插入结点时，第二参数为指针的引用！否则不能建立树。为什么？请读者自己思考。
#include<iostream>
using namespace std;
template<typename T>class BinaryTree;
template<typename T>class Node{
	Node<T> *lchild,*rchild;
	T info;
public:
	Node(){lchild=NULL;rchild=NULL;}
	Node(T data,Node<T> *left=NULL,Node<T> *right=NULL){
		info=data;
		lchild=left;
		rchild=right;
	}
	friend class BinaryTree<T>;
	
};
template<typename T>class BinaryTree{
	Node<T> *root;                  //二叉树的根指针
	void InOrder(Node<T> *Current);                //中序遍历
	void Insert(const T &data,Node<T> * &b); //插入结点，参数为引用！
	void Destory(Node<T> * Current);        //删除树
	int Countdepth(Node<T> *btree);         //树深度计数
public:
	BinaryTree(){root=NULL;}				//空树构造函数,无头结点
	~BinaryTree(){Destory(root);}			//析构函数
	void Creat(T data);                    //一步一步建立（排序）二叉树
	void InOrder(){InOrder(root);}                //中序遍历，公有函数为接口
	int Countdepth(){return Countdepth(root);}      //树深度计数
};
template<typename T> void BinaryTree<T>::Destory(Node<T> *Current){
	if(Current!=NULL){
		Destory(Current->lchild);
		Destory(Current->rchild);
		delete Current;  						//后序释放根结点
	}
}
template<typename T>void BinaryTree<T>::Insert(const T &data,Node<T> * &b){
	if(b==NULL){								//已到空树,插入
		b=new Node<T>(data);
		if(b==NULL){
			cout<<"空间不足"<<endl;
			exit(1);
		}
	}
	else if(data<b->info) Insert(data,b->lchild);			//小于,向左子树去查
	     else Insert(data,b->rchild);	//大于等于,向右子树去查
}
template<typename T>void BinaryTree<T>::Creat(T data){		//一步一步建立一棵搜索二叉树
	Insert(data,root);
}
template<typename T>void BinaryTree<T>::InOrder(Node<T> *Current){
	if(Current!=NULL){							//递归终止条件
		InOrder(Current->lchild);					//中序遍历左子树
		cout<<Current->info<<'t';					//访问根结点，注意所放位置
		InOrder(Current->rchild);					//中序遍历右子树
	}
}
template<typename T>int BinaryTree<T>::Countdepth(Node<T> *btree){//树深度
	int num1,num2;
	if(btree==NULL)return 0;
	else if(btree->lchild==NULL&&btree->rchild==NULL)return 1;
		else{
			num1=Countdepth(btree->lchild)+1;
			num2=Countdepth(btree->rchild)+1;
			if(num1>num2) return num1;
			else return num2;
			}
}

						