fullbinarytree.h

数据结构程序设计21

#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 & item);
       virtual void destory(){ destory(root); root=NULL; }
	   virtual void print(ostream & out);//打印满而插树
	   void setWidth(int w){ width=w;}
private:
	
		int size,width;
		static const int WIDTH;
		virtual int Insert(BinTreeNode<Type>* current,const Type & item);
    	void destory(BinTreeNode<Type> * current);
     	void print(ostream & out,char a,int step);
		void printend(ostream & out,int * position ,int num,int member);//打印满二插树的最后一行
		void printline(ostream & 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 & 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 & 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 & 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 & 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 & 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 & 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