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

#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;
}