cbaltree.cpp

来自「平衡树基类.可以通过继承重载建立自己需要的平衡树结构」· C++ 代码 · 共 749 行 · 第 1/2 页

			 else
				 InsteadObjANO->PRightObj=InsteadObj;
		 }
		 InsteadObj->PParentObj=InsteadObjANO;
		 //设置好新的ROOT的各个参数
		 InsteadObj->PID=BTO->PID;
		 InsteadObj->BalNum=1;
		 InsteadObj->DeepNum++;
		 //将BTO与新ROOT的右树绑定关系，设置好BTO和ROOT右树的参数
		 BTO->PLeftObj=InsteadObj->PRightObj;
		 InsteadObj->PRightObj->PParentObj=BTO;
		 InsteadObj->PRightObj->PID=-1;
		 BTO->BalNum=-1;
		 BTO->DeepNum--;
		 BTO->PID=1;
		 //将BTO与新ROOT绑定关系
		 BTO->PParentObj=InsteadObj;
		 InsteadObj->PRightObj=BTO;
		 break;
	 case 10:
		 InsteadObj=BTO->PRightObj;
		 InsteadObjANO=BTO->PParentObj;
		 //将根节点与新的ROOT绑定父子关系
		 if(InsteadObjANO)
		 {
			 if(BTO->PID==-1)
				 InsteadObjANO->PLeftObj=InsteadObj;
			 else
				 InsteadObjANO->PRightObj=InsteadObj;
		 }
		 InsteadObj->PParentObj=InsteadObjANO;
		 //设置好新的ROOT的各个参数
		 InsteadObj->PID=BTO->PID;
		 InsteadObj->BalNum=-1;
		 InsteadObj->DeepNum++;
		 //将BTO与新ROOT的左树绑定关系，设置好BTO和ROOT右树的参数
		 BTO->PRightObj=InsteadObj->PLeftObj;
		 InsteadObj->PLeftObj->PParentObj=BTO;
		 InsteadObj->PLeftObj->PID=1;
		 BTO->BalNum=1;
		 BTO->DeepNum--;
		 BTO->PID=-1;
		 //将BTO与新ROOT绑定关系
		 BTO->PParentObj=InsteadObj;
		 InsteadObj->PLeftObj=BTO;
		 break;
     default:
      return;
  };
};
BOOL BalTreeObj::SetPoint(BalTreeObj* const BTO,const int i)    //插入一个节点，并计算新的平衡值
{ 
    if(BTO)
	{   
		if(!i)   //左节点
        {  
			if(BTO->PLeftObj)
				return FALSE;
			this->PParentObj=BTO;
			BTO->PLeftObj=this;
			this->PID=-1;
			BTO->RefreshBalNum(-1*DeepNum);
		}
		else
		{   
			if(BTO->PRightObj)
				return FALSE;
			this->PParentObj=BTO;
			BTO->PRightObj=this;
			this->PID=1;
			BTO->RefreshBalNum(DeepNum);
		};
		return TRUE;
	};
	return FALSE;
};

CString BalTreeObj::GetValueMsg()
{
	return _T("");
}

BalTreeObj* BalTreeObj::DeletePoint(BalTreeObj* BTO,BalTreeObj*& BTOInstead)
{
	BalTreeObj* MoveBTO=NULL;
	if(BTO->BalNum<=0)  //从左边取节点
	{
		while(BTO->PLeftObj)
		{
		    MoveBTO=BTO->PLeftObj;
			assert(MoveBTO);
    		while(MoveBTO->PRightObj)
			{
        		MoveBTO=MoveBTO->PRightObj;
			}
			if(BTOInstead==MoveBTO)
				BTOInstead=BTO;
			BTO->NodeDataChange(MoveBTO);
			BTO=MoveBTO;
		}
	}
    else
	{
		while(BTO->PLeftObj||BTO->PRightObj)
		{
			MoveBTO=BTO->PRightObj;
			assert(MoveBTO);
			while(MoveBTO->PLeftObj)
				MoveBTO=MoveBTO->PLeftObj;
			if(BTOInstead==MoveBTO)
				BTOInstead=BTO;
			BTO->NodeDataChange(MoveBTO);
			BTO=MoveBTO;
				
		}
	}
	BalTreeObj* pRoot =  NULL;
	if(BTO->PParentObj)
	{
		if(BTO->PID==-1)
			BTO->PParentObj->PLeftObj=NULL;
		else
			BTO->PParentObj->PRightObj=NULL;
		BTO->PParentObj->RefreshBalNum(BTO->DeepNum*BTO->PID,FALSE);
		pRoot = BTO->PParentObj->GetRoot();
		BTO->PParentObj=NULL;
	}
	else
		pRoot = NULL;
	BTO->DeleteObject();
	delete BTO;
	return pRoot;
}

BalTreeObj* BalTreeObj::GetRoot()
{
if(this->PParentObj)
  return this->PParentObj->GetRoot();
else
     return this;
};

void BalTreeObj::RefreshBalNum(const int i,BOOL IsAdd)
{
	int RealDN;
	RealDN=0;
	if(IsAdd)
	{
		if((BalNum*i)>=0)
			RealDN=abs(i);
		else
			if(((BalNum+i)*BalNum)<0)
				RealDN=((BalNum+i)>0?(BalNum+i):-1*(BalNum+i));
		DeepNum=DeepNum+RealDN;
		BalNum=BalNum+i;
	}
	else
	{	
		if(BalNum*i>0)
		{
			if((BalNum-i)*BalNum>=0)
				RealDN=abs(i);
			else
				RealDN=abs(BalNum);
		}
		BalNum=BalNum-i;
		DeepNum=DeepNum-RealDN;
	};
	BalTreeObj* pParent = this->PParentObj;
	SHORT THISPID = this->PID;
	SHORT MinRealDN = 0;
	if(BalNum*BalNum>=4)    //发现不平衡
	{
		if(BalNum==-2)
		{ 
			if(this->PLeftObj->BalNum==-1)
			{
				ReBuild(this,1);
				MinRealDN = 1;
			}
			else if(this->PLeftObj->BalNum==1)
			{
				if(this->PLeftObj->PRightObj->BalNum==1)
				{
					MinRealDN = 1;
					ReBuild(this,3);
				}
				else if(this->PLeftObj->PRightObj->BalNum==-1)
				{
					MinRealDN = 1;
					ReBuild(this,2);
				}
				else
				{				
					MinRealDN = 1;
					ReBuild(this,4);
				}
			}
			else if(this->PLeftObj->BalNum==0)
			{	
				ReBuild(this,9);  //新加的情况，只有删除的时候才会出现
			};
		}
		else
		{   
			if(this->PRightObj->BalNum==1)
			{   
				MinRealDN = 1;
				ReBuild(this,5);
			}
			else if(this->PRightObj->BalNum==-1)
			{
				if(this->PRightObj->PLeftObj->BalNum==-1)
				{
					MinRealDN = 1;
					ReBuild(this,7);
				}
				else if(this->PRightObj->PLeftObj->BalNum==1)
				{
					MinRealDN = 1;
					ReBuild(this,6);
				}
				else
				{
					MinRealDN = 1;
					ReBuild(this,8);
				};
			}
			else
			{
				ReBuild(this,10);  //新加的情况，只有删除的时候才会出现
			};
		};
		if(IsAdd)
		    return;
		else
		{
			RealDN = MinRealDN;
		}
	};
	if(RealDN&&pParent)
	{   
		if(THISPID==-1)
		{
			pParent->RefreshBalNum(-1*RealDN,IsAdd);
		}
		else
		{
			pParent->RefreshBalNum(RealDN,IsAdd);
		}
	};
};

BalTreeObj::~BalTreeObj()
{
	DeleteObject();
}

void BalTreeObj::DeleteTree(BalTreeObj* pTreeObj)
{
	if(pTreeObj)
	{
		if(pTreeObj->PLeftObj)
		{
			DeleteTree(pTreeObj->PLeftObj);
			pTreeObj->PLeftObj->DeleteObject();
			delete pTreeObj->PLeftObj;
		}
		if(pTreeObj->PRightObj)
		{
			DeleteTree(pTreeObj->PRightObj);
			pTreeObj->PRightObj->DeleteObject();
			delete pTreeObj->PRightObj;
		}
	};
	
}

void BalTreeObj::DeleteObject()
{
}

void BalTreeObj::NodeDataChange(BalTreeObj* BTO)
{
	
}

BOOL BalTreeObj::CheckTreeData(BalTreeObj* BTO)
{
	assert(BTO);
	if(BTO->BalNum!=BTO->GetRealBalNum(BTO)||BTO->DeepNum!=BTO->GetRealDeep(BTO))
	{
		CString ErrorStr;
		ErrorStr=_T("BalNum or DeepNum Error:");
		ErrorStr+=BTO->GetValueMsg();
		BTO->PushError(ErrorStr);
		return FALSE;
	}
	if(BTO->PParentObj)
	{
		if((BTO->PParentObj->PLeftObj==BTO&&BTO->PID!=-1)||(BTO->PParentObj->PRightObj==BTO&&BTO->PID!=1))
		{
			CString ErrorStr;
			ErrorStr=_T("PID Error:");
			ErrorStr+=BTO->GetValueMsg();
			BTO->PushError(ErrorStr);
			return FALSE;
		}
	}
	if(BTO->PLeftObj)
	{
		if(BTO->PLeftObj->PParentObj!=BTO)
		{
			CString ErrorStr;
			ErrorStr=_T("PARENT Error:");
			ErrorStr+=BTO->GetValueMsg();
			BTO->PushError(ErrorStr);
			return FALSE;
		}
		if(!CheckTreeData(BTO->PLeftObj))
			return FALSE;
	}
	if(!BTO->CheckData())
		return FALSE;
	if(BTO->PRightObj)
	{
		if(BTO->PRightObj->PParentObj!=BTO)
		{
			CString ErrorStr;
			ErrorStr=_T("PARENT Error:");
			ErrorStr+=BTO->GetValueMsg();
			BTO->PushError(ErrorStr);
			return FALSE;
		}
		if(!CheckTreeData(BTO->PRightObj))
			return FALSE;
	}
	return TRUE;
}

SHORT BalTreeObj::GetRealDeep(BalTreeObj* BTO)
{
	if(BTO)
	{
		SHORT D1 = GetRealDeep(BTO->PLeftObj);
		SHORT D2 = GetRealDeep(BTO->PRightObj);
		return 1+(D1>D2?D1:D2);
	}
	else
		return 0;
}

SHORT BalTreeObj::GetRealBalNum(BalTreeObj* BTO)
{
	assert(BTO);
	return GetRealDeep(BTO->PRightObj)-GetRealDeep(BTO->PLeftObj);
}

void BalTreeObj::PushError(CString strReport)
{
}

BOOL BalTreeObj::CheckData()
{
	return TRUE;
}

INT BalTreeObj::GetTreeNode(BalTreeObj* BTO)
{
	if(!BTO)
		return 0;
	else
		return (GetTreeNode(BTO->PLeftObj))+(GetTreeNode(BTO->PRightObj))+1;
}