📄 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 + -