binarytree.h

非常完美地二叉搜索树模板～～～～ 希望大家能够喜欢

#ifndef BINARY_TREE_CLASS
#define BINARY_TREE_CLASS

#include "BinTreeNode.h"
#include "Stack.h"
#include "Queue.h"

template <class T>
class BinaryTree
{
public:
	BinaryTree():root(NULL){}
	BinaryTree(T value);
	virtual ~BinaryTree();
	void DeleteTree(BinTreeNode<T> *);
	void Insert(const T & x,BinTreeNode<T> * & ptr);
	BinTreeNode<T> *Search(const T & item,BinTreeNode<T> *t);
	void Remove(const T & item,BinTreeNode<T> *&t);
	void PreOrder();
	void PreOrder(BinTreeNode<T> *current);                 
	void PreOrdering();                                                                  
	void InOrder();
	void InOrder(BinTreeNode<T> *current);
	void InOrdering();                                      
	void PostOrder();
	void PostOrder(BinTreeNode<T> *current);
	void PostOrdering();
	void LevelScan(BinTreeNode<T> *current);
	void LevelScan();
	void PrintTree(BinTreeNode<T>*,int level);
	int CountNode(BinTreeNode<T> *t);
	int CountD1Node(BinTreeNode<T> *t);
	int CountD2Node(BinTreeNode<T> *t);
	void CountLeaf(BinTreeNode<T> *t,int & count);
	int Depth(BinTreeNode<T> *t);
	void Min(BinTreeNode<T> *t,T & item);
	void Max(BinTreeNode<T> *t,T & item);
	BinTreeNode<T> *Min(BinTreeNode<T> *t);
	BinTreeNode<T> *Max(BinTreeNode<T> *t);
	BinTreeNode<T> *Copy(BinTreeNode<T> *t);
	bool Equal(BinTreeNode<T> *a,BinTreeNode<T> *b);
	void Exchange(BinTreeNode<T> *t);
	BinTreeNode<T> * & Root(){return root;}

private:
	BinTreeNode<T> *root;
	T RefValue;
};

template <class T>
BinaryTree<T>::BinaryTree(T value)
{
	T x;
	root=NULL;
	RefValue=value;
	cin>>x;
	while(x!=RefValue)
	{
		Insert(x,root);
		cin>>x;
	}
}

template <class T>
BinaryTree<T>::~BinaryTree()
{
	DeleteTree(root);
}

template <class T>
void BinaryTree<T>::DeleteTree(BinTreeNode<T> *t)
{
	if(t!=NULL)
	{
		DeleteTree(t->left);
		DeleteTree(t->right);
		delete t;
	}
}

template <class T>
void BinaryTree<T>::Insert(const T & x,BinTreeNode<T> * & ptr)
{
	
	if(ptr==NULL)
	{
		ptr=new BinTreeNode<T>(x);
		if(ptr==NULL)
		{
			cout<<"Invalid space!"<<endl;
			exit(1);
		}
	}
	else if(x<ptr->data) Insert(x,ptr->left);
	else if(x>ptr->data) Insert(x,ptr->right);
}

template <class T>
BinTreeNode<T>* BinaryTree<T>::Search(const T &item,BinTreeNode<T> *t)
{
	if(t==NULL)
		return NULL;
	else if(item<t->data) Search(item,t->left);
	else if(item>t->data) Search(item,t->right);
	return t;
}

template <class T>
void BinaryTree<T>::Remove(const T &item,BinTreeNode<T> * &t)
{
	BinTreeNode<T> *temp;
	if(t!=NULL)
		if(item<t->data) Remove(item,t->left);
		else if(item>t->data) Remove(item,t->right);
		else if(t->left!=NULL&&t->right!=NULL)
		{
			temp=Min(t->right);
			t->data=temp->data;
			Remove(t->data,t->right);
		}
		else
		{
			temp=t;
            if(t->left==NULL) t=t->right;
			else if(t->right==NULL) t=t->left;
			delete temp;
		}
}

template <class T>
void BinaryTree<T>::InOrder()
{
	InOrder(root);
}

template <class T>
void BinaryTree<T>::InOrder(BinTreeNode<T> *current)
{
	if(current!=NULL)
	{
		InOrder(current->left);
		cout<<current->data;
		InOrder(current->right);
	}
}

template <class T>
void BinaryTree<T>::InOrdering()
{
	BinTreeNode<T> *p;
	Stack<BinTreeNode<T>* >S;
	p=root;
	while(p!=NULL||!S.IsEmpty())
	{
		if(p!=NULL)
		{
			S.Push(p);
			p=p->left;
		}
		else
		{
			p=S.Pop();
			cout<<p->data;
			p=p->right;
		}
	}
}

template <class T>
void BinaryTree<T>::PreOrder()
{
	PreOrder(root);
}

template <class T>
void BinaryTree<T>::PreOrder(BinTreeNode<T> *current)
{
	if(current!=NULL)
	{
		cout<<current->data;
		PreOrder(current->left);
		PreOrder(current->right);
	}
}

template <class T>
void BinaryTree<T>::PreOrdering()
{
	BinTreeNode<T> *p;
	Stack<BinTreeNode<T>* >S;
	S.Push(root);
	while(!S.IsEmpty()&&root!=NULL)
	{
		p=S.GetTop();
		S.Pop();
		cout<<p->data;
		if(p->right!=NULL) S.Push(p->right);
		if(p->left!=NULL) S.Push(p->left);
	}
}

template <class T>
void BinaryTree<T>::PostOrder()
{
	PostOrder(root);
}

template <class T>
void BinaryTree<T>::PostOrder(BinTreeNode<T> *current)
{
	if(current!=NULL)
	{
		PostOrder(current->left);
		PostOrder(current->right);
		cout<<current->data;
	}
}

template <class T>
void BinaryTree<T>::PostOrdering()
{
	Stack<BinTreeNode<T>* >S1;
	Stack<int> S2;
	BinTreeNode<T> *p;
	p=root;
	while(p!=NULL||!S1.IsEmpty())
	{
		while(p!=NULL)
		{
			S1.Push(p);
			p=p->left;
			S2.Push(0);
		}
		while(!S2.IsEmpty()&&S2.GetTop()==1)
		{
			cout<<S1.Pop()->data;
			S2.Pop();
		}
		if(!S2.IsEmpty())
		{
			S2.Pop();
			S2.Push(1);
			p=S1.GetTop()->right;
		}
	}
}

template <class T>
void BinaryTree<T>::LevelScan()
{
	LevelScan(root);
}

template <class T>
void BinaryTree<T>::LevelScan(BinTreeNode<T> *current)
{
	Queue<BinTreeNode<T> *> Q;
	BinTreeNode<T> *p;
	Q.EnQueue(current);
	while(Q.DeQueue(p)&&p!=NULL)
	{
		cout<<p->data;
		if(p->left!=NULL)
			Q.EnQueue(p->left);
		if(p->right!=NULL)
			Q.EnQueue(p->right);
	}
}

const int indentBlock=6;
void blank(int n)
{
	for(int i=0;i<n;i++)
		cout<<' ';
}

template <class T>
void BinaryTree<T>::PrintTree(BinTreeNode<T>*t,int level)
{
	if(t!=NULL)
	{
		PrintTree(t->right,level+1);
		blank(indentBlock* level);
		cout<<t->data<<endl;
		PrintTree(t->left,level+1);
	}
}

template <class T>
int BinaryTree<T>::CountNode(BinTreeNode<T> *t)
{
	if(t==NULL)
		return 0;
	if(t->left==NULL&&t->right==NULL)
		return 1;
	else
		return 1+CountNode(t->left)+CountNode(t->right);
}

template <class T>
void BinaryTree<T>::CountLeaf(BinTreeNode<T> *t,int & count)
{
	if(t!=NULL)
	{
		CountLeaf(t->left,count);
		CountLeaf(t->right,count);
		if(t->left==NULL&&t->right==NULL)
			count++;
	}
}

template <class T>
int BinaryTree<T>::CountD1Node(BinTreeNode<T> *t)
{
	if(t==NULL)
		return 0;
	else if(t->left==NULL&&t->right!=NULL)
		return 1+CountD1Node(t->right);
	else if(t->right==NULL&&t->left!=NULL)
		return 1+CountD1Node(t->left);
	else
		return CountD1Node(t->left)+CountD1Node(t->right);
}

template <class T>
int BinaryTree<T>::CountD2Node(BinTreeNode<T> *t)
{
	if(t==NULL)
		return 0;
	int num=CountD2Node(t->left)+CountD2Node(t->right);
	if(t->left!=NULL&&t->right!=NULL)
		return 1+num;
	else
		return num;
}

template <class T>
int BinaryTree<T>::Depth(BinTreeNode<T> *t)
{
	int depthLeft,depthRight,depthval;
	if(t==NULL)
		depthval=-1;
	else
	{
		depthLeft=Depth(t->left);
		depthRight=Depth(t->right);
		depthval=1+(depthLeft>depthRight?depthLeft:depthRight);
	}
	return depthval;
}

template <class T>
void BinaryTree<T>::Min(BinTreeNode<T> *t,T &item)
{
	if(t!=NULL)
	{
		Min(t->left,item);
		Min(t->right,item);
		if(t->data<item)
			item=t->data;
	}
}

template <class T>
void BinaryTree<T>::Max(BinTreeNode<T> *t,T &item)
{
	if(t!=NULL)
	{
		Max(t->left,item);
		Max(t->right,item);
		if(t->data>item)
			item=t->data;
	}
}

template <class T>
BinTreeNode<T>* BinaryTree<T>::Min(BinTreeNode<T> * t)
{
	BinTreeNode<T> *temp;
	while(t!=NULL)
	{
		temp=t;
		t=t->left;
	}
	return temp;
}

template <class T>
BinTreeNode<T>* BinaryTree<T>::Max(BinTreeNode<T> *t)
{
	BinTreeNode<T> *temp;
	while(t!=NULL)
	{
		temp=t;
		t=t->right;
	}
}

template <class T>
BinTreeNode<T>* BinaryTree<T>::Copy(BinTreeNode<T> *t)
{
	if(t==NULL)
		return NULL;
	BinTreeNode<T> *temp=new BinTreeNode<T>(t->data);
	Copy(t->left);
	Copy(t->right);
	return temp;
}

template <class T>
bool BinaryTree<T>::Equal(BinTreeNode<T> *a,BinTreeNode<T> *b)
{
	if(a==NULL&&b==NULL)
		return true;
	else if(a!=NULL&&b!=NULL&&a->data==b->data
		&&Equal(a->left,b->left)
		&&Equal(a->right,b->right))
		return true;
	return false;
}

template <class T>
void BinaryTree<T>::Exchange(BinTreeNode<T> *t)
{
	BinTreeNode<T> *temp;
	if(t!=NULL)
	{
		temp=t->left;
		t->left=t->right;
		t->right=temp;
		Exchange(t->left);
		Exchange(t->right);
	}
}

#endif