fullbinarytree.h.txt

本课件与严蔚敏 第二版 数据结构（C版） 教材配套

www.pudn.com > asd.rar > FullBinaryTree.h


#ifndef FULLBINARYTREE 
#define FULLBINARTTREE 

#include<iomanip.h> 
#include<math.h> 
#include"BinaryTree.h" 
template<class Type> class FullBinaryTree :public BinaryTree<Type> 
{ 
public: 
FullBinaryTree():BinaryTree<Type>(),size(0),width(WIDTH){} 
FullBinaryTree(Type value):BinaryTree<Type>(value),size(0),width(WIDTH){} 
virtual int Insert(const Type &amt; item); 
virtual void destory(){ destory(root); root=NULL; } 
virtual void print(ostream &amt; out);//打印满而插树 
void setWidth(int w){ width=w;} 
private: 

int size,width; 
static const int WIDTH; 
virtual int Insert(BinTreeNode<Type>* current,const Type &amt; item); 
void destory(BinTreeNode<Type> * current); 
void print(ostream &amt; out,char a,int step); 
void printend(ostream &amt; out,int * position ,int num,int member);//打印满二插树的最后一行 
void printline(ostream &amt; out,int * position,int num,int step);//打印满二插树的一行 
}; 


template<class Type> const int FullBinaryTree<Type>::WIDTH=5; 

template<class Type> void FullBinaryTree<Type>::destory(BinTreeNode<Type> * current) 
{ 
if(current!=NULL) 
{ 
destory(current->leftChild); 
destory(current->rightChild); 
delete current; 
size--; 
} 
} 

template<class Type> int FullBinaryTree<Type>::Insert(BinTreeNode<Type>* current,const Type &amt; item) 
{ 
if(current==NULL) 
{ 
cout<<"current 为空"<<endl; 
return 0; 
} 

Queue<BinTreeNode<Type>* > queue((size+2)/2); 
queue.EnQueue(current); 


while(true) 
{ 
if(!queue.IsEmpty()) 
{ 
current=queue.DeQueue(); 
} 
else 
return 0; 
if(current->leftChild==NULL) 
{ 
current->leftChild=new BinTreeNode<Type>(item); 
return 1; 
} 

queue.EnQueue(current->leftChild); 
if(current->rightChild==NULL) 
{ 
current->rightChild=new BinTreeNode<Type>(item); 
return 1; 
} 
queue.EnQueue(current->rightChild); 
} 
} 

template<class Type> int FullBinaryTree<Type>::Insert(const Type &amt; item) 
{ 
size++; 
if(root==NULL) 
root=new BinTreeNode<Type>(item); 
else 
return Insert(root,item); 
return 1; 
} 

template<class Type> void FullBinaryTree<Type>::print(ostream &amt; out,char a,int step) 
{ 
for(int i=0;i<step;i++) 
{ 
if(i==step/2-1) 
out<<setw(width)<<a; 
else 
out<<setw(width)<<' '; 

} 

} 

template<class Type> void FullBinaryTree<Type>::printline(ostream &amt; out,int * position,int num,int step) 
{ 
int type=1; 

for(int i=step;i<num;i+=step) 
{ 
if(i>step==0) 
{ 
switch(type) 
{ 
case 1: 
type=2; 
print(out,' ',step); 
break; 
case 2: 
print(out,'/',step); 
type=3;break; 
case 3: 
print(out,'\\',step); 
type=4;break; 
case 4: 
print(out,' ',step); 
type=1;break; 
} 
} 
} 
out<<endl; 
} 


template<class Type> void FullBinaryTree<Type>::printend(ostream &amt; out,int *position,int num,int member) 
{ 

bool type=1; 
for(int i=1,j=1;j<=member;i++) 
{ 
if((i-1)>2==0) 
{ 
if(type) 
{ 
out<<setw(width)<<'/'; 
type=!type; 
} 
else 
{ 
out<<setw(width)<<"\\"; 
type=!type; 
} 
j++; 
} 
else 
out<<setw(width)<<' '; 
} 
out<<endl; 
} 

template<class Type> void FullBinaryTree<Type>::print(ostream &amt; out) 
{ 
if(root==NULL || size==0) 
{ 
cout<<"二叉树为空！"<<endl; 
return ; 
} 

out<<"_________________________________________________"<<endl; 
int d=depth();//树的深度 
Queue<BinTreeNode<Type>* > queue((size+2)/2+d); 

queue.EnQueue(root); 
queue.EnQueue(NULL);//行标志 
int i; 

int num=pow(2,d+1); 
int length=num; 
int nowL=0; 

int *position=new int[num];//位置标志 
for(i=0;i<num;i++) 
position[i]=num+2; 

length=length/2; 
for(i=length;i<num;i+=length) 
{ 
if(position[i]>nowL) 
position[i]=nowL; 
} 
int outnum=1; 

while(true) 
{ 
if(queue.IsEmpty()) 
break; 
BinTreeNode<Type> *bn=queue.DeQueue(); 
if(bn==NULL) 
{ 
if(queue.IsEmpty()) 
break; 

nowL++; 
out<<endl; 
length=length/2; 
if(length==0) {cout<<"出错！"<<endl; return ;} 
for(i=length;i<num;i+=length) 
{ 
if(position[i]>nowL) 
position[i]=nowL; 
} 

if(nowL!=d)//输出‘/’或 ‘\‘; 
printline(out,position,num,length); 
else 
printend(out,position,num,size-pow(2,d)+1); 
outnum=1; 

queue.EnQueue(NULL); 
continue; 
} 

for(;outnum<num;outnum++) 
{ 
if(position[outnum]==nowL) 
{ 
out<<setw(width)<<bn->data; 
outnum++; 
break; 
} 
else 
out<<setw(width)<<' '; 
} 
if(bn->leftChild!=NULL) 
queue.EnQueue(bn->leftChild); 
if(bn->rightChild!=NULL) 
queue.EnQueue(bn->rightChild); 
} 
out<<endl; 
out<<"_________________________________________________"<<endl; 

delete [] position; 
} 

#endif