binarytree.h

一个数据结构

//程序5.2二叉树类
#include "BTNode.h"
#include "SeqQueue.h"

template<class T>
class BinaryTree
{
  public:
   BinaryTree(){ root=NULL; n=0; nn=0; nnn=0; }                
   ~BinaryTree(){Clear();}
   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));
   int Size();                              //求二叉树中结点的个数
   int Size1();                             //求二叉树中结点的个数，方法二
   int Size2();                             //求二叉树的分支结点数
   int Size3();                             //求度为1的结点个数
   int Node0();                             //求度为0的结点(叶结点)个数
   int Node1();                             //求度为1的结点个数
   int Node2();                             //求度为2的结点个数
   void Copy(BinaryTree<T>& atree);
   void Create();                           //建立二叉树
   int Leaves();                            //求叶结点的个数
   int Height();                            //求二叉树的高度
   void Change();                           //交换二叉树的左右子树
   void Copy_Change(BinaryTree<T>& tree);   //二叉树复制,并交换所有结点的左右子树
   void Path();                             //二叉树根到所有叶结点的路径
   void Path_p(T node);                     //二叉树根到指定结点p的路径
   void Max_Path();                         //求二叉树最长根路径
   T Ancestor(T pnode,T qnode);             //找p和q最近的共同祖先(假设p在q的左边)
   void hierarchical();                     //层次遍历
   bool Expand_Btree();                           //判断二叉树是否是扩充二叉树（2-树）

 protected:
   BTNode<T>* root;
 private:
   void Clear(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);     
   int Size(BTNode<T> *t);
   void Size1(BTNode<T> *t);
   void Size2(BTNode<T> *t);
   void Size3(BTNode<T> *t);
   int Node0(BTNode<T> *t); 
   int Node1(BTNode<T> *t);                             
   int Node2(BTNode<T> *t);                             
   BTNode<T>* Copy(BTNode<T> *t);
   BTNode<T>* Create(ifstream fin);
   void Leaves(BTNode<T> *t, int &count);
   int Height(BTNode<T> *t);  
   void Change(BTNode<T>*t); 
   BTNode<T>* Copy_Change(BTNode<T>* t);
   void Path(BTNode<T>* t,T ch[],int nn);
   void Path_p(BTNode<T>* t, T node, T ch[], int nn);
   void Max_Path(BTNode<T>*t,T ch[],int h, T max_ch[], int &max);
   void Ancestor(BTNode<T>* t, T pnode, T qnode, T stackp[], int &topp, T stackq[], int topq,T &anc);
   bool Expand_Btree(BTNode<T> *t); 
   int n;                   //二叉树结点个数
   int nn;                  //二叉树分支结点个数
   int nnn;                 //二叉树度为1的结点个数
};

 
//程序5.3 部分二叉树运算
template <class T>
void BinaryTree<T>::Clear()
{ Clear(root);
}

template <class T>
void BinaryTree<T>::Clear(BTNode<T>* t)
{ if(t)
	{  Clear(t->lChild);
       Clear(t->rChild);
       delete 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>::InOrder(void (*Visit)(T& x))
{ InOrder(Visit,root);
}

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

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

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

//程序5.7 求二叉树的结点数
template <class T>
int BinaryTree<T>::Size()
{ 
  return Size(root);
}

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

//求二叉树的结点数，方法二
template <class T>
int BinaryTree<T>::Size1()
{ Size1(root);
  return n;
}

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

template <class T>
int BinaryTree<T>::Size2()            //求二叉树的分支结点数
{ Size2(root);
  return nn;
}

template <class T>
void BinaryTree<T>::Size2(BTNode<T> *t)   
{
  if (t) 
  { if(t->lChild!=0||t->rChild!=0) nn++;
    Size2(t->lChild);
    Size2(t->rChild);
  }
}

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

template <class T>
void BinaryTree<T>::Size3(BTNode<T> *t)   //求二叉树度为1的结点数
{
  if (t) 
  { if((t->lChild==0&&t->rChild!=0)||(t->lChild!=0&&t->rChild==0)) nnn++;
    Size3(t->lChild);
    Size3(t->rChild);
  }
}

template<class T>
int BinaryTree<T>::Leaves()
{ int count = 0;
  Leaves(root, count);
  return count;
}

template <class T>
void BinaryTree<T>::Leaves(BTNode<T> *t, int &count)	
{ if(t)   
	{ if(!t->lChild&&!t->rChild) count++;				
	  Leaves(t->lChild, count);												
	  Leaves(t->rChild, count);										
	}
}

/********************求度为0的结点个数********************/
template<class T>
int BinaryTree<T>::Node0()
{
	return Node0(root);
}

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

/********************求度为1的结点个数********************/
template<class T>
int BinaryTree<T>::Node1()
{
	return Node1(root);
}

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

/********************求度为2的结点个数********************/
template<class T>
int BinaryTree<T>::Node2()
{
	return Node2(root);
}

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

//程序5.8 二叉树复制
template <class T>
void BinaryTree<T>::Copy(BinaryTree<T>& tree)
{  tree.root=Copy(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>
void BinaryTree<T>::Create()          //建立二叉树
{ ifstream fin("BinaryTree.txt");
  if(!fin)
  {	 cout<<"can not open!";
	   return;
  } 
  root=Create(fin);
  fin.close();
}

template<class T>
BTNode<T>* BinaryTree<T>::Create(ifstream fin)  //下面的二叉树，按先序输入：a b d h ^ ^ i^ ^ e ^ j ^ ^ c f ^ ^ g ^ ^
{ BTNode<T> *t;
  T ch;  
                                         //              a
  fin>>ch;                               //            /   \        
  if(ch=='^') return NULL;               //           b     c        
  else                                   //          / \   / \      
  { t=new BTNode<T>;                     //         d   e f   g  
    t->element=ch;                       //        / \   \ 
    t->lChild=Create(fin);               //       h   i   j 
    t->rChild=Create(fin);
  }
  return t;
}

template<class T>
int BinaryTree<T>::Height()                    //求二叉树的高度
{ return Height(root);
}

template<class T>
int BinaryTree<T>::Height(BTNode<T>*t)         //二叉树的高度
{	int hl,hr;
	if(t==NULL) return 0;
	else
	{	hl=Height(t->lChild);
		hr=Height(t->rChild);
    return hl>hr?hl+1:hr+1;
	}
}

template<class T>
void BinaryTree<T>::Change()              //交换二叉树的左右子树
{ Change(root);
}

template<class T>
void BinaryTree<T>::Change(BTNode<T>*t)   //交换二叉树的左右子树
{	if(t)
	{	BTNode<T> *p;                    
		p=t->lChild;                      
		t->lChild=t->rChild;          
		t->rChild=p;                 
		Change(t->lChild);         
		Change(t->rChild);
	}
}

template <class T>
void BinaryTree<T>::Copy_Change(BinaryTree<T>& tree)    //二叉树复制,并交换所有结点的左右子树
{  tree.root=Copy_Change(root);
}

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

template <class T>
void BinaryTree<T>::Path()                              //二叉树根到所有叶结点的路径   
{ T ch[10];  int nn=0; 
  Path(root,ch,nn);
}

template <class T>
void BinaryTree<T>::Path(BTNode<T>* t, T ch[],int nn)
{ 
  if(!t) return;
  ch[nn++]=t->element;
  if(!t->lChild&&!t->rChild)
  { for(int i=0; i<nn; i++) cout<<ch[i]<<" ";
    cout<<endl;
	return;
  }
  Path(t->lChild,ch,nn);
  Path(t->rChild,ch,nn);
}

template <class T>
void BinaryTree<T>::Path_p(T node)                 //二叉树根到指定结点p的路径   
{ T ch[10];  int nn=0; 
  Path_p(root,node,ch,nn);
}

template <class T>
void BinaryTree<T>::Path_p(BTNode<T>* t, T node, T ch[], int nn)
{ 
  if(!t) return;
  ch[nn++]=t->element;
  if(t->element==node)
  { for(int i=0; i<nn; i++) cout<<ch[i]<<" ";
    cout<<endl;
	  return;
  }
  Path_p(t->lChild,node,ch,nn);
  Path_p(t->rChild,node,ch,nn);
}

template<class T>
void BinaryTree<T>::Max_Path()    //现定义二叉树中结点X0的根路径为从根结点到X0结点的一条路径，
{   int max=0,h=0;                //请编写算法输出该二叉树中最长的根路径(多条最长根路径中只输出一条即可)
    T ch[10],max_ch[10];
	Max_Path(root,ch,h,max_ch,max); 
	
	cout<<"max="<<max<<endl;
	for(int i=0;i<max;i++) cout<<max_ch[i]<<" ";
	cout<<endl;
}

template<class T>
void BinaryTree<T>::Max_Path(BTNode<T>*t,T ch[],int h, T max_ch[], int &max) //求二叉树最长根路径
{	if(!t)
	{ if(h>max)
		{ max=h; 
		  for(int i=0; i<max; i++) max_ch[i]=ch[i];
		}
	}
  else
	{  ch[h++]=t->element;                         //先序
	   Max_Path(t->lChild,ch,h,max_ch,max);
	   Max_Path(t->rChild,ch,h,max_ch,max);
	   h--;                                        //回退一层
	}
}

template <class T>
T BinaryTree<T>::Ancestor(T pnode,T qnode)      //找p和q最近的共同祖先(假设p在q的左边)
{ T anc;
  T stackp[10];  int topp;                      //未考虑找不到p,q以及空二叉树的情形
  T stackq[10];  int topq=-1;
  Ancestor(root,pnode,qnode,stackp,topp,stackq,topq,anc);
  return anc;
}

template <class T>
void BinaryTree<T>::Ancestor(BTNode<T>* t, T pnode, T qnode, T stackp[], int &topp, T stackq[], int topq,T &anc)
{ if(!t) return;
  stackq[++topq]=t->element;
  if(t->element==pnode)
  { topp=topq;
    for(int i=0; i<=topp; i++) stackp[i]=stackq[i];
  }
  if(t->element==qnode)
  { for(int i=0,j=0; stackp[i]==stackq[j]; i++,j++);
    anc=stackp[i-1];
    return;
  }
  Ancestor(t->lChild,pnode,qnode,stackp,topp,stackq,topq,anc);
  Ancestor(t->rChild,pnode,qnode,stackp,topp,stackq,topq,anc);
}

template<class T>
void BinaryTree<T>::hierarchical()
{  BTNode<T>* t=root;
   SeqQueue<BTNode<T>*> q(20);
   
   if(t)
   { q.EnQueue(t);
     while (!q.IsEmpty())
     { q.Front(t);  q.DeQueue();
       Visit(t->element);
       if(t->lChild) q.EnQueue(t->lChild);
	     if(t->rChild) q.EnQueue(t->rChild);
     }
   }
}

template<class T>
bool BinaryTree<T>::Expand_Btree()
{ return Expand_Btree(root);
}

template<class T>
bool BinaryTree<T>::Expand_Btree(BTNode<T> *t)
{ if(!t) return true;
  if(!t->lChild&&t->rChild||t->lChild&&!t->rChild) return false;
  return Expand_Btree(t->lChild)&&Expand_Btree(t->rChild);
}


/*
template<class T>
class HuffTree<T>::BinaryTree
{
  public:
   BinaryTree(){ root=NULL; }
   ~BinaryTree(){Clear();}

   void Path_Length(T& x));

// protected:
  // BTNode<T>* root;
 private:
   void PreOrder(void (*Visit)(T& x),BTNode<T>*t);
   int weight;
};
*/