tree.h

顺序二叉树和树的复制及哈夫曼编码

顺序二叉树和树的复制及哈夫曼编码       网络二班
                   任文旭     41


template<class T>
class TBinTreeNode //tree node object;
{
	private:
		T info; //tree node info;
        TBinTreeNode<T> *lson,*rson,*father; //three poiters structure; 
	public:
		TBinTreeNode(){
			lson=0;
			 rson=0;
			father=0;
		}
		
		T& GetElem(){return info;}
		void SetElem(T e){info=e;}

		TBinTreeNode* GetSon(char sonNo)
		{
			if(sonNo==1) return lson;
			else         return rson;
		}
      void SetSon(char sonNo,TBinTreeNode<T>* pSon)
	   {
           if(sonNo==1)  lson=pSon;
		   else          rson=pSon;
	   }

	  void Setfather(TBinTreeNode<T>* f)
	  { father=f;}
	  TBinTreeNode<T>* Getfather()
	  {return father;}

	  bool IsLeaf()
	  {return (lson==NULL && rson==NULL);}

};

enum TTraverseMode{preorder,inorder,postorder,levelorder};

template<class T>
class TBinTree  //tree object;
{
private:
 
 long PreOrder(TBinTreeNode<T>* pNode,TBinTreeNode<T>** e);
 long InOrder(TBinTreeNode<T>* pNode,TBinTreeNode<T>** e);
 long PostOrder(TBinTreeNode<T>* pNode,TBinTreeNode<T>** e);
 long LevelOrder(TBinTreeNode<T>* pNode,TBinTreeNode<T>** e);
 TBinTreeNode<T>* CopyTree(TBinTreeNode<T>* pNode,long& n);
public:
 long numNodes;// num of nodes;
 TBinTreeNode<T>* root;// the root
 TBinTree();
 ~TBinTree();

  virtual TBinTreeNode<T>* SetRoot(TBinTreeNode<T> *rt);
  virtual TBinTreeNode<T>* GetRoot();

  virtual long GetLevel(TBinTreeNode<T>*pNode);// get the level of a node according its poiter;
  virtual long GetHeight(TBinTreeNode<T> * pNode); //get the subtree's height which root is pNode; 
  virtual long GetNumSubNodes(TBinTreeNode<T> * pNode);//get the subtree's count of nodes
  //virtual long GetNumLeaves(TBinTreeNode<T>* pNode);//get count of leaves of a subtree

  virtual void Copy(TBinTree<T>& atree);
  //cluster in different ways;
  virtual long Cluster(TBinTreeNode<T>* pNode,T** e,TTraverseMode tm);
  virtual long Cluster(TBinTreeNode<T>* pNode,TBinTreeNode<T>** e,TTraverseMode tm);
  
  virtual long ClusterAncestors(TBinTreeNode<T>* pNode,T**e); 
  virtual long ClusterAncestors(TBinTreeNode<T>* pNode,TBinTreeNode<T>** pe);

  virtual long ClusterDescendants(TBinTreeNode<T>* pNode,T** es);
  virtual long ClusterDescendants(TBinTreeNode<T>* pNode,TBinTreeNode<T>** pe);

  virtual long ClusterSeniors(TBinTreeNode<T>* pNode,TBinTreeNode<T>** pe);
  virtual long ClusterSeniors(TBinTreeNode<T>* pNode,T** es);

  virtual long ClusterJuniors(TBinTreeNode<T>* pNode,TBinTreeNode<T>** pe);
  virtual long ClusterJuniors(TBinTreeNode<T>* pNode,T** es);

  virtual long GetLeaves(TBinTreeNode<T>** e);

  virtual void DeleteSubTree(TBinTreeNode<T>* pNode,int sonNo);    //delete subtree of a pNode;
  void ReleaseAllNodes();  //

 
  virtual TBinTreeNode<T>* Locate(TBinTreeNode<T>* rt,T& e,long sn=1);

  virtual TBinTreeNode<T>* GListToTree(long * gListExp,T* es,long numElem);   //lists to tree;
  virtual long TreeToGList(TBinTreeNode<T> * rt,T* e);  // tree to lists;

  virtual TBinTreeNode<T>* PreOrderExToTree(T* nodes,int numElem);  // preorder extention to tree;
  virtual TBinTreeNode<T>* InPreToTree(T* pa ,T* ia,long p1,long p2,long i1,long i2);

  virtual void Print(TBinTreeNode<T>* rt,TTraverseMode mode=preorder);    //print the result in different mode;
};