binarytree.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

#ifndef BINARY_TREE
#define BINARY_TREE

#include<fstream>
#include<iostream>
#include "SeqQueue.h"
using namespace std;
template <class T> 
struct BinTreeNode {	      //二叉树结点类定义
	T data;	 		      //数据域
	BinTreeNode<T> *leftChild, *rightChild;
	//左子女、右子女链域
	BinTreeNode ()                //构造函数
	{ leftChild = NULL;  rightChild = NULL; }
	BinTreeNode (T x, BinTreeNode<T> *l = NULL,  
		BinTreeNode<T> *r = NULL)
	{ data = x;  leftChild = l;  rightChild = r; }
};

template <class T> 
class BinaryTree {		//二叉树类定义
public:
	BinaryTree () : root (NULL) { }	  //构造函数
	BinaryTree (T value) : RefValue(value), root(NULL) 
	{ }					  //构造函数
	BinaryTree(BinTreeNode<T> * p,T value) {
		root = p;
		RefValue = value;
	}
	BinaryTree (BinaryTree<T>& s){    //复制构造函数
		if (this != &s){
			root=Copy(s.root);
		}
	}
	~BinaryTree () { destroy(root); }	  //析构函数
	bool IsEmpty () { return root == NULL;}
	//判二叉树空否
	//二叉树查找
	bool Find ( T& x){ return Find(root,x); }
	int Height () { return Height(root); }  //求树高度
	int Size () { return Size(root); }	    //求结点数
	BinTreeNode<T> *Parent (BinTreeNode <T> *t)  
	{ return (root == NULL || root ==  t) ?NULL : Parent (root, t); }    //返回双亲结点
	BinTreeNode<T> *LeftChild (BinTreeNode<T> *t)
	{ return (t != NULL)? t->leftChild : NULL; }
	//返回左子女
	BinTreeNode<T> *RightChild (BinTreeNode<T> *t)
	{ return (t != NULL)? t->rightChild : NULL; }  
	//返回右子女
	BinTreeNode<T> *getRoot () const { return root; }
	//取根
	void PreOrder (void (*visit) (BinTreeNode<T> *t))  
	{ PreOrder (root, visit); }           //前序遍历
	void InOrder (void (*visit) (BinTreeNode<T> *t))
	{ InOrder (root, visit); }             //中序遍历
	void PostOrder (void (*visit) (BinTreeNode<T> *t))
	{ PostOrder (root, visit); }         //后序遍历
	void levelOrder (void (*visit)(BinTreeNode<T> *t));	                                                //层次序遍历
	int Insert (const T item);	       //插入新元素	
protected:
	BinTreeNode<T> *root; 	//二叉树的根指针
	T RefValue;	 		//数据输入停止标志
	void CreateBinTree (ifstream& in,  BinTreeNode<T> *& subTree);
	bool Insert (BinTreeNode<T> *& subTree,  T& x);	                                       //插入
	void destroy (BinTreeNode<T> *& subTree) ;
	//查找	
	bool Find (BinTreeNode<T> *subTree, T& x)const;
	BinTreeNode<T> *Copy (BinTreeNode<T> *r);		                                  //复制
	int Height (BinTreeNode<T> *subTree) const ;		                    
	int Size (BinTreeNode<T> *subTree)const;
	//返回父结点
	BinTreeNode<T> *Parent (BinTreeNode<T> *    subTree, BinTreeNode<T> *t);

	void PreOrder (BinTreeNode<T>* subTree, 
		void (*visit) (BinTreeNode<T> *t));
	void InOrder (BinTreeNode<T>* subTree, 
		void (*visit) (BinTreeNode<T> *t));
	void PostOrder (BinTreeNode<T>* subTree, 
		void (*visit) (BinTreeNode<T> *t));
	friend ifstream& operator >> (ifstream& in,  
		BinaryTree<T>& Tree){
			//重载操作: 输入并建立一棵二叉树Tree。in是输
			//入流对象。
			Tree.CreateBinTree (in, Tree.root); 	//建立二叉树
			return in;
	};
};

template <class T>
void BinaryTree<T>::CreateBinTree (ifstream& in,  BinTreeNode<T> *& subTree){
	//私有函数: 以递归方式建立二叉树。
	T item;
	if ( !in.eof () ) {	    	//未读完, 读入并建树	
		in >> item;  		//读入根结点的值
		if (item != RefValue) {
			subTree = new BinTreeNode<T>(item);
			//建立根结点
			if (subTree == NULL) 
			{cerr <<"存储分配错!" << endl;  exit (1);}
			CreateBinTree (in, subTree->leftChild);	//递归建立左子树
			CreateBinTree (in, subTree->rightChild); //递归建立右子树
		}
		else subTree = NULL;						    //封闭指向空子树的指针
	}
};

//插入
template<class T>
bool BinaryTree<T>::Insert (BinTreeNode<T> *& subTree,  T& x){
	if (!subTree){
		subTree=new BinTreeNode<T>(x);
		if (!subTree)
		{cerr <<"存储分配错!" << endl;  exit (1);}
	}
	Insert (subTree->leftChild);
	Insert (subTree->rightChild);
}

//查找
template<class T>
bool BinaryTree<T>::Find (BinTreeNode<T> *subTree, T& x)const{
	if (!subTree) 
		return false;
	if (subTree->data==x)
		return true;
	bool p=false;
	p = Find(subTree->leftChild,x); 
	if (p)  
		return true;	         //递归在左子树中搜索
	else return Find (subTree->rightChild, x);
};

//复制
template<class T>
BinTreeNode<T> *BinaryTree<T>::Copy (BinTreeNode<T> *r){ 
	 if(!r)
		 return NULL;
	 BinTreeNode<T> *p=new BinTreeNode<T>(r->data);
	 p->leftChild = Copy(r->leftChild);
	 p->rightChild = Copy(r->rightChild);
	 return p;
}




template <class T> 
void BinaryTree<T>::destroy (BinTreeNode<T> *& subTree){
	//私有函数: 删除根为subTree的子树
	if (subTree != NULL) {
		destroy (subTree->leftChild);     //删除左子树
		destroy (subTree->rightChild);   //删除右子树
		delete subTree; 			 //删除根结点
	}
};	

template <class T> 
int BinaryTree<T>::Height (BinTreeNode<T> *subTree) const{
	//私有函数：利用二叉树后序遍历算法计算二叉
	//树的高度或深度
	if (subTree == NULL) return 0;	//空树高度为0
	else {
		int i = Height (subTree->leftChild);
		int j = Height (subTree->rightChild);
		return (i < j) ? j+1 : i+1; 
	}
};		 



template <class T> 
int BinaryTree<T>::Size (BinTreeNode<T> *subTree)const{       //返回结点数
	//私有函数：利用二叉树后序遍历算法计算二叉
	//树的结点个数
	if (subTree == NULL) return 0;	       //空树
	else return 1+Size (subTree->leftChild) 
		+ Size (subTree->rightChild);
};


template <class T> 
BinTreeNode<T> *BinaryTree<T>::Parent (BinTreeNode<T> *    subTree, BinTreeNode<T> *t) {
	//私有函数: 从结点 subTree 开始, 搜索结点 t 的双
	//亲, 若找到则返回双亲结点地址, 否则返回NULL
	if (subTree == NULL) return NULL;
	if (subTree->leftChild == t || 
		subTree->rightChild == t ) 
		return subTree;	//找到, 返回父结点地址
	BinTreeNode <T> *p;
	if ((p = Parent (subTree->leftChild, t)) != NULL)  
		return p;	         //递归在左子树中搜索
	else return Parent (subTree->rightChild, t);
	//递归在左子树中搜索
};			


template <class T> 
void BinaryTree<T>::PreOrder (BinTreeNode<T>* subTree, void (*visit) (BinTreeNode<T> *t)){
	if (subTree != NULL) {
		visit (subTree);		//访问根结点
		PreOrder (subTree->leftChild, visit);
		//遍历左子树
		PreOrder (subTree->rightChild, visit);
		//遍历右子树
	}
};
template <class T> 
void BinaryTree<T>::InOrder (BinTreeNode<T>* subTree, void (*visit) (BinTreeNode<T> *t)){
	if (subTree != NULL) {
		InOrder (subTree->leftChild, visit); 
		//遍历左子树
		visit (subTree);		//访问根结点
		InOrder (subTree->rightChild, visit);
		//遍历右子树
	}
};


template <class T> 
void BinaryTree<T>::PostOrder (BinTreeNode<T>* subTree, void (*visit) (BinTreeNode<T> *t)){
	if (subTree != NULL ) {
		PostOrder (subTree->leftChild, visit);		
		//遍历左子树
		PostOrder (subTree->rightChild, visit);		                                        //遍历右子树
		visit (subTree);	         //访问根结点
	}
};
template <class T>
void BinaryTree<T>::levelOrder (void (*visit) (BinTreeNode<T> *t)) {
	if (root == NULL) return;
	SeqQueue<BinTreeNode<T> * > Q;
	BinTreeNode<T> *p = root;   
	visit (p);   Q.EnQueue (p); 	
	while (!Q.IsEmpty ()) {
		Q.DeQueue (p);
		if (p->leftChild != NULL) {              
			visit (p->leftChild);
			Q.EnQueue (p->leftChild);
		}
		if (p->rightChild != NULL) {
			visit (p->rightChild);
			Q.EnQueue (p->rightChild);
		}
	}
};




#endif