cbaltree.cpp

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

CPP
749 行
字号
12
#include "stdafx.h"
#include "CBalTree.h"
#include "assert.h"
#include "ExternVal.h"

BalTreeObj::BalTreeObj()
{ 
       BalNum=0;
       DeepNum=1;
       PLeftObj=0;
       PRightObj=0;
       PParentObj=0;
       PID=0;
};

char BalTreeObj::GetBalNum()
{ 
return BalNum;
};

char BalTreeObj::GetDeepNum()
{ 
return DeepNum;
};

char BalTreeObj::GetPIDNum()
{ 
return PID;
};

void BalTreeObj::ReBuild(BalTreeObj* const BTO,int UnBalID)
{  
  BalTreeObj* InsteadObj;
  BalTreeObj* InsteadObjANO;
  InsteadObj=0;
  InsteadObjANO=0;
  switch(UnBalID)
  {  
     case 1:                              //平衡树的第一种情况
      InsteadObj=BTO->PLeftObj;  
      if(BTO->PParentObj)
      {
		  if(BTO->PID>0)
		  {     
			  BTO->PParentObj->PRightObj=InsteadObj;
		  }
		  else
		  {   
			  BTO->PParentObj->PLeftObj=InsteadObj;
		  };     
      };
      InsteadObj->PParentObj=BTO->PParentObj;
         BTO->PLeftObj=InsteadObj->PRightObj;
      if(InsteadObj->PRightObj)
      {
       InsteadObj->PRightObj->PParentObj=BTO;
          InsteadObj->PRightObj->PID=-1;
      };
         InsteadObj->PRightObj=BTO;
         InsteadObj->PID=BTO->PID;
      BTO->PID=1;
      BTO->PParentObj=InsteadObj;
      BTO->DeepNum-=2;
      BTO->BalNum=0;
      InsteadObj->BalNum=0;
      break;
     case 2:
      InsteadObj=BTO->PLeftObj->PRightObj;   //新的主节点已经连接好，并且设置了上层节点的DEEPNUM和BALNUM
      if(BTO->PParentObj)
      {
       if(BTO->PID>0)
       {
        BTO->PParentObj->PRightObj=InsteadObj;
       }
       else
       {
        BTO->PParentObj->PLeftObj=InsteadObj;
       }
      };
      InsteadObj->PID=BTO->PID;
      InsteadObj->PParentObj=BTO->PParentObj;
      InsteadObjANO=BTO->PLeftObj;         //At4与ki+1新的父子关系确定
      InsteadObjANO->PRightObj=InsteadObj->PLeftObj;
      InsteadObj->PLeftObj->PParentObj=InsteadObjANO;
      InsteadObj->PLeftObj->PID=1;
      InsteadObjANO->DeepNum--;
      InsteadObjANO->BalNum=0;
      InsteadObjANO->PRightObj->PID=1;
      BTO->PLeftObj=InsteadObj->PRightObj; //Ki与At-13新的父子关系确定
      if(InsteadObj->PRightObj)
      {
       InsteadObj->PRightObj->PParentObj=BTO;
       InsteadObj->PRightObj->PID=-1;
      };
      BTO->BalNum=1;
      BTO->DeepNum-=2;
      InsteadObj->PLeftObj=InsteadObjANO;  //新的主节点与其他两节点的父子关系确定
      InsteadObj->PRightObj=BTO;
      InsteadObjANO->PParentObj=InsteadObj;
      BTO->PParentObj=InsteadObj;
      BTO->PID=1;
      InsteadObj->BalNum=0;
      InsteadObj->DeepNum++;
               break;
     case 3:
      InsteadObj=BTO->PLeftObj->PRightObj;   //新的主节点已经连接好，并且设置了上层节点的DEEPNUM和BALNUM
      if(BTO->PParentObj)
      {
       if(BTO->PID>0)
       {
        BTO->PParentObj->PRightObj=InsteadObj;
       }
       else
       {
        BTO->PParentObj->PLeftObj=InsteadObj;
       }
      };
      InsteadObj->PID=BTO->PID;
      InsteadObj->PParentObj=BTO->PParentObj;
      InsteadObjANO=BTO->PLeftObj;         //At-14与ki+1新的父子关系确定
      InsteadObjANO->PRightObj=InsteadObj->PLeftObj;
      if(InsteadObj->PLeftObj)
               {
       InsteadObj->PLeftObj->PParentObj=InsteadObjANO;
          InsteadObj->PLeftObj->PID=1;
      };
      InsteadObjANO->DeepNum--;
      InsteadObjANO->BalNum=-1;
      BTO->PLeftObj=InsteadObj->PRightObj; //Ki与At3新的父子关系确定
      InsteadObj->PRightObj->PParentObj=BTO;
      InsteadObj->PRightObj->PID=-1;
               BTO->BalNum=0;
      BTO->DeepNum-=2;
      InsteadObj->PLeftObj=InsteadObjANO; //新的主节点与其他两节点的父子关系确定
      InsteadObj->PRightObj=BTO;
      InsteadObjANO->PParentObj=InsteadObj;
      BTO->PParentObj=InsteadObj;
      BTO->PID=1;
      InsteadObj->BalNum=0;
      InsteadObj->DeepNum++;
               break;
     case 4:
      InsteadObj=BTO->PLeftObj->PRightObj;   //新的主节点已经连接好，并且设置了上层节点的DEEPNUM和BALNUM
      InsteadObjANO=BTO->PParentObj;
      if(InsteadObjANO)
      {
       if(BTO->PID>0)
       {
           InsteadObjANO->PRightObj=InsteadObj;
       }
       else
       {
        BTO->PParentObj->PLeftObj=InsteadObj;
       };
      };
      InsteadObj->PID=BTO->PID;
      InsteadObj->PParentObj=BTO->PParentObj;
      InsteadObjANO=BTO->PLeftObj;
	  if(InsteadObj->PRightObj)  
	  {
//		  if(!InsteadObj->PLeftObj)
//			  BTO->PushError("错误发生在Rebuild函数的case 8，原因是BALNUM实际不平衡");
		  BTO->PLeftObj=InsteadObj->PRightObj;
		  InsteadObj->PRightObj->PParentObj=BTO;
		  InsteadObj->PRightObj->PID=-1;
		  InsteadObjANO->PRightObj=InsteadObj->PLeftObj;
		  InsteadObj->PLeftObj->PParentObj=InsteadObjANO;
		  InsteadObj->PLeftObj->PID=1;
	  }
	  else
	  {
		  
		  InsteadObjANO->PRightObj=0;
		  BTO->PLeftObj=0;
	  };
      InsteadObj->PLeftObj=InsteadObjANO;
      InsteadObj->PRightObj=BTO;
      InsteadObj->DeepNum++;
      InsteadObj->BalNum=0;
      InsteadObjANO->BalNum=0;
      InsteadObjANO->DeepNum--;
      BTO->PParentObj=InsteadObj;
      InsteadObjANO->PParentObj=InsteadObj;
      BTO->BalNum=0;
      BTO->DeepNum-=2;
      BTO->PID=1;
      break;
     case 5:                              //平衡树的第一种情况
      InsteadObj=BTO->PRightObj;  
      if(BTO->PParentObj)
      {
		  if(BTO->PID>0)
		  {     
			  BTO->PParentObj->PRightObj=InsteadObj;
		  }
		  else
		  {   
			  BTO->PParentObj->PLeftObj=InsteadObj;
		  };
     
      };
      InsteadObj->PParentObj=BTO->PParentObj;
      BTO->PRightObj=InsteadObj->PLeftObj;
      if(InsteadObj->PLeftObj)
      {
          InsteadObj->PLeftObj->PParentObj=BTO;
          InsteadObj->PLeftObj->PID=1;
      };
          InsteadObj->PLeftObj=BTO;
          InsteadObj->PID=BTO->PID;
      BTO->PID=-1;
      BTO->PParentObj=InsteadObj;
      BTO->DeepNum-=2;
      BTO->BalNum=0;
      InsteadObj->BalNum=0;
      break;
     case 6:
      InsteadObj=BTO->PRightObj->PLeftObj;   //新的主节点已经连接好，并且设置了上层节点的DEEPNUM和BALNUM
      if(BTO->PParentObj)
      {
       if(BTO->PID>0)
       {
        BTO->PParentObj->PRightObj=InsteadObj;
       }
       else
       {
        BTO->PParentObj->PLeftObj=InsteadObj;
       }
      };
      InsteadObj->PID=BTO->PID;
      InsteadObj->PParentObj=BTO->PParentObj;
      InsteadObjANO=BTO->PRightObj;         //At4与ki+1新的父子关系确定
      InsteadObjANO->PLeftObj=InsteadObj->PRightObj;
      InsteadObj->PRightObj->PParentObj=InsteadObjANO;
      InsteadObj->PRightObj->PID=-1;
      InsteadObjANO->DeepNum--;
      InsteadObjANO->BalNum=0;
      InsteadObjANO->PLeftObj->PID=-1;
      BTO->PRightObj=InsteadObj->PLeftObj; //Ki与At-13新的父子关系确定
      if(InsteadObj->PLeftObj)
      {
       InsteadObj->PLeftObj->PParentObj=BTO;
       InsteadObj->PLeftObj->PID=1;
      };
      BTO->BalNum=-1;
      BTO->DeepNum-=2;
      InsteadObj->PRightObj=InsteadObjANO;  //新的主节点与其他两节点的父子关系确定
      InsteadObj->PLeftObj=BTO;
      InsteadObjANO->PParentObj=InsteadObj;
      BTO->PParentObj=InsteadObj;
      BTO->PID=-1;
      InsteadObj->BalNum=0;
      InsteadObj->DeepNum++;
               break;
     case 7:
      InsteadObj=BTO->PRightObj->PLeftObj;   //新的主节点已经连接好，并且设置了上层节点的DEEPNUM和BALNUM
      if(BTO->PParentObj)
      {
       if(BTO->PID>0)
       {
        BTO->PParentObj->PRightObj=InsteadObj;
       }
       else
       {
        BTO->PParentObj->PLeftObj=InsteadObj;
       }
      };
      InsteadObj->PID=BTO->PID;
      InsteadObj->PParentObj=BTO->PParentObj;
      InsteadObjANO=BTO->PRightObj;         //At-14与ki+1新的父子关系确定
      InsteadObjANO->PLeftObj=InsteadObj->PRightObj;
      if(InsteadObj->PRightObj)
               {
       InsteadObj->PRightObj->PParentObj=InsteadObjANO;
          InsteadObj->PRightObj->PID=-1;
      };
      InsteadObjANO->DeepNum--;
      InsteadObjANO->BalNum=1;
      BTO->PRightObj=InsteadObj->PLeftObj; //Ki与At3新的父子关系确定
      InsteadObj->PLeftObj->PParentObj=BTO;
      InsteadObj->PLeftObj->PID=1;
               BTO->BalNum=0;
      BTO->DeepNum-=2;
      InsteadObj->PRightObj=InsteadObjANO; //新的主节点与其他两节点的父子关系确定
      InsteadObj->PLeftObj=BTO;
      InsteadObjANO->PParentObj=InsteadObj;
      BTO->PParentObj=InsteadObj;
      BTO->PID=-1;
      InsteadObj->BalNum=0;
      InsteadObj->DeepNum++;
       break;
     case 8:
		 /*
      InsteadObj=BTO->PRightObj->PLeftObj;   //新的主节点已经连接好，并且设置了上层节点的DEEPNUM和BALNUM
      InsteadObjANO=BTO->PParentObj;
      if(InsteadObjANO)
      {
       if(BTO->PID>0)
       {
           InsteadObjANO->PRightObj=InsteadObj;
       }
       else
       {
        BTO->PParentObj->PLeftObj=InsteadObj;
       };
      };
      InsteadObj->PID=BTO->PID;
      InsteadObj->PParentObj=BTO->PParentObj;
      InsteadObjANO=BTO->PRightObj;
      InsteadObj->PRightObj=InsteadObjANO;
      InsteadObj->PLeftObj=BTO;
      InsteadObj->DeepNum++;
      InsteadObj->BalNum=0;
      InsteadObjANO->BalNum=0;
      InsteadObjANO->DeepNum--;
      InsteadObjANO->PLeftObj=0;
      BTO->PRightObj=0;
      BTO->PParentObj=InsteadObj;
      InsteadObjANO->PParentObj=InsteadObj;
      BTO->BalNum=0;
      BTO->DeepNum-=2;
      BTO->PID=-1;
	  */
		 InsteadObj=BTO->PRightObj->PLeftObj;   //新的主节点已经连接好，并且设置了上层节点的DEEPNUM和BALNUM
		 InsteadObjANO=BTO->PParentObj;
		 if(InsteadObjANO)
		 {
			 if(BTO->PID>0)
			 {
				 InsteadObjANO->PRightObj=InsteadObj;
			 }
			 else
			 {
				 BTO->PParentObj->PLeftObj=InsteadObj;
			 };
		 };
		 InsteadObj->PID=BTO->PID;
		 InsteadObj->PParentObj=BTO->PParentObj;
		 InsteadObjANO=BTO->PRightObj;
		 if(InsteadObj->PRightObj)  
		 {
			 InsteadObjANO->PLeftObj=InsteadObj->PRightObj;
			 InsteadObj->PRightObj->PParentObj=InsteadObjANO;
			 InsteadObj->PRightObj->PID=-1;
			 InsteadObj->PLeftObj->PParentObj=BTO;
			 BTO->PRightObj=InsteadObj->PLeftObj;
			 InsteadObj->PLeftObj->PID=1;
		 }
		 else
		 {
			 
			 InsteadObjANO->PLeftObj=0;
			 BTO->PRightObj=0;
		 };
		 InsteadObj->PRightObj=InsteadObjANO;
		 InsteadObj->PLeftObj=BTO;
		 InsteadObj->DeepNum++;
		 InsteadObj->BalNum=0;
		 InsteadObjANO->BalNum=0;
		 InsteadObjANO->DeepNum--;

		 BTO->PParentObj=InsteadObj;
		 InsteadObjANO->PParentObj=InsteadObj;
		 BTO->BalNum=0;
		 BTO->DeepNum-=2;
		 BTO->PID=-1;     
      break;
	 case 9:
		 InsteadObj=BTO->PLeftObj;
		 InsteadObjANO=BTO->PParentObj;
		 //将根节点与新的ROOT绑定父子关系
		 if(InsteadObjANO)
		 {
			 if(BTO->PID==-1)
				 InsteadObjANO->PLeftObj=InsteadObj;
12

cbaltree.cpp - 源码说明

本页面展示了「平衡树基类.可以通过继承重载建立自己需要的平衡树结构」中的 cbaltree.cpp 源码文件，采用 C++ 编程语言编写，共 749 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫开发者社区收录了大量与平衡树相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?