*衡二叉树相关知识和代码实现

发布于:2021-09-28 11:41:04


*衡二叉树(Balanced binary tree)是由阿德尔森-维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的,所以又称为AVL树。



定义:*衡二叉树或为空树,或为如下性质的二叉排序树:


??(1)左右子树深度之差的绝对值不超过1;


??(2)左右子树仍然为*衡二叉树.


??????*衡因子BF=左子树深度-右子树深度.


*衡二叉树每个结点的*衡因子只能是1,0,-1。若其绝对值超过1,则该二叉排序树就是不*衡的。


如图所示为*衡树和非*衡树示意图:




二、*衡二叉树算法思想


若向*衡二叉树中插入一个新结点后破坏了*衡二叉树的*衡性。首先要找出插入新结点后失去*衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系,使之成为新的*衡子树。当失去*衡的最小子树被调整为*衡子树后,原有其他所有不*衡子树无需调整,整个二叉排序树就又成为一棵*衡二叉树。


????????失去*衡的最小子树是指以离插入结点最*,且*衡因子绝对值大于1的结点作为根的子树。假设用A表示失去*衡的最小子树的根结点,则调整该子树的操作可归纳为下列四种情况。


?(1)LL型*衡旋转法


由于在A的左孩子B的左子树上插入结点F,使A的*衡因子由1增至2而失去*衡。故需进行一次顺时针旋转操作。?即将A的左孩子B向右上旋转代替A作为根结点,A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。




(2)RR型*衡旋转法


由于在A的右孩子C?的右子树上插入结点F,使A的*衡因子由-1减至-2而失去*衡。故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转代替A作为根结点,A向左下旋转成为C的左子树的根结点。而原来C的左子树则变成A的右子树。




(3)LR型*衡旋转法


由于在A的左孩子B的右子数上插入结点F,使A的*衡因子由1增至2而失去*衡。故需进行两次旋转操作(先逆时针,后顺时针)。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置,然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型,再按LL型处理。




??????如图中所示,即先将圆圈部分先调整为*衡树,然后将其以根结点接到A的左子树上,此时成为LL型,再按LL型处理成*衡型。


(4)RL型*衡旋转法??


由于在A的右孩子C的左子树上插入结点F,使A的*衡因子由-1减至-2而失去*衡。故需进行两次旋转操作(先顺时针,后逆时针),即先将A结点的右孩子C的左子树的根结点D向右上旋转提升到C结点的位置,然后再把该D结点向左上旋转提升到A结点的位置。即先使之成为RR型,再按RR型处理。




?如图中所示,即先将圆圈部分先调整为*衡树,然后将其以根结点接到A的左子树上,此时成为RR型,再按RR型处理成*衡型。


*衡化靠的是旋转。参与旋转的是3个节点(其中一个可能是外部节点NULL),旋转就是把这3个节点转个位置。注意的是,左旋的时候p->right一定不为空,右旋的时候p->left一定不为空,这是显而易见的。


如果从空树开始建立,并时刻保持*衡,那么不*衡只会发生在插入删除操作上,而不*衡的标志就是出现bf == 2或者?bf == -2的节点。



注意:以上是网易博客kimibob的文章内容,本人觉得是我看过的关于*衡二叉树最简洁有力、通俗易懂的阐述,在此希望能帮到大家。说是原创实在是心生愧疚,其实我要原创的是二叉树的代码实现,有了kimibob以上对*衡二叉树的描述,我瞬间有一种自己也能动手实现二叉树建立和相关操作的代码了,不知道大家的感觉是否也是这样?让我们一起来写代码吧.............(未完待续)



写代码的时候才发现难度不小啊,而且我自己还人为的给自己写代码增加了难度,本来想在节点里面增加一个指向父节点的指针以便于寻找父节点,哪里知道在写代码的时候才发现为了维护这个父节点指针,实在是让人憔悴了不少。而且我采用的还是私有成员,这样搞了很多获取和设置值得函数,让代码的可读性也降低了,而且我写代码的时候也看着眼花,好在硬着头皮把*衡二叉树的建立写出来了,并用中序遍历大致证明其有序性,删除操作实在写着崩溃了(这和我还没有完全了解删除时到底有哪些情况的变化有直接关系,因此我决定完全搞懂删除一个节点有多少种情况,以及每种情况的现象时再完成吧--后面一句加上删除代码了,但感觉有点问题,大家可以用随机整数测我的代码测,建立应该没问题了,删除操作会有问题)下面就上二叉树建立的代码了。在上代码之前,我不得不提到这下面这个关于二叉*衡树的超牛文章:


http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.html


好了上代码:





// AVLTree.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include
using namespace std;
//节点
class CNode
{
private:
int m_nBF;//*衡因子
int m_nData;//数据
CNode* m_pLChild;//左子树
CNode* m_pRChild;//右子树
CNode* m_pParent;//父节点
public:
CNode(int nData,int nBF,CNode* pParent,CNode* pLChild,CNode* pRChild)
:m_nData(nData),m_nBF(nBF),m_pParent(pParent),m_pLChild(pRChild),m_pRChild(pRChild)
{

}

int GetBF() const { return m_nBF;}
int ModifyBF(int nIncrement) { m_nBF += nIncrement; return m_nBF; }

int GetData() const { return m_nData; }
void SetData(int nNewData) { m_nData = nNewData;}

CNode* GetLChild() const { return m_pLChild; }
CNode* SetLChild(CNode* pNode) { m_pLChild = pNode; return m_pLChild;}

CNode* GetRChild() const { return m_pRChild; }
CNode* SetRChild(CNode* pNode) { m_pRChild = pNode; return m_pRChild; }

CNode* GetParent() const { return m_pParent; }
CNode* SetParent(CNode* pNode) { m_pParent = pNode; return m_pParent; }
void PutNode()
{
cout< }
};

//AVL树
class CAVLTree
{
private:
CNode* m_pRoot;//树根
CNode* m_pCurrentNode;//当前节点
public:
CAVLTree():m_pRoot(NULL),m_pCurrentNode(NULL){}
bool InsertNode(int nNodeValue);
bool RotateSubTree(CNode* pSubTreeRoot,int nBF);//旋转子树返回新的树根节点
CNode* LL(CNode* pSubTreeRoot);//LL型时进行的旋转操作
CNode* RR(CNode* pSubTreeRoot);//RR型时进行的旋转操作
CNode* LR(CNode* pSubTreeRoot);//LL型时进行的旋转操作,
//接上-这种操作又细分为LR:R和LR:L其实都是一样,区别在于旋转后对LR:R中冒号前面的R节点的子节点(冒号后面的R节点)放在新树的右子树根的左孩子处(LR:R)
//还是将旋转后的对LR:L中冒号前面的L节点的子节点(冒号后面的L节点)放在新树的左子树根的右孩子处(LR:L)
CNode* RL(CNode* pSubTreeRoot);//RR型时进行的旋转操作
//接上-这种操作又细分为RL:L和RL:R其实都是一样,区别在于旋转后对RL:L中冒号前面的L节点的子节点(冒号后面的L节点)放在新树的左子树根的右孩子处(RL:L)
//还是将旋转后的对RL:R中冒号前面的L节点的子节点(冒号后面的R节点)放在新树的右子树根的左孩子处(RL:R)

void MidOrderParse(CNode *pRoot);

CNode* GetRoot() const { return m_pRoot;}

bool DeleteNode(int nTarget);

};

bool CAVLTree::InsertNode(int nNodeValue)
{

if(m_pRoot == NULL)//如果是空树
{
m_pRoot = new CNode(nNodeValue,0,NULL,NULL,NULL);
return true;
}

//否则进行搜寻
m_pCurrentNode = m_pRoot;//从树根开始搜索
CNode* pPreNode = NULL;//记录前一个访问的节点
while(m_pCurrentNode != NULL)
{
if (nNodeValueGetData())
{
pPreNode = m_pCurrentNode;
m_pCurrentNode = m_pCurrentNode->GetLChild();
}
else if (nNodeValue>m_pCurrentNode->GetData())
{
pPreNode = m_pCurrentNode;
m_pCurrentNode = m_pCurrentNode->GetRChild();
}
else
{
return false;//说明两个值相等,不需要插入,返回插入失败
}
}

//上面如果不返回false那么pPreNode所指向的位置即为要插入新节点叶节点
if (nNodeValue>pPreNode->GetData())
{
CNode* pNewNode = new CNode(nNodeValue,0,pPreNode,NULL,NULL);
pPreNode->SetRChild(pNewNode);
pPreNode->ModifyBF(-1);//将当前节点的
pNewNode->SetParent(pPreNode);
if (pPreNode->GetBF()==0)
{
return true;
}
}
else
{
CNode* pNewNode = new CNode(nNodeValue,0,pPreNode,NULL,NULL);
pPreNode->SetLChild(pNewNode);
pPreNode->ModifyBF(1);
pNewNode->SetParent(pPreNode);
if (pPreNode->GetBF()==0)
{
return true;
}
}

//以pPreNode为出发点,向Root回溯修改各个父节点的BF,如果发现某一时刻需要*衡则*衡
m_pCurrentNode = pPreNode;
while(m_pCurrentNode!=m_pRoot)
{
if (m_pCurrentNode->GetData()GetParent()->GetData())//小于父节点说明是左树,那么父节点的BF加一
{
m_pCurrentNode = m_pCurrentNode->GetParent();//回溯一个节点指向父节点
m_pCurrentNode->ModifyBF(1);//加一

//加1后看是否变为了2,如果变为了2要进行*衡
if (m_pCurrentNode->GetBF()==2)
{
RotateSubTree(m_pCurrentNode,2);//对以m_pCurrentNode所指节点为根的子树进行旋转
return true;//旋转后肯定就*衡了
}
else if (m_pCurrentNode->GetBF()==0)
{
return true;//直接*衡了
}
}
else
{
m_pCurrentNode = m_pCurrentNode->GetParent();
m_pCurrentNode->ModifyBF(-1);//减1
if (m_pCurrentNode->GetBF()==-2)
{
RotateSubTree(m_pCurrentNode,-2);//对以m_pCurrentNode所指节点为根的子树进行旋转
return true;//旋转后肯定就*衡了
}
else if (m_pCurrentNode->GetBF() == 0)
{
return true;//直接*衡,效果就好比原先已经有一个左子节点,现在又插入一个右子节点完全不影响*衡性。
}
}
}

return true;
}

bool CAVLTree::RotateSubTree(CNode* pSubTreeRoot,int nBF)
{
bool bDepthChange = true;
CNode* pNewRoot = NULL;
if (nBF == 2)//L
{
int nLChildBF = pSubTreeRoot->GetLChild()->GetBF();
if (nLChildBF == 1)//LL
{
pNewRoot = LL(pSubTreeRoot);
}
else if(nLChildBF == -1)//LR
{
pNewRoot = LR(pSubTreeRoot);
}
else//左孩子为0,删除时候才回出现
{
pNewRoot = LL(pSubTreeRoot);
bDepthChange = false;
}
}
else if (nBF == -2)
{
int nRChildBF = pSubTreeRoot->GetRChild()->GetBF();
if (nRChildBF == -1)//RR
{
pNewRoot = RR(pSubTreeRoot);
}
else if(nRChildBF == 1)//RL
{
pNewRoot = RL(pSubTreeRoot);
}
else//当旋转根右孩子的BF为0时,只有删除时才会出现
{
pNewRoot = RR(pSubTreeRoot);
bDepthChange = false;
}
}

//将旋转后的子树接到原先的大树中
if (pSubTreeRoot == m_pRoot)//说明进行旋转操作的子书就是整棵大树,因此旋转后的子树根节点应该是整个大树的根节点
{
m_pRoot = pNewRoot;
}
else
{
/*pNewRoot->SetParent(pSubTreeRoot->GetParent());*/
if (pNewRoot->GetData()GetParent()->GetData())
{
pNewRoot->GetParent()->SetLChild(pNewRoot);
}
else
{
pNewRoot->GetParent()->SetRChild(pNewRoot);
}
}

return bDepthChange;//返回旋转时有没有改变数目的深度(高度)来区分是插入节点还是删除节点
}


CNode* CAVLTree::LL( CNode* pSubTreeRoot )
{
CNode* pNewRootNode = NULL;//定义旋转后的新节点
pNewRootNode = pSubTreeRoot->GetLChild();//首先确定新的根节点的位置
//保护好整个子树的父节点
CNode* pTreeParent = pSubTreeRoot->GetParent();

if (pNewRootNode->GetBF() == 1)//正常的LL型必然满足
{

//以下是pNewRootNode有右孩子和没右孩子的特性
if (pNewRootNode->GetRChild() != NULL)
{
pNewRootNode->GetParent()->SetLChild(pNewRootNode->GetRChild());//将右孩子放到新右子树的左孩子处

pNewRootNode->GetRChild()->SetParent(pNewRootNode->GetParent());
pNewRootNode->SetRChild(pNewRootNode->GetParent());//和右子树交换父子关系
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->SetParent(pTreeParent);//设置正确的父节点
}
else
{
pNewRootNode->SetRChild(pNewRootNode->GetParent());//和右子树根节点(原父节点)交换父子关系
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->GetParent()->SetLChild(NULL);
pNewRootNode->SetParent(pTreeParent);//设置正确的父节点
}

//以下是各种情况下的LL所具备的共性,改变相应节点的*衡因子
pNewRootNode->ModifyBF(-1);//设置为0
pNewRootNode->GetRChild()->ModifyBF(-2);//设置为0;

}
else if (pNewRootNode->GetBF() == 0)//正常的LL型必然满足
{//pNewRootNode->GetBF() == 0的情况,此时又是删除节点时发生的

pNewRootNode->GetParent()->SetLChild(pNewRootNode->GetRChild());
pNewRootNode->GetRChild()->SetParent(pNewRootNode->GetParent());
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->SetRChild(NULL);
pNewRootNode->SetParent(pTreeParent);

//修正*衡因子
pNewRootNode->ModifyBF(-1);
pNewRootNode->GetRChild()->ModifyBF(-1);
}

return pNewRootNode;
}

CNode* CAVLTree::RR( CNode* pSubTreeRoot )
{
CNode* pNewRootNode = NULL;//定义旋转后的新节点
pNewRootNode = pSubTreeRoot->GetRChild();//首先确定新的根节点的位置
//保护好整个子树的父节点
CNode* pTreeParent = pSubTreeRoot->GetParent();

if (pNewRootNode->GetBF() == -1)//正常的RR型必然满足
{

//以下是pNewRootNode有左孩子和没左孩子的特性
if (pNewRootNode->GetLChild() != NULL)
{
pNewRootNode->GetParent()->SetRChild(pNewRootNode->GetLChild());//将左孩子放到新左子树的右孩子处
pNewRootNode->GetLChild()->SetParent(pNewRootNode->GetParent());
pNewRootNode->SetLChild(pNewRootNode->GetParent());//和新左子树根节点(原父节点)交换父子关系
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->SetParent(pTreeParent);
}
else
{
pNewRootNode->SetLChild(pNewRootNode->GetParent());//和右子树交换父子关系
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->GetParent()->SetRChild(NULL);
pNewRootNode->SetParent(pTreeParent);
}

//以下是各种情况下的LL所具备的共性,改变相应节点的*衡因子
pNewRootNode->ModifyBF(1);//设置为0
pNewRootNode->GetLChild()->ModifyBF(2);//设置为0;

}
else if (pNewRootNode->GetBF() == 0)//pNewRootNode->GetBF() == 0的情况,此时仅仅在删除节点时发生的
{
pNewRootNode->GetParent()->SetRChild(pNewRootNode->GetLChild());
pNewRootNode->GetLChild()->SetParent(pNewRootNode->GetParent());
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->SetLChild(pNewRootNode->GetParent());
pNewRootNode->SetParent(pSubTreeRoot);

//修正*衡因子
pNewRootNode->ModifyBF(1);
pNewRootNode->GetLChild()->ModifyBF(1);
}

return pNewRootNode;
}

CNode* CAVLTree::LR( CNode* pSubTreeRoot )
{
CNode* pNewRootNode = NULL;//定义旋转后的新节点
CNode* pTreeParent = pSubTreeRoot->GetParent();//保护整棵树的父节点
pNewRootNode = pSubTreeRoot->GetLChild()->GetRChild();

//判断是LR:R型还是LR:L型
if (pNewRootNode->GetBF()==-1)//LR:R
{
//特别注意的一个大bug是LR:R类型时并不是代表其左边没有子树了,仍然可能实际存在两颗子树
if (pNewRootNode->GetLChild()!=NULL)//说明他同时还存在左子树,把左子树保护起来
{
//先左旋
pNewRootNode->GetParent()->SetRChild(pNewRootNode->GetLChild());
pNewRootNode->GetLChild()->SetParent(pNewRootNode->GetParent());

pNewRootNode->SetLChild(pNewRootNode->GetParent());
pSubTreeRoot->SetLChild(pNewRootNode);
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->SetParent(pSubTreeRoot);

}
else
{
//先左旋
pNewRootNode->SetLChild(pNewRootNode->GetParent());

pSubTreeRoot->SetLChild(pNewRootNode);
pNewRootNode->GetParent()->SetRChild(NULL);
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->SetParent(pSubTreeRoot);
}


//第一次左旋完成,接着进行右旋
/*pNewRootNode = pSubTreeRoot->GetLChild();*/
//再次手动操作,但也可以调用LL函数
pNewRootNode->GetRChild()->SetParent(pNewRootNode->GetParent());
pNewRootNode->GetParent()->SetLChild(pNewRootNode->GetRChild());

pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->SetRChild(pNewRootNode->GetParent());
pNewRootNode->SetParent(pTreeParent);

//改变相应节点的BF
pNewRootNode->GetLChild()->ModifyBF(2);//变为1;
pNewRootNode->GetRChild()->ModifyBF(-2);//变为0;
pNewRootNode->ModifyBF(1);//变为0;
}
else if (pNewRootNode->GetBF()==1)//LR:L
{

//先左旋
pSubTreeRoot->SetLChild(pNewRootNode);//
pNewRootNode->GetParent()->SetRChild(pNewRootNode->GetLChild());
pNewRootNode->GetLChild()->SetParent(pNewRootNode->GetParent());
pNewRootNode->SetLChild(NULL);
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->SetLChild(pNewRootNode->GetParent());
pNewRootNode->SetParent(pSubTreeRoot);


//再进行右旋
//同样特别注意的一个大bug是LR:L类型时并不是代表其右边没有子树了,仍然可能实际存在两颗子树
if (pNewRootNode->GetRChild()!=NULL)//应当将其保护起来
{
//再进行右旋
pNewRootNode->GetParent()->SetLChild(pNewRootNode->GetRChild());
pNewRootNode->GetRChild()->SetParent(pNewRootNode->GetParent());

pNewRootNode->SetRChild(pNewRootNode->GetParent());
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->SetParent(pTreeParent);
}
else
{
//再进行右旋
pNewRootNode->SetRChild(pNewRootNode->GetParent());
pNewRootNode->GetParent()->SetLChild(NULL);
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->SetParent(pTreeParent);
}

//改变相应节点的*衡因子
pNewRootNode->GetLChild()->ModifyBF(1);//变为0
pNewRootNode->ModifyBF(-1);//变为0
pNewRootNode->GetRChild()->ModifyBF(-3);//变为-1
}
else//此种情况是等于0的情况
{
pSubTreeRoot->SetLChild(pNewRootNode);
pNewRootNode->SetLChild(pNewRootNode->GetParent());
pNewRootNode->GetParent()->SetRChild(NULL);
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->SetRChild(pSubTreeRoot);
pSubTreeRoot->SetParent(pNewRootNode);
pSubTreeRoot->SetLChild(NULL);
pNewRootNode->SetParent(pTreeParent);

//调整*衡因子
pNewRootNode->GetLChild()->ModifyBF(1);
pNewRootNode->GetRChild()->ModifyBF(-2);
}

return pNewRootNode;
}

CNode* CAVLTree::RL( CNode* pSubTreeRoot )
{
CNode* pNewRootNode = NULL;//定义旋转后的新节点
CNode* pTreeParent = pSubTreeRoot->GetParent();//保护整棵树的父节点
pNewRootNode = pSubTreeRoot->GetRChild()->GetLChild();

//判断是RL:L型还是RL:R型
if (pNewRootNode->GetBF() == 1)//RLL型
{
//特别注意的一个大bug是LR:R类型时并不是代表其右边没有子树了,仍然可能实际存在两颗子树
if (pNewRootNode->GetRChild()!=NULL)//说明他同时还存在右子树,把右子树保护起来
{
//先右旋
pNewRootNode->GetParent()->SetLChild(pNewRootNode->GetRChild());
pNewRootNode->GetRChild()->SetParent(pNewRootNode->GetParent());

pSubTreeRoot->SetRChild(pNewRootNode);
pNewRootNode->SetRChild(pNewRootNode->GetParent());
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->SetParent(pSubTreeRoot);

}
else
{
//先右旋
pSubTreeRoot->SetRChild(pNewRootNode);
pNewRootNode->SetRChild(pNewRootNode->GetParent());
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->GetParent()->SetLChild(NULL);
pNewRootNode->SetParent(pSubTreeRoot);
}


//再左旋
pNewRootNode->GetParent()->SetRChild(pNewRootNode->GetLChild());
pNewRootNode->GetLChild()->SetParent(pNewRootNode->GetParent());
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->SetLChild(pNewRootNode->GetParent());
pNewRootNode->SetParent(pTreeParent);

//设置*衡因子
pNewRootNode->ModifyBF(-1);//0
pNewRootNode->GetLChild()->ModifyBF(2);//0
pNewRootNode->GetRChild()->ModifyBF(-2);//-1
}
else if (pNewRootNode->GetBF() == -1)//RL:R型
{
//先右旋
pSubTreeRoot->SetRChild(pNewRootNode);
pNewRootNode->GetParent()->SetLChild(pNewRootNode->GetRChild());
pNewRootNode->GetRChild()->SetParent(pNewRootNode->GetParent());
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->SetRChild(pNewRootNode->GetParent());
pNewRootNode->SetParent(pSubTreeRoot);

//特别注意的一个大bug是LR:L类型时并不是代表其左边没有子树了,仍然可能实际存在两颗子树
if (pNewRootNode->GetLChild()!=NULL)//说明他同时还存在左子树,把左子树保护起来
{
//再左旋
pNewRootNode->GetParent()->SetRChild(pNewRootNode->GetLChild());
pNewRootNode->GetLChild()->SetParent(pNewRootNode->GetParent());

pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->SetLChild(pNewRootNode->GetParent());
pNewRootNode->SetParent(pTreeParent);
}
else
{
//再左旋
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->GetParent()->SetRChild(NULL);
pNewRootNode->SetLChild(pNewRootNode->GetParent());
pNewRootNode->SetParent(pTreeParent);
}


//再调整*衡因子
pNewRootNode->ModifyBF(1);//0
pNewRootNode->GetLChild()->ModifyBF(3);//1
pNewRootNode->GetRChild()->ModifyBF(-1);//0
}
else//0的情况,也就是最简单的RL形式
{
pSubTreeRoot->SetRChild(pNewRootNode);
pNewRootNode->GetParent()->SetParent(pNewRootNode);
pNewRootNode->GetParent()->SetLChild(NULL);
pNewRootNode->SetRChild(pNewRootNode->GetParent());
pNewRootNode->SetLChild(pSubTreeRoot);
pSubTreeRoot->SetRChild(NULL);
pSubTreeRoot->SetParent(pNewRootNode);
pNewRootNode->SetParent(pTreeParent);

//修改*衡因子
pNewRootNode->GetLChild()->ModifyBF(2);
pNewRootNode->GetRChild()->ModifyBF(-1);
}
return pNewRootNode;
}

//从节点pRoot开始中顺遍历AVL树,我们传入参数m_pRoot从排序特性上来检验一下书是不是*衡二叉树
void CAVLTree::MidOrderParse( CNode *pRoot )
{
if (m_pRoot == NULL)
{
cout<<"
这是一颗空树
";
return;
}
else
{
if (pRoot->GetLChild()!=NULL)
{
MidOrderParse(pRoot->GetLChild());//遍历左边子树
}

pRoot->PutNode();//输出中间节点
if (pRoot->GetRChild()!=NULL)
{
MidOrderParse(pRoot->GetRChild());//遍历右子树
}
}
}

//从节点pRoot开始中顺遍历AVL树,我们传入参数m_pRoot从排序特性上来检验一下书是不是*衡二叉树
void PutWrongNumber( CNode *pRoot )
{

if (pRoot->GetLChild()!=NULL)
{
PutWrongNumber(pRoot->GetLChild());//遍历左边子树
}
if (pRoot->GetBF()==0&&((pRoot->GetLChild()!=NULL&&pRoot->GetRChild()==NULL)||(pRoot->GetRChild()!=NULL&&pRoot->GetLChild()==NULL)))
{
cout<<" "<<"出错节点";
pRoot->PutNode();//输出中间节点
cout<<" ";
}

if (pRoot->GetRChild()!=NULL)
{
PutWrongNumber(pRoot->GetRChild());//遍历右子树
}

}


//删除指定节点的值
bool CAVLTree::DeleteNode( int nTarget )
{
//先查找AVL树中是否有该值
bool bFind = false;
CNode* pCurrentNode = m_pRoot;
while(pCurrentNode!=NULL)
{
if (nTargetGetData())
{
pCurrentNode = pCurrentNode->GetLChild();
}
else if (nTarget>pCurrentNode->GetData())
{
pCurrentNode = pCurrentNode->GetRChild();
}
else if (nTarget == pCurrentNode->GetData())
{
bFind = true;
break;
}
}

if (!bFind)//没找到对应节点就返回
{
return false;
}

//删除该节点
if (pCurrentNode->GetRChild()!=NULL&&pCurrentNode->GetLChild()!=NULL)//被删除的节点存在左右子树
{
CNode* pChildNode = pCurrentNode->GetLChild();
CNode* pTempNode = pChildNode;
CNode* pPreNodeInMidParse = pTempNode;
while (pTempNode->GetRChild()!=NULL)//获取应删除节点的中序遍历直接前驱节点
{
pTempNode = pTempNode->GetRChild();
pPreNodeInMidParse=pTempNode;

}

//用中序遍历前驱节点的值代替被删除节点的值
pCurrentNode->SetData(pPreNodeInMidParse->GetData());
if (pPreNodeInMidParse->GetParent() == pCurrentNode)
{
pCurrentNode->SetLChild(pPreNodeInMidParse->GetLChild());
if (pPreNodeInMidParse->GetLChild()!=NULL)
{
pPreNodeInMidParse->GetLChild()->SetParent(pCurrentNode);
}
delete pPreNodeInMidParse;//实质性删除
//还应该修改改点的BF,因为毕竟左树少了一个节点,那么应该减掉1
pCurrentNode->ModifyBF(-1);
}
else
{
pPreNodeInMidParse->GetParent()->SetRChild(pPreNodeInMidParse->GetLChild());
if(pPreNodeInMidParse->GetLChild()!=NULL)
{
pPreNodeInMidParse->GetLChild()->SetParent(pPreNodeInMidParse->GetParent());
}
pCurrentNode = pPreNodeInMidParse->GetParent();//指向回溯点
delete pPreNodeInMidParse;//实质性删除
//还应该修改改点的BF,因为对于删除点的父节点(回溯位置)来说毕竟右树少了一个节点,那么应该加1
pCurrentNode->ModifyBF(1);
}
}
else//这棵树没有子树或只有一个子树
{
CNode* pChildNode = pCurrentNode->GetLChild();
if (pChildNode == NULL)
{
pChildNode = pCurrentNode->GetRChild();//仍然可能是NULL
}

if (pCurrentNode!=m_pRoot)
{
if (pCurrentNode->GetData()GetParent()->GetData())//说明被删除节点是父节点的左孩子
{
pCurrentNode->GetParent()->SetLChild(pChildNode);//直接略过该节点
if (pChildNode!=NULL)
{
pChildNode->SetParent(pCurrentNode->GetParent());
}
CNode* delNode = pCurrentNode;
pCurrentNode = pCurrentNode->GetParent();
delete delNode;//实质性删除

//pCurrentNode = pChildNode;//让当前指针指着原先被删除节点的位置
//因为在左边删除了一个节点,自然是要将BF减1
pCurrentNode->ModifyBF(-1);
}
else
{
pCurrentNode->GetParent()->SetRChild(pChildNode);
if (pChildNode!=NULL)
{
pChildNode->SetParent(pCurrentNode->GetParent());
}
CNode* delNode = pCurrentNode;
pCurrentNode = pCurrentNode->GetParent();
delete delNode;//实质性删除
//pCurrentNode = pChildNode;//让当前指针指着原先被删除节点的位置
//因为在右边删除了一个节点,自然是要将BF加1
pCurrentNode->ModifyBF(1);
}
}
else
{
m_pRoot = pChildNode;
pChildNode->SetParent(NULL);
}

}

现在current指向了回溯的起点
//while (pCurrentNode!=m_pRoot)
//{

//}
m_pCurrentNode = pCurrentNode;//用成员变量来寻找
while(m_pCurrentNode!=m_pRoot)
{
if (m_pCurrentNode->GetData()GetParent()->GetData())//小于父节点说明是左树,那么父节点的BF加一
{
m_pCurrentNode = m_pCurrentNode->GetParent();//回溯一个节点指向父节点
m_pCurrentNode->ModifyBF(-1);//减掉1
/*if (mp)
{
}*/

//减掉1后看是否变为了-2,如果变为了-2要进行*衡
if (m_pCurrentNode->GetBF()==-2)
{
if (!RotateSubTree(m_pCurrentNode,-2))//对以m_pCurrentNode所指节点为根的子树进行旋转
{
return true;//旋转后,且高度没有降低,不必继续回溯
}
}
else if (m_pCurrentNode->GetBF()==1||m_pCurrentNode->GetBF()==-1)//说明只是删除了原先某个*衡位置的某个分支,也不需要回溯了
{
return true;//直接*衡了
}

//当然为0的情况代码子树的高度变低了,可能会影响到其它地方,需要继续回溯到上层节点去找寻是否存在不*衡的地方以便加以*衡
}
else
{
m_pCurrentNode = m_pCurrentNode->GetParent();
m_pCurrentNode->ModifyBF(1);//加1
if (m_pCurrentNode->GetBF()==2)
{
if (!RotateSubTree(m_pCurrentNode,2))//对以m_pCurrentNode所指节点为根的子树进行旋转
{
return true;//旋转后,且高度没有降低,不必继续回溯
}
}
else if (m_pCurrentNode->GetBF() == -1||m_pCurrentNode->GetBF() == 1)
{
return true;//直接*衡,说明只是删除了原先某个*衡位置的某个分支,也不需要回溯了。
}
//当然为0的情况代码子树的高度变低了,可能会影响到其它地方,需要继续回溯到上层节点去找寻是否存在不*衡的地方以便加以*衡
}
}

}




int _tmain(int argc, _TCHAR* argv[])
{
CAVLTree avlTree;
for (int i=0;i<60;i++)
{
int d=rand()%100;
avlTree.InsertNode(d);
//cout< //avlTree.MidOrderParse(avlTree.GetRoot());
PutWrongNumber(avlTree.GetRoot());
cout< }

avlTree.InsertNode(89);
avlTree.InsertNode(43);
avlTree.InsertNode(45);
avlTree.InsertNode(76);
avlTree.InsertNode(23);
avlTree.InsertNode(54);
avlTree.InsertNode(2);
avlTree.InsertNode(45);
avlTree.InsertNode(435);
avlTree.InsertNode(94);
avlTree.InsertNode(114);


avlTree.InsertNode(3);
PutWrongNumber(avlTree.GetRoot());
avlTree.InsertNode(36);
PutWrongNumber(avlTree.GetRoot());
avlTree.InsertNode(109);
PutWrongNumber(avlTree.GetRoot());
avlTree.InsertNode(78);
PutWrongNumber(avlTree.GetRoot());
avlTree.InsertNode(98);
PutWrongNumber(avlTree.GetRoot());
avlTree.InsertNode(29);
PutWrongNumber(avlTree.GetRoot());
avlTree.InsertNode(13);
PutWrongNumber(avlTree.GetRoot());
avlTree.InsertNode(90);
PutWrongNumber(avlTree.GetRoot());
avlTree.InsertNode(1);
PutWrongNumber(avlTree.GetRoot());
avlTree.InsertNode(49);
PutWrongNumber(avlTree.GetRoot());

avlTree.InsertNode(56);
PutWrongNumber(avlTree.GetRoot());
avlTree.InsertNode(23);
PutWrongNumber(avlTree.GetRoot());
avlTree.InsertNode(34);
PutWrongNumber(avlTree.GetRoot());
avlTree.InsertNode(789);
PutWrongNumber(avlTree.GetRoot());
avlTree.InsertNode(21);

// //LL型测试用例
//avlTree.InsertNode(50);
//PutWrongNumber(avlTree.GetRoot());
//avlTree.InsertNode(25);
//PutWrongNumber(avlTree.GetRoot());
//avlTree.InsertNode(10);
//PutWrongNumber(avlTree.GetRoot());
//avlTree.InsertNode(40);
//PutWrongNumber(avlTree.GetRoot());
//avlTree.InsertNode(70);
//avlTree.InsertNode(5);


RR型测试用例
//avlTree.InsertNode(25);
//avlTree.InsertNode(10);
//avlTree.InsertNode(50);
//avlTree.InsertNode(70);
//avlTree.InsertNode(40);
//avlTree.InsertNode(90);


LR:L型测试用例
//avlTree.InsertNode(50);
//avlTree.InsertNode(25);
//avlTree.InsertNode(70);
//avlTree.InsertNode(10);
//avlTree.InsertNode(40);
//avlTree.InsertNode(32);

LR:R型测试用例
//avlTree.InsertNode(50);
//avlTree.InsertNode(25);
//avlTree.InsertNode(70);
//avlTree.InsertNode(10);
//avlTree.InsertNode(40);
//avlTree.InsertNode(46);

RL:L型测试用例
//avlTree.InsertNode(25);
//avlTree.InsertNode(10);
//avlTree.InsertNode(50);
//avlTree.InsertNode(40);
//avlTree.InsertNode(70);
//avlTree.InsertNode(32);

RL:R型测试用例
//avlTree.InsertNode(25);
//avlTree.InsertNode(10);
//avlTree.InsertNode(50);
//avlTree.InsertNode(70);
//avlTree.InsertNode(40);
//avlTree.InsertNode(43);

cout< avlTree.MidOrderParse(avlTree.GetRoot());
cout< avlTree.DeleteNode(12);
/*avlTree.DeleteNode(70);*/
avlTree.MidOrderParse(avlTree.GetRoot());
return 0;
}








我随机生成了一些数字,同时手动插入了一些数字,其运行效果如下:






大致可见二叉*衡树是建立成功了,如果要彻底证明这是一颗*衡树而不仅仅是排序树,可以检索树的深度来证实。


小结:个人觉得不必要看代码,看着也费尽,最好的办法是看二叉树的特征,明白这到底是什么,在插入删除的时候会发生什么特征的改变,然后自己依照这些特征写代码。


体会:一点体会是在学校里面的时候一提到这些数据结构就害怕,就不想去碰,原因是不知道他们的用处,更不知道他们的用途,以及他们为什么叫这样的名字,其实细细体味,才发现原来二叉*衡树的名字是如此的形象,以及它是如此有用而有趣的一种结构,通过这次我加上了父节点指针带来的麻烦,更是体会到了计算机里面的结构为什么要么是顺序结构,要么是树,而不是别的特别复杂的网状结构,首先计算机程序的主要特性就是做判断进行流动。而树正是具有这样的特性,将数据以树的形式聚合在一块,可以很方便通过程序的选择判断找到任何一个节点,并且节点的添加删除也是比较容易维护的。如果将数据以网状结构聚合在一起,那么这样的数据集合虽然四通八达,但是一旦有节点的变动,要从新建立一张符合规则的网所付出的代价将是很大的。因此在你获得好处的同时也必然要付出代价。目前二叉树是一个很好的折中选择,同样你也能明白为什么3叉树,4叉树等结构的应用比较罕见。



相关推荐

最新更新

猜你喜欢