btree.h

使用中序遍历

#include "head.h"
#include "iostream.h"

template<class T>
class BTree
{
	public:
		BTree(){root=NULL;}                
        ~BTree(){}
        bool IsEmpty()const;
        bool Root(T &x)const;
        void MakeTree(const T &e ,BTree<T>& left, BTree<T>& right); 
        void BreakTree(T &e ,BTree<T>& left,BTree<T>& right); 
       
		void PreOrder(void (*Visit)(BTNode<T>* u)) 
		{
			PreOrder(Visit,root);
		}
        void InOrder(void (*Visit)(BTNode<T>* u)) 
		{
			InOrder(Visit,root);
		}
        void PostOrder(void (*Visit)(BTNode<T>* u))
		{
			PostOrder(Visit,root);
		}
		int Size()
		{
           return Size(root);
		}
		int High()
		{
			return High(root);
		}
		void Exch()
		{
			Change(root);
		}
   private:
        BTNode<T>* root;
        void PreOrder(void (*Visit)(BTNode<T>*u), BTNode<T>*t);
        void InOrder(void (*Visit)(BTNode<T>* u), BTNode<T>*t); 
        void PostOrder(void (*Visit)(BTNode<T>* u), BTNode<T>*t);
         int Size(BTNode<T>* t);
		void Change(BTNode<T> *t);
        int High(BTNode<T>*t);
	
		
};

//判断二叉树是否为空
template<class T>
bool BTree<T>::IsEmpty() const
{
	return root==NULL;
}

//求二叉树根结点的值
template <class T>
bool BTree<T>::Root(T &x) const 
{
	if (root)
	{
		x=root->element;
		return true;
	}
	else return false;
}

//建造一棵二叉树，T为新生成树的根结点
//left,right为新生成树的左右子树
template <class T>
void BTree<T>::MakeTree(const T &e, BTree<T>& left, BTree<T>& right)
{  
	cout<<"here in BTree<T>::MakeTree"<<endl;
	if(root||&left==&right)return;
	root=new BTNode<T>(e,left.root,right.root);
	left.root=right.root=NULL;
}

//求二叉树根结点的值，
//left,right为左右两棵子树
//此处应该修改，原树root应该为空
template <class T>
void BTree<T>::BreakTree(T &e,BTree<T>&left, BTree<T>& right) 
{
	cout<<"here in BTree<T>::BreakTree."<<endl;
	if(!root||&left==&right||left.root||right.root)return;
	e=root->element;
	left.root=root->lchild;right.root=root->rchild;
	delete root;root=NULL;
}

template <class T>
void BTree<T>::PreOrder(void (*Visit)(BTNode<T>* u),BTNode<T>* t)
{ 
	if(t)
	{Visit(t);
	PreOrder(Visit,t->lchild);
	PreOrder(Visit,t->rchild);
	}
}

template <class T>
void BTree<T>::InOrder (void (*Visit)(BTNode<T>* u),BTNode<T>* t)
{ 
	if (t)
	{InOrder(Visit,t->lchild);
	 Visit(t);
     InOrder(Visit,t->rchild);
	}
}

template <class T>
void BTree<T>::PostOrder(void (*Visit)(BTNode<T>* u),BTNode<T>* t)
{ 
	if (t)
	{PostOrder(Visit,t->lchild);
	 PostOrder(Visit,t->rchild);
	 Visit(t);

	}
}


/*实现二叉树的按层遍历，用到了一个队列(第三章中的循环队列)
首先将根结点入队列，当对列不为空的时候：取队首元素，输出队首元素，
将队首元素的左右结点入队列，删除队首元素。如此循环直到队列为空。
该程序不是递归算法。
*/

template<class T>
int BTree<T>::Size(BTNode<T>* t)
{ if(!t) return 0;
  return Size(t->lchild) + Size(t->rchild) + 1;
}
template<class T>
int BTree<T>::High(BTNode<T>*t)
{if(!t) return 0;
 int h=1;
 if(t->lchild&&t->rchild)
 {	if(High(t->lchild)>=High(t->rchild))
    h=h+High(t->lchild);
 else
	 h=h+High(t->rchild);
 }

	return h;
}


template <class T>
void BTree<T>::Change(BTNode<T> *t)
{BTNode<T> *p;
	if (t)
	{p=t->lchild;
	t->lchild=t->rchild;
	t->rchild=p;
	Change(t->lchild);
	Change(t->rchild);
	}
	
	
}