btcontrol.cpp

一个构建、显示和判断完全二叉树的小程序。

// BTControl.cpp: implementation of the CBTControl class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "BT1033.h"
#include "BTControl.h"
#include <math.h>

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CBTControl::CBTControl(){}
CBTControl::~CBTControl(){}

bool CBTControl::INS_CHILD(CBinaryTree *h,bool InsType,int Ipoint)
{
	bool EN=0; //是否找到插入点标识
	int pn=0; //节点应有的编号
	while(h->NextNode!=h) //循环到末尾返回
	{
		pn++;
		h=h->NextNode;
		if (pn == Ipoint && EN==false) {Ipoint=h->FBTserial;EN=true;}
		if (h->FBTserial > 2*Ipoint+(int)InsType) //找到插入点的后继
			if (InsertChild(h->FirstNode,h,2*Ipoint+(int)InsType)) return true;
	}
	if (InsertChild(h,0,2*Ipoint+(int)InsType)) return true;

return false;
}

int CBTControl::CHILD(CBinaryTree *h,bool cType,int Fpoint)
{
	bool EN=0; //是否找到插入点标识
	int pn=0; //节点应有的编号
	do  //查找直到链表末尾结束
	{
		pn++;
		h = h->NextNode;

		if (pn == Fpoint && EN==false) {EN=true;Fpoint=h->FBTserial;} //找到查询点
		if (pn > Fpoint && EN == false) return -1; //节点不存在返回-1
		if (h->FBTserial > 2*Fpoint +1 ) return 0; //如果查找不到返回0
		if (h->FBTserial == 2*Fpoint && cType == false) return 2*Fpoint; //找到左孩子
		if (h->FBTserial == 2*Fpoint +1 && cType == true) return 2*Fpoint +1; //找到右孩子

	} while(h->NextNode!=h);
if(EN) return 0; else return -1;
}

bool CBTControl::InsertChild(CBinaryTree *fp,CBinaryTree *np,int Sn)
{
	//创建并插入节点
	CBinaryTree *tmp = new CBinaryTree;
	tmp->FBTserial = Sn;
	tmp->FEmptyNode = Sn - (fp->FBTserial + 1);
	tmp->FirstNode = fp;
	fp->NextNode = tmp;
	if (np!=0) 
	{
		tmp->NextNode=np;
		np->FirstNode=tmp;
		np->FEmptyNode = np->FBTserial - (Sn + 1);
	}
	
return true;
}

void CBTControl::ShowBTList(CBinaryTree *h)
{
	int tmp,tmp2,tmp3,tmp4;
	int cl2=0; //当前遍历的所在层
	int pn=0; //节点应有的编号
	int cl=CountLayer(h); //获取二叉树的层数
	do
	{
		pn++;
		h=h->NextNode;
		if (h->FBTserial >= pow(2,cl2)) 
		{
			printf("\n");
			tmp2=pow(2,cl-cl2)-1;
			cl2++;
			tmp4=pow(2,cl2-1); //当前层的起始编号
			for(tmp=0;tmp<pow(2,cl-cl2)-1;tmp++) printf("  "); //输出前占位符	
		}
		else
			for(tmp=0;tmp < tmp2;tmp++) printf("  "); //输出中占位符

		

		for(tmp=0;tmp < h->FBTserial-tmp4;tmp++) //若当前节点前有空节点 
		{
			printf("  "); //输出节点占位符
			for(tmp3=0;tmp3<tmp2;tmp3++) printf("  "); //输出中占位符
		}
			
		printf("%2i",pn) ; //输出节点应有的编号
		tmp4=h->FBTserial+1;

	}while(h->NextNode!=h);

}

int CBTControl::CountLayer(CBinaryTree *h)
{
	int cl=0; //层数
	do //移动节点至末尾结束 
	{
		h=h->NextNode; 
		if(h->FBTserial >= pow(2,cl)) cl+=1;
	}while(h->NextNode!=h);
return cl;
}

bool CBTControl::JudgeBT(CBinaryTree *Tail)
{
	while(Tail->NextNode != Tail) Tail=Tail->NextNode; //Tail指向最末节点的指针
	while(Tail->FirstNode != Tail) //倒序层次遍历
	{
		if (Tail->FEmptyNode !=0) return false; //节点有空节点则不为完全二叉树
		Tail=Tail->FirstNode;
	}
return true;
}

bool CBTControl::DeletPoint(CBinaryTree *h,int ip)
{
	int pn=0; //节点应有的编号
	do //查找待删除节点
	{
		pn++;
		h=h->NextNode;
	}while(pn!=ip);

	if (h->NextNode != h) //判断是否为最末的节点
	{
		h->FirstNode->NextNode = h->NextNode;
		h->NextNode->FirstNode = h->FirstNode;
		h->NextNode->FEmptyNode = h->NextNode->FBTserial - h->FirstNode->FBTserial -1;
	}
	else
	{
		h->FirstNode->NextNode = h->FirstNode;
	}
	free(h); //释放空间

return 1;
}

void CBTControl::FreeMemory(CBinaryTree *h)
{
	h=h->NextNode; //指向根节点
	while(h->NextNode !=h) //依次清除每一个节点
	{
		h=h->NextNode;
		free(h->FirstNode);
	}
	free(h);
}