binarytree.cpp

一个数据结构实现二叉树的小程序的源码。希望能对大家有点帮助！

#include<iostream.h>

//BinaryTree 
template<class T>
struct BTNode
{
	BTNode(){lChild=rChild=NULL;}
	BTNode(const T& x)
	{
		element=x;lChild=rChild=NULL;
	}
	BTNode(const T& x,BTNode<T>*l,BTNode<T>*r)
	{
		element=x;lChild=l;rChild=r;
	}
	T element;
	BTNode<T>*lChild,*rChild;
} ;

template <class T>
void PreVisit(BTNode<T>*p)          //遍历一棵节点数
{
	if(p)
	{
		cout<<p->element<<" ";
		PreVisit(p->lChild);
		PreVisit(p->rChild);
	}
}

template<class T>
class BinaryTree
{
  public:
	  BinaryTree(){root=NULL;}
	  ~BinaryTree(){Clear();}
	  bool IsEmpty()const;                 //判断树空
	  void Clear();                        //删除一棵二叉树，释放结点空间
	  bool Root(T&x)const;                 //取树根元素
	  void MakeTree(const T&e,BinaryTree<T>&left,BinaryTree<T>& right);
	  void BreakTree(T &e,BinaryTree<T> &left,BinaryTree<T> &right);
	  void PreOrder(void(*Visit)(T&x));    //先序遍历
	  void InOrder(void(*Visit)(T&x));     //中序遍历
	  void PostOrder(void(*Visit)(T&x));   //后序遍历
	  void LayOrder(void(*Visit)(T&x));    //层次遍历
	  void Change();                   //交换树的左右孩子
	  int High();                          //计算树的高度
	  int Leaf();                          //计算叶子节点数
	  BTNode<T>*Copy();                    //复制一棵树
	  int OneSize();                       //计算度为1的结点个数
	  int Size();                          //计算所有结点个数
  protected:
	  BTNode<T> *root;
  private:
	  void Clear(BTNode<T> *t);
	  void Change(BTNode<T> *t);
	  int High(BTNode<T>*t);
	  int Leaf(BTNode<T>*t);
	  BTNode<T>*Copy(BTNode<T> *t);
	  int OneSize(BTNode<T>*t);
	  int Size(BTNode<T>*t);
	  void PreOrder(void(*Visit)(T &x),BTNode<T> *t);
	  void InOrder(void(*Visit)(T &x),BTNode<T> *t);
	  void PostOrder(void(*Visit)(T &x),BTNode<T> *t);
	  void LayOrder(void(*Visit)(T&x),BTNode<T> *t);
};

template<class T>
bool BinaryTree<T>::Root(T &x) const
{
	if(root)
	{
		x=root->element;
		return true;
	}
	else
		return false;
}

template<class T>
void BinaryTree<T>::MakeTree(const T &x,BinaryTree<T> &left,BinaryTree<T> &right)
{
	if(root||&left==&right)return;
	root=new BTNode<T>(x,left.root,right.root);
	left.root=right.root=NULL;
}

template<class T>
void BinaryTree<T>::BreakTree(T &x,BinaryTree<T> &left,BinaryTree<T> &right)
{
	if(!root||&left==&right||left.root||right.root)return;
	x=root->element;
	left.root=root->lChild;right.root=root->rChild;
	delete root;
	root=NULL;
}

template<class T>
void Visit(T& x)
{
	cout<<x<<" ";
}

template<class T>
void BinaryTree<T>::PreOrder(void(*Visit)(T &x))
{
	PreOrder(Visit,root);
}

template<class T>
void BinaryTree<T>::PreOrder(void(*Visit)(T& x),BTNode<T>* t)
{
	if(t)
	{
		Visit(t->element);
		PreOrder(Visit,t->lChild);
		PreOrder(Visit,t->rChild);
	}
}

template<class T>
void BinaryTree<T>::LayOrder(void(*Visit)(T&x))
{
	LayOrder(Visit,root);
}

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

template<class T>
void BinaryTree<T>::Clear(BTNode<T> *t)
{
	if(t)
	{
		Clear(t->rChild);
		Clear(t->lChild);
		delete t;
	}
}

template<class T>
void BinaryTree<T>::Change(BTNode<T>*t)
{
	BTNode<T>*q;
	if(t)
	{
		q=t->lChild;
		t->lChild=t->rChild;
		t->rChild=q;
		Change(t->lChild);
		Change(t->rChild);
	}
}

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

template<class T>
int BinaryTree<T>::High(BTNode<T> *t)
{
	int h,hr,hl;
	if(t)
	{
		hr=High(t->rChild);
		hl=High(t->lChild);
		h=1+((hr>hl)? hr:hl);
		return h;
	}
	else return 0;
}

template<class T>
int BinaryTree<T>::High()
{
	return	High(root);
}

template<class T>
int BinaryTree<T>::Leaf(BTNode<T> *t)
{
	if(t)
	{
		if(t->rChild||t->lChild)
			return Leaf(t->rChild)+Leaf(t->lChild);
		else 
			return 1;
	}
	else return 0;
}

template<class T>
int BinaryTree<T>::Leaf()
{
	return Leaf(root);
}

template<class T>
BTNode<T>* BinaryTree<T>::Copy(BTNode<T>*t)
{
	if(!t)
		return NULL;
	BTNode<T>*q=new BTNode<T>(t->element);
	q->lChild=Copy(t->lChild);
	q->rChild=Copy(t->rChild);
	return q;
}

template<class T>
BTNode<T>* BinaryTree<T>::Copy()
{
	return Copy(root);
}

template<class T>
int BinaryTree<T>::OneSize(BTNode<T>*t)
{
	if(t)
	{
		if(!t->lChild&&t->rChild)
			return 1+OneSize(t->rChild);
		if(t->lChild&&!t->rChild)
			return 1+OneSize(t->lChild);
		else
			return OneSize(t->lChild)+OneSize(t->rChild);
	}
	else
		return 0;
}

template<class T>
int BinaryTree<T>::OneSize()
{
	return OneSize(root);
}

template<class T>
int BinaryTree<T>::Size(BTNode<T>*t)
{
	if(t)
		return Size(t->lChild)+Size(t->rChild)+1;
	else
		return 0;
}

template<class T>
int BinaryTree<T>::Size()
{
	return Size(root);
}


void main(void)
{
	char e;
	BinaryTree<char>a,b,x,y,z,m;
	BTNode<char>*NewTreeRoot;
	y.MakeTree('E',a,b);                 /*     B      */
	z.MakeTree('F',a,b);                 /*    / \     */
	m.MakeTree('H',a,b);                 /*   D   C    */
	x.MakeTree('C',y,z);                 /*  /   / \   */
	y.MakeTree('D',m,b);                 /* H   E   F  */
	z.MakeTree('B',y,x);
	cout<<"先序遍历Z的元素为："<<endl;
	z.PreOrder(Visit);
	z.Change();                            //交换树的左右孩子
	cout<<endl<<"将Z的左右孩子转换后先序遍历得："<<endl;
	z.PreOrder(Visit);

	cout<<endl<<"Z的叶子节点数为："<<endl<<z.Leaf()<<endl;
	                                           //计算叶子节点数
	cout<<"Z的高度为："<<endl;
	cout<<z.High()<<endl;                      //计算树的高度
	cout<<"Z中总结点数为："<<endl<<z.Size()<<endl;
	                                           //计算总结点个数

	cout<<"Z中度为1的结点个数为："<<endl<<z.OneSize()<<endl;
	                                           //计算度为1的结点个数

	NewTreeRoot=z.Copy();                      //复制一棵树
	cout<<"从Z复制的新数的先序元素是："<<endl;

	PreVisit(NewTreeRoot);                     //遍历新树

	z.BreakTree(e,y,x);                        //拆树
	cout<<endl<<"拆分Z所得两棵数是："<<endl;
	x.PreOrder(Visit);
	cout<<endl;
	y.PreOrder(Visit);
	
	cout<<endl;
	
}