cbintree.h

数据结构二叉树的功能实现, 比如在二叉搜索树上查找或者删除一个结点。

#include "iostream.h"
#include "stdlib.h"
#include "..\CircularQ\CircularQueue.h"

template<class T>
struct BinTreeNode
{
	T data;
	BinTreeNode<T> *leftchild,*rightchild;
	BinTreeNode():leftchild(NULL),rightchild(NULL){};
	BinTreeNode(T value):data(value),leftchild(NULL),rightchild(NULL){};
};

template<class T>
class BinTree
{
	T RefValue;
	BinTreeNode<T> *root;
public:
	BinTree():root(NULL){}
	BinTree(T value);
	BinTree(BinTreeNode<T> *t,BinTreeNode<T> *p);
	~BinTree(){Destroy(root);}
	BinTreeNode<T>* GetTop(){return root;}
	void Destroy(BinTreeNode<T> *subtree);
	bool Insert(const T& t,BinTreeNode<T> *&p);
	void InOrder(BinTreeNode<T> *p);
	void LevelOrder(BinTreeNode<T> *p);
	void LeafSize(BinTreeNode<T> *p,int &i);
	void OffsetSize(BinTreeNode<T> *p,int &i);
	int Height(BinTreeNode<T> *p)const;
	BinTreeNode<T>* Search(const T x,BinTreeNode<T> *p);//---------------此函数是这次作业新增的函数！
	bool Remove(const T x,BinTreeNode<T> *&p);//--------------------------同上！是新增函数！
};

template<class T>
BinTree<T>::BinTree(T value)
{
	T x;
	root=NULL;
	RefValue=value;
	cout<<"The Refvalue is -1."<<endl;
	cout<<"Input a node:";
	cin>>x;
	while (x!=RefValue)
	{
		Insert(x,root);
		cout<<"Input a node again:";
		cin>>x;
	}
}

template<class T>
void BinTree<T>::Destroy(BinTreeNode<T>* subtree)
{
	if(subtree!=NULL)
	{
		Destroy(subtree->leftchild);
		Destroy(subtree->rightchild);
		delete subtree;
	}
	return;
}

template<class T>
BinTree<T>::BinTree(BinTreeNode<T> *t,BinTreeNode<T> *p)
{
	if(t)
	{
		p=new BinTreeNode<T>;
		p->data=t->data;
		BinTree(t->leftchild,p->leftchild);
		BinTree(t->rightchild,p->rightchild);
	}
}

template<class T>
bool BinTree<T>::Insert(const T& t,BinTreeNode<T> *&p)
{
	if(p==NULL)
	{
		p=new BinTreeNode<T>(t);
		if(p==NULL)
		{
			cerr<<"Out of space!"<<endl;
			exit(1);
		}
		return true;
	}
	else if(t<p->data) Insert(t,p->leftchild);
	else if(t>p->data) Insert(t,p->rightchild);
	else return false;
}

template<class T>
void BinTree<T>::InOrder(BinTreeNode<T> *p)
{
	if(p)
	{
		InOrder(p->leftchild);
		cout<<p->data<<" ";
		InOrder(p->rightchild);
	}
	return;
}	

template<class T>
void BinTree<T>::LevelOrder(BinTreeNode<T> *p)
{
	 CircularQueue<BinTreeNode<T>*> Q(20);
	 Q.EnQueue(p);
	 while (!Q.IsEmpty())
	 {
		 Q.DeQueue(p);
		 cout<<p->data<<" ";
		 if(p->leftchild) Q.EnQueue(p->leftchild);
		 if(p->rightchild) Q.EnQueue(p->rightchild);
	 }
	 return;
}

template<class T>
void BinTree<T>::LeafSize(BinTreeNode<T> *p,int &i)
{
	if(p&&p->leftchild==NULL&&p->rightchild==NULL) i++;
	if(p)
	{
		LeafSize(p->leftchild,i);
		LeafSize(p->rightchild,i);
	}
	return;
}

template<class T>
void BinTree<T>::OffsetSize(BinTreeNode<T> *p,int & i)
{
	if (p->leftchild)
	{
		if(p->leftchild->leftchild||p->leftchild->rightchild)
		{
			i++;
			OffsetSize(p->leftchild,i);
		}
	}
	if (p->rightchild)
	{
		if(p->rightchild->leftchild||p->rightchild->rightchild)
		{
			i++;
			OffsetSize(p->rightchild,i);
		}		
	}
	return ;
}

template<class T>
int BinTree<T>::Height(BinTreeNode<T> *p)const
{
	if(p==NULL) return 0;
	int i=Height(p->leftchild);
	int j=Height(p->rightchild);
	return (i<j)? j+1:i+1;
}

template<class T>
BinTreeNode<T>* BinTree<T>::Search(const T x,BinTreeNode<T> *p)//------------------这是新增查找函数的实现~
{
	if(p==NULL) return NULL;
	else if(x<p->data) return Search(x,p->leftchild);
	else if(x>p->data) return Search(x,p->rightchild);
	else return p;
}

template<class T>
bool BinTree<T>::Remove(const T x,BinTreeNode<T> *&p)//-----------------------------这是新增删除函数的实现~
{
	BinTreeNode<T> *temp;
	if (p)
	{
		if(x<p->data) Remove(x,p->leftchild);
		else if(x>p->data) Remove(x,p->rightchild);
		else if(p->leftchild&&p->rightchild)
		{
			temp=p->rightchild;
			while(temp->leftchild) temp=temp->leftchild;
			p->data=temp->data;
			Remove(p->data,p->rightchild);
		}
		else
		{
			temp=p;
			if(p->leftchild==NULL) p=p->rightchild;
			else p=p->leftchild;
			delete temp;
			return true;
		}
	}
	if(p==NULL)
		return false;
}