?? tree.cpp
字號:
順序二叉樹和樹的復制及哈夫曼編碼
網絡二班 任文旭 41
#include "Tree.h"
#include<stdlib.h>
#include<iostream.h>
template<class T>
TBinTree<T>::TBinTree()
{
root=NULL;
numNodes=0;
}
template<class T>
TBinTree<T>::~TBinTree()
{
ReleaseAllNodes();
}
template<class T>
TBinTreeNode<T>* TBinTree<T>::SetRoot(TBinTreeNode<T> *rt)
{
root=rt;
return root;
}
template<class T>
TBinTreeNode<T>* TBinTree<T>::GetRoot()
{
return root;
}
/////////////////////////////////////////////////////////////////////////////
template<class T>
long TBinTree<T>::GetLevel(TBinTreeNode<T>* pNode)//獲得節點層號
{
long level=1;
TBinTreeNode<T>* p=pNode;
while(p->Getfather())
{
level++;
p=p->Getfather();
}
return level;
}
template<class T>
long TBinTree<T>::GetLeaves(TBinTreeNode<T>** e)//獲得一根樹的子葉指針,返回子葉個數
{
long cnt=0,nNodes,top=0;
TBinTreeNode<T>* p;
nNodes=GetHeight(root);
if(nNodes<=0) return 0;
TBinTreeNode<T>** stack=new TBinTreeNode<T>*[nNodes+1];
if(stack==NULL) exit(0);
p=root;
while(p!=NULL ||top!=0)
{
if(p!=NULL)
{
if(p->GetSon(1)==NULL && p->GetSon(2)==NULL)
e[cnt++]=p;
top++; stack[top]=p;
p=p->GetSon(1);
}
else
{
p=stack[top];
top--;
p=p->GetSon(2);
}
}
delete[] stack;
return cnt;
}
////////////////////////////////////////////////////////////////////////////////////
template<class T>
long TBinTree<T>::GetHeight(TBinTreeNode<T> * pNode) //獲得樹(子樹)的高度，根為一
{
long h=1,nNodes;
long i,r=1,l=1,t=1;
nNodes=numNodes;
if(pNode==NULL)
return 0;
TBinTreeNode<T>* p=pNode;
TBinTreeNode<T>** pNodes=new TBinTreeNode<T>*[nNodes+1];
pNodes[1]=p;
while(1)
{
for(i=r;i<=l;i++)
{
if(p->GetSon(1)!=NULL)
pNodes[t++]=p->GetSon(1);
if(p->GetSon(2)!=NULL)
pNodes[t++]=p->GetSon(2);
p=pNodes[i];
}
if(l==t) break;
r=l+1;l=t; ++h;
}
return h;
}
template<class T>
long TBinTree<T>::GetNumSubNodes(TBinTreeNode<T> * pNode)//獲得以pNOde為根的樹的子孫個數
{
long cnt=0,nNodes,top=0;
TBinTreeNode<T>* p;
nNodes=GetHeight(pNode);
if(nNodes<=0) return 0;
TBinTreeNode<T>** stack=new TBinTreeNode<T>*[nNodes+1];
if(stack==NULL) exit(0);
p=pNode;
while(p!=NULL ||top!=0)
{
if(p!=NULL)
{
cnt++;
top++; stack[top]=p;
p=p->GetSon(1);
}
else
{
p=stack[top];
top--;
p=p->GetSon(2);
}
}
delete[] stack;
return cnt;
}
////////////////////////////////////////////////cluster in different ways;
template<class T>
long TBinTree<T>::Cluster(TBinTreeNode<T>* pNode,T** es,TTraverseMode tm)//按指定方式遍歷樹
{
long t,i=0;
TBinTreeNode<T>** e=new TBinTreeNode<T>*[numNodes];
t=Cluster(pNode,e,tm);
for(i=0;i<numNodes;i++)
es[i]=&(e[i]->GetElem());
delete[] e;
return t;
}
template<class T>
long TBinTree<T>::Cluster(TBinTreeNode<T>* pNode,TBinTreeNode<T>** e,TTraverseMode tm)
{
switch(tm){
case preorder:return PreOrder(pNode,e);
case inorder: return InOrder(pNode,e);
case postorder:return PostOrder(pNode,e);
case levelorder:return LevelOrder(pNode,e);
}
return 0;
}
/////////////////////////////////////////////////////////////////////////////////
template<class T>
long TBinTree<T>::PreOrder(TBinTreeNode<T>* pNode,TBinTreeNode<T>** e)//前序遍歷
{
long cnt=0,nNodes,top=0;
TBinTreeNode<T>* p;
nNodes=GetHeight(pNode);
// cout<<nNodes<<endl;
if(nNodes<=0) return 0;
TBinTreeNode<T>** stack=new TBinTreeNode<T>*[nNodes+1];
if(stack==NULL) exit(0);
p=pNode;
while(p!=NULL ||top!=0)
{
if(p!=NULL)
{
e[cnt++]=p;
top++; stack[top]=p;
p=p->GetSon(1);
}
else
{
p=stack[top];
top--;
p=p->GetSon(2);
}
}
delete[] stack;
return cnt;
}
template<class T>
long TBinTree<T>::InOrder(TBinTreeNode<T>* pNode,TBinTreeNode<T>** e)//中序遍歷
{
long cnt=0,nNodes,top=0;
TBinTreeNode<T>* p;
nNodes=GetHeight(pNode);
// cout<<nNodes<<endl;
if(nNodes<=0) return 0;
TBinTreeNode<T>** stack=new TBinTreeNode<T>*[nNodes+1];
if(stack==NULL) exit(0);
p=pNode;
while(p!=NULL ||top!=0)
{
if(p!=NULL)
{ top++; stack[top]=p;
p=p->GetSon(1);
}
else
{
p=stack[top];
top--;
e[cnt++]=p;
p=p->GetSon(2);
}
}
delete[] stack;
return cnt;
}
template<class T>
long TBinTree<T>::PostOrder(TBinTreeNode<T>* pNode,TBinTreeNode<T>** pNodes)//后序遍歷
{
long cnt=0,nNodes,top=0;
TBinTreeNode<T>* p;
if(pNode==NULL) return 0;
nNodes=GetHeight(pNode);
if(nNodes<=0) return 0;
struct TPostTraverseStackNode
{
TBinTreeNode<T>* pNode;
char isFirst;
};
TPostTraverseStackNode*sk2;
sk2=new TPostTraverseStackNode[nNodes+1];
if(sk2==NULL) exit(0);
p=pNode;
while(p!=NULL || top!=0)
{
if(p!=NULL)
{
top++;
sk2[top].pNode=p;
sk2[top].isFirst=1;
p=p->GetSon(1);
}
else if(sk2[top].isFirst)
{
sk2[top].isFirst=0;
p=sk2[top].pNode->GetSon(2);
}
else
{
p=sk2[top].pNode;
top--;
pNodes[cnt++]=p;
p=NULL;
}
}
delete[] sk2;
return cnt;
}
template<class T>
long TBinTree<T>::LevelOrder(TBinTreeNode<T>* pNode,TBinTreeNode<T>** e)//層序遍歷
{
long cnt=0,nNodes;
TBinTreeNode<T>*p=pNode;
TBinTreeNode<T>* t;
TBinTreeNode<T>** queue=new TBinTreeNode<T>*[numNodes];
if(queue==NULL) exit(0);
for(int i=0;i<numNodes;i++)
queue[i]=0;
nNodes=1;
queue[0]=p;
while(1)
{
e[cnt]=queue[cnt];
cnt++;
if((cnt!=1) && (queue[cnt]==0)) break;
if((t=p->GetSon(1))!=NULL)
queue[nNodes++]=t;
if((t=p->GetSon(2))!=NULL)
queue[nNodes++]=t;
p=queue[cnt];
}
delete[] queue;
return --cnt;
}
///////////////////////////////////////////////////////////////////////////////
template<class T>
long TBinTree<T>::ClusterAncestors(TBinTreeNode<T>* pNode,T**e)//功能還沒實現
{
return 0;//not actualize yet
}
template<class T>
long TBinTree<T>::ClusterAncestors(TBinTreeNode<T>* pNode,TBinTreeNode<T>** pe)
{
return 0;//not actualize yet
}
template<class T>
long TBinTree<T>::ClusterDescendants(TBinTreeNode<T>* pNode,T** es)
{
return 0;//not actualize yet
}
template<class T>
long TBinTree<T>::ClusterDescendants(TBinTreeNode<T>* pNode,TBinTreeNode<T>** pe)
{
return 0;//not actualize yet
}
template<class T>
long TBinTree<T>::ClusterSeniors(TBinTreeNode<T>* pNode,TBinTreeNode<T>** pe)
{
return 0;//not actualize yet
}
template<class T>
long TBinTree<T>::ClusterSeniors(TBinTreeNode<T>* pNode,T** es)
{
return 0;//not actualize yet
}
template<class T>
long TBinTree<T>::ClusterJuniors(TBinTreeNode<T>* pNode,TBinTreeNode<T>** pe)
{
return 0;//not actualize yet
}
template<class T>
long TBinTree<T>::ClusterJuniors(TBinTreeNode<T>* pNode,T** es)
{
return 0;//not actualize yet
}
///////////////////////////////////////////////////////////////////////////
template<class T>
void TBinTree<T>::DeleteSubTree(TBinTreeNode<T>* pNode,int sonNo)//刪除子樹
{
TBinTreeNode<T>* p=pNode->GetSon(sonNo);
long nNodes=GetNumSubNodes(p);
TBinTreeNode<T>** e=new TBinTreeNode<T>*[nNodes];
Cluster(p,e,preorder);
for(int i=0;i<nNodes;i++)
delete e[i];
pNode->SetSon(sonNo,NULL);
delete[] e;
}
template<class T>
void TBinTree<T>::ReleaseAllNodes()//釋放所有樹節點
{
TBinTreeNode<T>** e=new TBinTreeNode<T>*[numNodes];
Cluster(root,e,preorder);
for(int i=0;i<numNodes;i++)
delete e[i];
root=NULL;
numNodes=0;
delete[] e;
}
/////////////////////////////////////////////////////////////////////////////
template<class T>
TBinTreeNode<T>* TBinTree<T>::Locate(TBinTreeNode<T>* rt,T& e,long sn)//定位
{
long nNodes,top=0;
long n=0;
nNodes=GetHeight(rt);
if(nNodes<=0) return 0;
TBinTreeNode<T>* p;
TBinTreeNode<T>** stack=new TBinTreeNode<T>*[nNodes+1];
if(stack==NULL) exit(0);
p=rt;
while(p!=NULL ||top!=0)
{
if(p!=NULL)
{
if(p->GetElem()==e)
{
n++;
if(n==sn)
return p;
}
top++; stack[top]=p;
p=p->GetSon(1);
}
else
{
p=stack[top];
top--;
p=p->GetSon(2);
}
}
return NULL;
}
template<class T>
TBinTreeNode<T>* TBinTree<T>::GListToTree(long * gListExp,T* es,long numElem) //lists to tree;
{
return NULL; //not actualize yet
}
template<class T>
long TBinTree<T>::TreeToGList(TBinTreeNode<T> * rt,T* e)// tree to lists;
{
return 0; //not actualize yet
}
template<class T>
TBinTreeNode<T>* TBinTree<T>::PreOrderExToTree(T* nodes,int numElem)// preorder extention to tree;
{
return NULL; //not actualize yet
}
///////////////////////////////////////////////////////////////////////////////////////////
template<class T>
TBinTreeNode<T>* TBinTree<T>::InPreToTree(T* pa ,T* ia,long p1,long p2,long i1,long i2)//按前序遍歷和中序遍歷結果構造樹
{
long k;
TBinTreeNode<T>* p;
if(i1>i2) return NULL;
k=0;
while(pa[p1]!=ia[i1+k]) k++;
p=new TBinTreeNode<T>;
p->SetElem(pa[p1]);
p->SetSon(1,InPreToTree(pa,ia,p1+1,p1+k,i1,i1+k-1));
p->SetSon(2,InPreToTree(pa,ia,p1+k+1,p2,i1+k+1,i2));
if(p->GetSon(1)!=NULL)
p->GetSon(1)->Setfather(p);
if(p->GetSon(2)!=NULL)
p->GetSon(2)->Setfather(p);
root=p;
numNodes=p2-p1+1;
return p;
}
template<class T>
void TBinTree<T>::Print(TBinTreeNode<T>* rt,TTraverseMode mode)//按不同遍歷方式打印樹節點
{ TBinTreeNode<T>** e=new TBinTreeNode<T>*[numNodes];
Cluster(root,e,mode);
for(int i=0;i<numNodes;i++)
cout<<e[i]->GetElem()<<" ";
cout<<endl;
delete[] e;
}
///////////////////////////////////////////////////////////////////////////////////////
template<class T>
void TBinTree<T>::Copy(TBinTree<T>& atree)//復制一棵二叉樹，以rt為樹根
{
long cnt=0;
atree.SetRoot(CopyTree(root,cnt));
atree.numNodes=cnt;
}
template<class T>
TBinTreeNode<T>* TBinTree<T>::CopyTree(TBinTreeNode<T>* pNode ,long& n)
{
T info;
TBinTreeNode<T>* newNode=new TBinTreeNode<T>;
info=pNode->GetElem();
newNode->SetElem(info);
n++;
if(pNode->GetSon(1)!=NULL)
newNode->SetSon(1,CopyTree(pNode->GetSon(1),n));
else
newNode->SetSon(1,NULL);
if(pNode->GetSon(2)!=NULL)
newNode->SetSon(2,CopyTree(pNode->GetSon(2),n));
else
newNode->SetSon(2,NULL);
if(newNode->GetSon(1)!=NULL) newNode->GetSon(1)->Setfather(newNode);
if(newNode->GetSon(2)!=NULL) newNode->GetSon(2)->Setfather(newNode);
return newNode;
}
///////////////////////////////////////////////////////////////////////////////////
bool IsOrderedTree(TBinTree<double>* atree) //判斷一棵樹是否是順序二叉樹
{
long nNodes,sign=0;
long i,r=1,l=1,t=1;
nNodes=atree->numNodes;
if(nNodes==0)
return true;
TBinTreeNode<double>* p=atree->root;
TBinTreeNode<double>** pNodes=new TBinTreeNode<double>*[nNodes+1];
pNodes[1]=p;
while(1)
{
for(i=r;i<=l;i++)
{
if(p->GetSon(1)!=NULL)
pNodes[t++]=p->GetSon(1);
else
sign=1;
if(p->GetSon(2)!=NULL)
{
if(sign==1)
break;
pNodes[t++]=p->GetSon(2);
}
else if(l==i)
sign=0;
p=pNodes[i];
}
if(sign==1) return false;
if(l==t) break;
r=l+1;l=t;
}
return true;
}
/////////////////////////////////////////////////////////////////////////////////
void Huffmancode(TBinTree<double>& tr,long n) //求haffman 編碼
{
long i,j,height,nleaves,k;
TBinTreeNode<double>* p;
TBinTreeNode<double>** leaves=new TBinTreeNode<double>*[n];
if(leaves==NULL) exit(0);
nleaves=tr.GetLeaves(leaves);
height=tr.GetHeight(tr.root);
double* aa=new double[nleaves*height];
for(i=0;i<nleaves*height;i++)
aa[i]=2;
for(i=0;i<nleaves;i++)
{
j=0;
while(1)
{
p=leaves[i]->Getfather();
if(p!=NULL)
{
k=i*height+j;
j++;
if(p->GetSon(1)==leaves[i])
aa[k]=0;
else
aa[k]=1;
}
else break;
leaves[i]=p;
}
}
for(i=0;i<nleaves;i++)
for(j=0;j<height;j++)
if(aa[i*height+j]!=2)
cout<<aa[i*height+j];
else
{cout<<endl; break;}
}
////////////////////////////////////////////////////////////////////////////////
void main()
{
TBinTree<double> myTree;
cout<<"NO1: decide a bintree whether a ordered bintree"<<endl;
double arr1[7]={1,2,4,5,3,6,7};
double arr2[7]={2,5,4,1,3,7,6};
myTree.InPreToTree(arr1,arr2,0,6,0,6);//用前序遍歷和中序遍歷結果創建一棵二叉樹(非順序二叉樹)
myTree.Print(myTree.GetRoot());
if(IsOrderedTree(&myTree)) //調用IsOrderedTree()函數判斷是否是順序二叉樹
cout<<"Yeah a Ordered Tree!"<<endl;
else
cout<<"Not a Ordered Tree!"<<endl;
TBinTree<double> myTree2;
double arr11[]={1,2,4,5,3};
double arr12[]={4,2,5,1,3};
myTree2.InPreToTree(arr11,arr12,0,4,0,4);//用前序遍歷和中序遍歷結果創建一棵二叉樹(為順序二叉樹)
myTree2.Print(myTree2.GetRoot());
if(IsOrderedTree(&myTree2))//調用IsOrderedTree()函數判斷是否是順序二叉樹
cout<<"Yeah a Ordered Tree!"<<endl;
else
cout<<"Not a Ordered Tree!"<<endl;
TBinTree<double> ACopiedTree;
cout<<endl<<endl;
cout<<"NO2:Copying a tree:"<<endl;
myTree2.Copy(ACopiedTree); //用TBinTree類的一個函數Copy()實現二叉樹的復制
cout<<"This is a copied tree:"<<endl;
ACopiedTree.Print(ACopiedTree.GetRoot());//輸出復制的二叉樹的結果，以比較兩棵樹是否一致
cout<<endl;
cout<<endl;
cout<<"NO3:Huffman Encoding:"<<endl;
TBinTree<double> haffmantree;
double aa[9]={1,2,4,8,9,5,3,6,7};
double bb[9]={8,4,9,2,5,1,6,3,7};
haffmantree.InPreToTree(aa,bb,0,8,0,8);
cout<<"This is huffman tree:"<<endl;
haffmantree.Print(haffmantree.root);
cout<<"These are Huffman encodings:"<<endl;
Huffmancode(haffmantree,9);
cout<<endl;
cout<<"Note: The display of a bintree is in preorder!"<<endl;
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -