首页所有驱动分类下载数据挖掘与人工智能搜索引擎与SEO技术备忘录站长随笔

详解平衡二叉树原理与各种增删操作

2020-02-21 数据结构 浏览次数:46
 
排序二叉树的定义: 每一个节点的值比它所有的左节点都值大,比它所有的右节点小,简单的说,左边的节点值比右边的节点值小。另外要注意的是,每个节点的值都是唯一的,没有重复。

下图就是一个排序二叉树:



排序二叉树的思想,跟二分查找的思想类似,但其中的结构又稍微比二分查找的复杂点。二分查找数据结构是一个顺序链表,每个点存储的都是相邻的节点地址;而排序二叉树其中一些节点存储的是另外节点的地址,而不是相邻节点的地址。

往排序二叉树的添加数据的规则为:

若二叉树为空,将新数据成为根节点;

如果新数据比节点值小,如果节点没左子树,则将新数据成为节点的左子树;如果节点有左子树,新数据继续跟左子树对比;

如果新数据比节点值大,如果节点没右子树,则将新数据成为节点的右子树;如果节点有右子树,新数据继续跟右子树对比;

但是排序二叉树也有缺点,同样的一组数据,添加顺序不同,导致树的结构也大不相同。例如,有6个数值,分别是:1,2,3,4,5,6。

如果按照4,2,3,1,6,5的顺序添加到树里面,则是一个比较合理的二叉树,但是如果把输入数据的顺序改为:1,2,3,4,5,6的话,那么这个二叉树就变成了一个链表一样的结构了,这时候看起来非常不合理,也增加了搜索数据的时间。下图就是两种输入顺序生成的二叉树:



为了避免产生这种不合理(畸形)的二叉树,看来需要稍微再增加点规则,尽可能的让每一个节点都有两片叶子,以便生成的二叉树更加趋向于饱满。

于是,在排序二叉树的定义基础上,再增加一些定义规则:以任意一个节点看作树的根节点,必须是一颗排序二叉树或者是叶子,而且如果这个节点不是叶子的话,其左右两边的子树最大深度差,不能大于1

这样一来,拥有这种定义的树就成了:平衡二叉树

关于节点深度值的约定:

空节点,其深度为负1
叶子节点,其深度为零;
非叶子节点(即:有子节点的节点),其深度值就是其中一个拥有最大深度值的子节点的深度值 + 1 (例如:一个子节点深度值为2,另一个子节点深度值为4,那么这个节点的深度值就是5=4+1);

如果要生成平衡二叉树,看来得修改一下数据的插入规则:

1 继续使用排序二叉树的插入数据规则
2 当新数据成功插入后,继续执行以下新规则:

如果新节点兄弟节点,说明被插入节点的深度没有发生变化,不需要做下一步处理。
如果新节点没有兄弟节点,说明被插入节点的深度发生了变化。从被插入点开始,由下往上逐层判断每一个节点的左右两边的子树的最大深度差,如果小于1,则不处理,如果大于1,那么这个节点被称为不平衡点,则需要做下面的处理,分四种情况:

新节点数据值小于不平衡点,然后继续跟不平衡点左子树的值进行对比,根据下面两种情况作出相应处理:

1:新节点值小于不平衡点左子树的值,那么对不平衡点执行右旋操作(TurnRight函数)
2:新节点值大于不平衡点左子树的值,那么先对不平衡点的左子树执行左旋,然后再对不平衡点执行右旋操作(TurnLeftNodeLR函数)

新节点数据值大于不平衡点,然后继续跟不平衡点右子树的值进行对比,根据下面两种情况作出相应处理:

1:新节点值大于不平衡点右子树的值,那么对不平衡点执行左旋操作(TurnLeft函数)
2:新节点值小于不平衡点右子树的值,那么先对不平衡点的右子树执行右旋,然后对不平衡点执行左旋操作(TurnRightNodeRL函数)


从不平衡点开始,如果用新节点往下移动的走向作为方向参考的话,上面的旋转规则可以用一句口诀来记:左左就右旋,右右就左旋,左右就左右旋,右左就右左旋

最后有个小技巧,可以减少程序运行时间,由于找到了不平衡点,将其旋转调整后,不需要递归执行下去了,停止递归,函数终止。新数据插入算法是AddNode函数。

关于旋转的操作方法,下图是右旋和左旋的操作,左图是旋转前的样子,右图是旋转后的最终结果。例子1和2都是对顶点进行右旋操作,例子3和4都是对顶点进行左旋操作。



右旋操作步骤

1 如果被旋转节点的左子节点有右子节点的话,此右子节点成为被旋转节点的左子节点。例2中,被旋转点5的左子节点是3,节点3的右子节点是4,所以节点4成为被旋转点5的左子节点。
2 被旋转节点成为其左子节点的右子节点。例1中,被旋转点3的左子节点是2,所以被旋转点3成为节点2的右子节点。例2中也一样,被旋转点5成为节点3的右子节点。

左旋操作步骤

1 如果被旋转节点的右子节点有左子节点的话,此左子节点成为被旋转节点的右子节点。例4中,被旋转点2的右子节点是4,节点4的左子节点是3,所以节点3成为被旋转点2的右子节点。
2 被旋转节点成为其右子节点的左子节点。例3中,被旋转点1的右子节点是2,所以被旋转点1成为节点2的左子节点。例4中也一样,被旋转点2成为节点4的左子节点。

接下来,该讲下删除算法了,删除算法和插入算法部份很相似,但是又有点区别,因为删除算法中有时候可以直接删除节点,也有时候要将某个底部的节点提上来,顶替删除点的位置。虽然稍微比插入算法复杂点,但是也不难。

找到删除点后,删除规则:

第一步要做的事情:找到要删除的节点,抽取底部某个节点进行顶替,定位检查起始点。

如果删除节点是叶子,那么直接删除,此时这个位置的父节点看作是检查起始点。

如果删除点只有一个子节点,把这个子节点替代删除点的位置,删除点位置的父节点看作是检查起始点。

如果删除点有两个子节点,找到最深的一个子节点,如果左子树最深,那么将左子树的最大值节点顶替删除点的位置;如果右子树最深,那么将右子树的最小值节点顶替删除点的位置;实际上,底部的某个节点被抽调上去顶替了删除点,此时,被抽调上去的底部叶子节点,这个叶子的父节点看作是检查起始点

第二步要做的事情:逐层检查每个节点,是否为平衡点,如果不平衡,就进行旋转调整。

从检查起始点点开始,由下往上逐层判断每一个节点的左右两边的子树的最大深度差,如果小于1,则不处理,如果大于1,那么当前节点被称为不平衡点,则需要做下面的处理,分四种情况:

如果不平衡点的左子树比右子树深,根据下面两种情况作出相应:

1 如果不平衡点的左子树的左子节点深度大于或等于不平衡点的左子树的右子节点的深度,那么对不平衡点执行右旋操作(TurnRight函数)
2 如果不平衡点的左子树的左子节点深度小于不平衡点的左子树的右子节点的深度,那么先对不平衡点的左子树执行左旋,然后对不平衡点执行右旋操作(TurnLeftNodeLR函数)

如果不平衡点的右子树比左子树深,根据下面两种情况作出相应:

1 如果不平衡点的右子树的左子节点深度小于或等于不平衡点的右子树的右子节点的深度,那么对不平衡点执行左旋操作(TurnLeft函数)
2 如果不平衡点的右子树的左子节点深度大于不平衡点的右子树的右子节点的深度,那么先对不平衡点的右子树执行右旋,然后对不平衡点执行左旋操作(TurnRightNodeRL函数)


从不平衡点开始,如果用第一层子节点,和第二层节点的深度值作为作为方向参考的话,上面的旋转规则口诀跟插入是一样:左左就右旋,右右就左旋,左右就左右旋,右左就右左旋。

下图有连个删除节点的例子,从左往右看。

例子5:删除节点5。

由于节点5是叶子节点,所以可以直接删除这个节点,删除之后它的父节点(节点4)就是检查起始点。由于节点4没有右子树,这时候右子树的深度值为-1,而它的左子树深度1,1减去负1等于2,所以节点4是不平衡点。符合这条规则:


如果不平衡点的左子树比右子树深,根据下面两种情况作出相应:

1 如果不平衡点的左子树的左子节点深度大于或等于不平衡点的左子树的右子节点的深度,那么对不平衡点执行右旋操作(TurnRight函数)



根据规则,对节点4进行右旋,就得到最终的结果(图三)。



上图中的例子6,删除节点6:

删除节点6值后,如图二。由于节点6只有一个子节点,所以节点7很自然的就顶替了节点6的位置。由于节点6的父节点是节点5,所以就从节点5开始进行逐层检查,看看它是否平衡点。很明显节点5不是一个平衡点,符合这条规则:


如果不平衡点的左子树比右子树深,根据下面两种情况作出相应:

2 如果不平衡点的左子树的左子节点深度小于不平衡点的左子树的右子节点的深度,那么先对不平衡点的左子树执行左旋,然后对不平衡点执行右旋操作(TurnLeftNodeLR函数)



对不平衡点的左子树进行左旋(其实就是对节点2进行左旋),得到了图三的结果;然后再对不平衡点进行右旋操作(其实就是对节点5进行右旋操作),得到了图四的结果。

还有一个例子7,下图:



按照这个规则删除节点6之后,得到图二:


如果删除点有两个子节点,找到最深的一个子节点,如果左子树最深,那么将左子树的最大值节点顶替删除点的位置;此时,被抽调上去的底部叶子节点,这个叶子的父节点看作是检查起始点。


安装上面的规则,很明显,左子树深度最大,所以左子树的最大值节点5被抽调上去,顶替节点6的位置了,而节点5在没有被抽调前,它的原父节点是节点4,这个时候的检查起始点是节点4,节点4属于不平衡点,所以必须进行旋转处理,根据下面的规则判断:


如果不平衡点的左子树比右子树深,根据下面两种情况作出相应:

1 如果不平衡点的左子树的左子节点深度大于或等于不平衡点的左子树的右子节点的深度,那么对不平衡点执行右旋操作(TurnRight函数)



对节点4进行右旋操作,就得到了图三的结果,继续逐层往上检查,一直检查到整棵树的根节点(节点9),没有发现不平衡点,所以整棵树就是一个平衡二叉树。

最后,平衡二叉树还有个特点,任意一个子节点,它的左右两边的最大深度值和最小深度值的差,不会大于2,只会小于或等于2。所以,平衡二叉树是一颗比较饱满的树。

其实平衡二叉树并不复杂,只是判断条件多,分支多。

下面的代码可以直接编译运行(编译环境VC6,越古老越喜欢):


#include <stdlib.h>
#include <memory.h>
#include <stdio.h>
#include <iostream.h>


// 树节点结构
typedef struct _TreeNode{
int NodeKey; // 节点键值
int Depth; // 子树的最大深度值
_TreeNode* left; // 左子节点
_TreeNode* right; // 右子节点
}TTreeNode, *PTreeNode;

/*
不依靠节点结构其他变量,用递归的方法,获取一个节点下的最大深度值,但数据里大的话,耗时间长

思路:当前节点所在层数大于最深层数值,最深层数值+1

参数:
M: 节点所在层数
N: 记录已探索到最深的层数
*/
void NodeDepth_1(PTreeNode Node,int M,int* N)
{
if (!Node) return;

M++;
if (M > *N) *N=*N+1;

if (Node->left) NodeDepth_1(Node->left,M,N);
if (Node->right) NodeDepth_1(Node->right,M,N);
}

// 利用节点结构里内部的最大深度值,计算一个节点的最大深度值,速度快
int NodeDepth_2(PTreeNode Node)
{
int intResult=0;

if (!Node) return intResult;

// 分别获取左右两边子节点的深度
int LD=-1;
if (Node->left) LD=Node->left->Depth;

int RD=-1;
if (Node->right) RD=Node->right->Depth;

// 节点的最大深度值 等于 深度值最大的子树的值 + 1
int MaxDepth=LD;
if (LD < RD) MaxDepth=RD;

intResult=MaxDepth+1;

return intResult;
}

// 判断一棵树是否为平衡二叉树
bool TreeBalanced(PTreeNode RootNode)
{
bool bolResult=true;

if (!RootNode) return bolResult;

// 计算两边子节点的最大深度值

/*
// 计算深度的方法1,不依赖节点上的额外存储信息但耗时
int LD=0;
if (RootNode->left){
LD=0;
NodeDepth_1(RootNode->left,0,&LD);
}

int RD=0;
if (RootNode->right){
RD=0;
NodeDepth_1(RootNode->right,0,&RD);
}
*/

// 计算深度的方法2,需要节点存储最大深度值,但非常快
int LD=-1;
if (RootNode->left) LD=RootNode->left->Depth;
int RD=-1;
if (RootNode->right) RD=RootNode->right->Depth;

int D=LD-RD;
if (LD < RD) D=RD-LD;
// 两边节点的最大深度差大于1,肯定不是平衡二叉树
if (D > 1) bolResult=false;

// 左边的值大于或等于右边的值,肯定不是平衡二叉树
if (bolResult && RootNode->left && RootNode->right){
if (RootNode->left->NodeKey >= RootNode->right->NodeKey) bolResult=false;
}

if (bolResult && RootNode->left) bolResult=TreeBalanced(RootNode->left);
if (bolResult && RootNode->right) bolResult=TreeBalanced(RootNode->right);

return bolResult;
}

// 将节点左旋
PTreeNode TurnLeft(PTreeNode RootNode)
{
if (!RootNode) return 0;

PTreeNode SonNode=RootNode->right;
RootNode->right=SonNode->left;
SonNode->left=RootNode;

// 左旋转后,根节点变成了左节点,更新此点的深度值
SonNode->left->Depth=NodeDepth_2(SonNode->left);

// 原来的右子树移动到根节点的位置,更新此节点的深度值
SonNode->Depth=NodeDepth_2(SonNode);

return SonNode;
}

// 将节点右旋
PTreeNode TurnRight(PTreeNode RootNode)
{
if (!RootNode) return 0;

PTreeNode SonNode=RootNode->left;
RootNode->left=SonNode->right;
SonNode->right=RootNode;

// 右旋转后,根节点变成了右节点,更新此点的深度值
SonNode->right->Depth=NodeDepth_2(SonNode->right);

// 原来的左子树移动到根节点的位置,更新此节点的深度值
SonNode->Depth=NodeDepth_2(SonNode);

return SonNode;
}

// 先将节点下的第一层左子树左旋,然后再将节点右旋
PTreeNode TurnLeftNodeLR(PTreeNode RootNode)
{
if (!RootNode) return 0;

PTreeNode SonNode=TurnLeft(RootNode->left);
RootNode->left=SonNode;
SonNode=TurnRight(RootNode);

return SonNode;
}

// 先将节点下的第一层右子树右旋,然后再将节点左旋
PTreeNode TurnRightNodeRL(PTreeNode RootNode)
{
if (!RootNode) return 0;

PTreeNode SonNode=TurnRight(RootNode->right);
RootNode->right=SonNode;
SonNode=TurnLeft(RootNode);

return SonNode;
}

/*
往树添加新数据

返回值

0: 已经将不平衡点调平,停止递归
1: 添加新数据成功,树的深度没有变化
2: 添加新数据成功,树的深度增加了1层
*/
int AddNode(PTreeNode* TopRootNode, PTreeNode newNode)
{
int intResult=0;

if (!(*TopRootNode)) return intResult;

PTreeNode RootNode=*TopRootNode;

if (!RootNode || !newNode) return intResult;

// 平衡二叉树不允许有任意两个节点的值相同
if (newNode->NodeKey==RootNode->NodeKey) return intResult;

if (newNode->NodeKey < RootNode->NodeKey){
// 新节点值小于当前节点值,往左子树遍历
if (RootNode->left){
intResult=AddNode(&RootNode->left,newNode);
}
else{
// 成为左叶子
RootNode->left=newNode;
intResult=1;
// 如果右边为空,这个节点深度增加了
if (!RootNode->right) intResult=2;
}
}
else{
// 新节点值大于当前节点值,往右子树遍历
if (RootNode->right){
intResult=AddNode(&RootNode->right,newNode);
}
else{
// 成为右叶子
RootNode->right=newNode;
intResult=1;
// 如果左边为空,这个节点深度增加了
if (!RootNode->left) intResult=2;
}
}

if (intResult==2){
// 如果当前节点或当前节点的某一个子节点深度发生变化

// 更新当前节点的深度值
RootNode->Depth=NodeDepth_2(RootNode);

// 分别获取左右两边子节点的深度
int LD=-1;
if (RootNode->left) LD=RootNode->left->Depth;
int RD=-1;
if (RootNode->right) RD=RootNode->right->Depth;

// 如果当前节点左右两边子树的深度差大于1,那么当前节点就是不平衡点
int D=LD-RD;
if (LD < RD) D=RD-LD;

if (D > 1){
if (newNode->NodeKey < RootNode->NodeKey){
// 新节点数据值小于不平衡点,所以在不平衡点的左边
PTreeNode NextNode=RootNode->left;
if (newNode->NodeKey < NextNode->NodeKey){
// 如果新节点数据小于不平衡点左子树的值,那么对不平衡点执行右旋操作
*TopRootNode=TurnRight(RootNode);
}
else{
// 如果新节点数据大于不平衡点左子树的值,那么先对不平衡点的左子树执行左旋,然后对不平衡点执行右旋操作
*TopRootNode=TurnLeftNodeLR(RootNode);
}
}
else{
// 新数据值大于不平衡点,所以在不平衡点的右边
PTreeNode NextNode=RootNode->right;
if (newNode->NodeKey > NextNode->NodeKey){
// 如果新节点数据大于不平衡点右子树的值,那么对不平衡点执行左旋操作
*TopRootNode=TurnLeft(RootNode);
}
else{
// 如果新节点数据小于不平衡点右子树的值,那么先对不平衡点的右子树执行右旋,然后对不平衡点执行左旋操作
*TopRootNode=TurnRightNodeRL(RootNode);
}
}

// 由于找到了不平衡点,并且已经将其调平,所以不需要递归执行下去了,停止递归
intResult=0;
} // end if (D > 1)
} // end if (intResult==2)

return intResult;
}

/*
对一颗平衡二叉树删除某个节点

返回值:

0: 函数执行失败
1: 找到了删除点,深度没发生变化
2: 找到了删除点,深度发生变化
*/
int DelNode(PTreeNode* TopRootNode, int delNodeKey)
{
int intResult=0;

if (!(*TopRootNode)) return intResult;

PTreeNode RootNode=*TopRootNode;

if (!RootNode) return intResult;

if (delNodeKey==RootNode->NodeKey){
// 找到了要删除的节点

bool bolDelNode=false;
if (!RootNode->left && !RootNode->right){
// 这个节点左右子节点都是空的,则是叶子,直接删除
*TopRootNode=0;
// 高度发生了变化
intResult=2;
bolDelNode=true;
}
else{
// 否则,这个节点至少有一个子节点不是空的

if (RootNode->left && RootNode->right){
// 两个子节点都不空

// 分别获取左右两边子节点的深度
int LD=RootNode->left->Depth;
int RD=RootNode->right->Depth;

if (LD >= RD){
// 如果左子树比右子树深,找到左子树最大值的节点(其实就是最右边的节点),找到后将节点里的数据拷贝到要删除的节点
PTreeNode FindNode=RootNode->left;
while (FindNode){
if (!FindNode->right){
RootNode->NodeKey=FindNode->NodeKey;
break;
}
FindNode=FindNode->right;
}
// 再次调用递归函数,将左子树最大值的节点删除
intResult=DelNode(&RootNode->left,FindNode->NodeKey);
// 重新计算此节点的最大深度值
RootNode->Depth=NodeDepth_2(RootNode);
}
else{
// 如果右子树比左子树深,找到右子树的最小值节点(其实就是最左边的节点),找到后将节点里的数据拷贝到要删除的节点
PTreeNode FindNode=RootNode->right;
while (FindNode){
if (!FindNode->left){
RootNode->Depth=FindNode->Depth;
RootNode->NodeKey=FindNode->NodeKey;
break;
}
FindNode=FindNode->left;
}
// 再次调用递归函数,将右子树的最小值节点删除
intResult=DelNode(&RootNode->right,FindNode->NodeKey);
// 重新计算此节点的最大深度值
RootNode->Depth=NodeDepth_2(RootNode);
}
}
else{
// 其中一个是空的,把指针指向非空的一个,然后删除找到的节点
if (RootNode->left) *TopRootNode=RootNode->left;
if (RootNode->right) *TopRootNode=RootNode->right;
// 高度发生了变化
intResult=2;
bolDelNode=true;
}
}

if (bolDelNode) delete RootNode;

return intResult;
}
else{
// 没找到
if (delNodeKey < RootNode->NodeKey){
// 新节点值小于当前节点值,往左子树遍历
if (RootNode->left) intResult=DelNode(&RootNode->left,delNodeKey);
}
else{
// 新节点值大于当前节点值,往右子树遍历
if (RootNode->right) intResult=DelNode(&RootNode->right,delNodeKey);
}
}

if (intResult==2){
// 如果当前节点或当前节点的某一个子节点深度发生变化

// 更新当前节点的深度值
RootNode->Depth=NodeDepth_2(RootNode);

// 分别获取左右两边子节点的深度
int LD=-1;
if (RootNode->left) LD=RootNode->left->Depth;
int RD=-1;
if (RootNode->right) RD=RootNode->right->Depth;

// 如果当前节点左右两边子树的深度差大于1,那么当前节点就是不平衡点
int D=LD-RD;
if (LD < RD) D=RD-LD;

if (D > 1){
if (LD > RD){
// 如果左子树比右子树深
PTreeNode NextNode=RootNode->left;
// 获取左子树下的左右两子节点的深度
int LLD=-1;
if (NextNode->left) LLD=NextNode->left->Depth;
int LRD=-1;
if (NextNode->right) LRD=NextNode->right->Depth;

if (LLD >= LRD){
// 如果左子节点深度大于或等于右子节点的深度,那么对不平衡点执行右旋操作
*TopRootNode=TurnRight(RootNode);
}
else{
// 如果左子节点深度小于右子节点的深度,那么先对不平衡点的左子树执行左旋,然后对不平衡点执行右旋操作
*TopRootNode=TurnLeftNodeLR(RootNode);
}
}
else{
// 如果右子树比左子树深
PTreeNode NextNode=RootNode->right;
// 获取右子树下的左右两子节点的深度
int LLD=-1;
if (NextNode->left) LLD=NextNode->left->Depth;
int LRD=-1;
if (NextNode->right) LRD=NextNode->right->Depth;

if (LLD <= LRD){
// 如果左子节点小于或等于右子节点的值,那么对不平衡点执行左旋操作
*TopRootNode=TurnLeft(RootNode);
}
else{
// 如果左子节点大于右子节点的值,那么先对不平衡点的右子树执行右旋,然后对不平衡点执行左旋操作
*TopRootNode=TurnRightNodeRL(RootNode);
}
}

} // end if (D > 1)
} // end if (intResult==2)

return intResult;
}

// 将整颗树的数据显示出来
typedef struct _NodeLink{
int FValue; // 父节点的值
int Depth; // 层次
int location; // 位置,1 左边;2 右边
_TreeNode* TreeNode; // 指向一个树的节点
_NodeLink* next; // 下一个结构 TNodeLink
}TNodeLink, *PNodeLink;

void PrintfTree(PTreeNode RootNode)
{
// 采用广度优先遍历

if (!RootNode) return;

printf("当前树结构\r\n");

PNodeLink lpNodeLink=new TNodeLink;
lpNodeLink->Depth=0;
lpNodeLink->next=0;
lpNodeLink->FValue=0;
lpNodeLink->TreeNode=RootNode;

int N=0;
while (lpNodeLink){
if (N != lpNodeLink->Depth){
N=lpNodeLink->Depth;
printf("\r\n");
}

char strLocation[32]={0};
if (lpNodeLink->location==1) sprintf(strLocation,"-Left");
if (lpNodeLink->location==2) sprintf(strLocation,"-Right");

printf("[%d%s,%d,%d] ",lpNodeLink->FValue,strLocation,lpNodeLink->TreeNode->NodeKey,lpNodeLink->TreeNode->Depth);

// 将树节点的左右子节点加入队列后面
if ( (lpNodeLink->TreeNode->left) || (lpNodeLink->TreeNode->right) ){

PNodeLink LeftNodeLink=0;
if (lpNodeLink->TreeNode->left){
LeftNodeLink=new TNodeLink;
LeftNodeLink->Depth=lpNodeLink->Depth + 1;
LeftNodeLink->next=0;
LeftNodeLink->FValue=lpNodeLink->TreeNode->NodeKey;
LeftNodeLink->location=1;
LeftNodeLink->TreeNode=lpNodeLink->TreeNode->left;
}

PNodeLink RightNodeLink=0;
if (lpNodeLink->TreeNode->right){
RightNodeLink=new TNodeLink;
RightNodeLink->Depth=lpNodeLink->Depth + 1;
RightNodeLink->next=0;
RightNodeLink->FValue=lpNodeLink->TreeNode->NodeKey;
RightNodeLink->location=2;
RightNodeLink->TreeNode=lpNodeLink->TreeNode->right;
}

if (LeftNodeLink){
LeftNodeLink->next=RightNodeLink;
}
else{
LeftNodeLink=RightNodeLink;
}

if (LeftNodeLink){
PNodeLink NextNodeLink=lpNodeLink;
while (NextNodeLink){
if (!NextNodeLink->next){
NextNodeLink->next=LeftNodeLink;
break;
}
NextNodeLink=NextNodeLink->next;
}
}
}

PNodeLink DelNodeLink=lpNodeLink;
lpNodeLink=lpNodeLink->next;
/*
之所以注释掉下面这句话,是因为Windows系统,频繁的申请和释放小内存块,会造成内存泄漏,
从而导致程序崩溃,在实际开发中,应考虑内存池的方法
*/
// delete DelNodeLink;
}


printf("\r\n========================================\r\n");
}

int main()
{
// 根节点
PTreeNode RootNode=0;

printf("\r\n1 添加新数据请输入正数;\r\n2 删除数据请输入负数(例如,要删除数据2,则输入-2);\r\n3 输入数值0为退出\r\n");
printf("\r\n树结构说明;\r\n[a-Left,b,c]: a当前节点的父节点键值;Left或Right,当前节点在父节点的左边还是右边;b代表当前节点的键值;c当前节点为的最大深度值\r\n");
while(true){
printf("\r\ninput number: ");

int inputvalue=0;
cin>>inputvalue;
if (inputvalue == 0) break; // 如果输入值是0,退出程序

if (inputvalue < 0){
inputvalue=abs(inputvalue);
if (RootNode) DelNode(&RootNode,inputvalue);
}
else{
PTreeNode newNode=new TTreeNode;
newNode->left=0;
newNode->right=0;
newNode->NodeKey=inputvalue;
newNode->Depth=0;
if (RootNode){
AddNode(&RootNode,newNode);
}
else{
RootNode=newNode;
}
}

// 将树打印出来
if (TreeBalanced(RootNode)) printf("\r\n是平衡二叉树,");
PrintfTree(RootNode);
} // end while (true)

return 0;
}


编译后运行,输入的数值分别是:3, 2, 1, 4, 5, 6, 7, 10, 9, 8,运行后输出的数据:



最底部红色的是最终运行结果,解释如下:

[4-Left,2,1] 表示父节点是4,在父节点的左边,当前节点值是2,当前节点最大深度是1
[4-Right,7,2] 表示父节点是4,在父节点的右边,当前节点值是7,当前节点最大深度是2

以此类推

输入负数,代表删除,输入-4,就相当于删除顶点,得到的结果为:

留言

有啥想说的就说吧,有啥想问的就问吧
Good good study, day day up!

名称

Email

内容

预览(只读), 点击返回编辑.

 
最新文章
 
留言
版权所有 © 2020 mypcrun.com.
桂ICP备19002156号桂公网安备 45070202000667号
这回把网站设计得那么漂亮,这下子不会被人笑了吧。