欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

全网最强 最仔细 AVL平衡二叉树代码解析 新人访问少，但绝对是干货，绝对值得看

程序员文章站 2022-03-03 09:41:41
...

代码转自
c语言中文网
http://c.biancheng.net/view/3432.html
旋转操作 学习自
https://www.cnblogs.com/cherryljr/p/6669489.html
但注释与解析绝大部分为原创 ，非常详细深刻，
每一行代码都有解释
具体分析过程我另外一个博客 加了 分析过程的手写笔迹

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

//分别定义平衡因子数
#define LH +1
#define EH 0
#define RH -1
typedef int ElemType;
//typedef enum { false, true } bool;

//定义二叉排序树
typedef struct BSTNode {
ElemType data;
int bf;//balance flag
struct BSTNode *lchild, *rchild;
}*BSTree, BSTNode;

//对以 p 为根结点的二叉树做右旋处理，令 p 指针指向新的树根结点
//这里需要的 结点p是旋转中心节点
//根据左旋右旋法则，
// 右右单旋转时，这里的 旋转中心结点p 为最小不平衡树的 孩子结点
// 右左双旋转时候，旋转中心结点p 为最小不平衡树的 孙子结点
void R_Rotate(BSTree* p)
{
//借助文章中的图 5 所示加以理解，其中结点 A 为 p 指针指向的根结点
BSTree lc = (*p)->lchild;
//这里lc->rchild 如果不为NULL,则应该挪到 (*p)->lchild;
//如果lc->rchild 如果为NULL,则挪到 (*p)->lchild;也不影响，因为 (*p)的lchild;转换过程中被转换掉变为NULL了，则再加一次NULL也不影响
//所以无论lc->rchild 是否为 NULL,都应该挪到 (*p)->lchild;
(*p)->lchild = lc->rchild;
lc->rchild = *p;
p = lc;
}
//对以 p 为根结点的二叉树做左旋处理，令 p 指针指向新的树根结点
//这里需要的 结点p是旋转中心节点
//根据左旋右旋法则，
// 左左单旋转时，这里的 旋转中心结点p 为最小不平衡树的 孩子结点
// 左右双旋转时候，旋转中心结点p 为最小不平衡树的 孙子结点
void L_Rotate(BSTree p)
{
//借助文章中的图 6 所示加以理解，其中结点 A 为 p 指针指向的根结点
BSTree rc = (*p)->rchild;
//这里rc->lchild 如果不为NULL,则应该挪到 (*p)->rchild;
//如果rc->lchild 如果为NULL,则挪到 (*p)->rchild;也不影响，因为 (*p)的rchild;转换过程中被转换掉变为NULL了，则再加一次NULL也不影响
//所以无论rc->lchild 是否为 NULL,都应该挪到 (*p)->rchild;
(*p)->rchild = rc->lchild;
rc->lchild = *p;
*p = rc;
}

//对以指针 T 所指向结点为根结点的二叉树作左子树的平衡处理，令指针 T 指向新的根结点
// 需要这这里平很处理的结点 必定是已经不平衡了得结点
//也就是必须是平衡因子为-2 或者 2 的结点，又因为左旋，所以这里需要的 参数T的平衡因子必须为2 ，才可以调用这个左旋函数
//这里是对T的左子树进行不平衡的旋转处理
//分为左左单旋转和左右双旋转
void LeftBalance(BSTree* T)
{
BSTree lc, rd;
lc = (*T)->lchild;
//查看以 T 的左子树为根结点的子树，失去平衡的原因，
//如果 bf 值为 1 ，则说明新节点添加在左子树为根结点的左子树中，需要对其进行左左单旋转旋处理；
//反之，如果 bf 值为 -1，说明添加在以左子树为根结点的右子树中，需要进行双向先左旋后右旋（左右双旋转）的处理
switch (lc->bf)
{
//bf 值为 1 ，则新节点说明添加在左子树为根结点的左子树中，需要对其进行左左单旋转旋处理；
case LH:
//先调整好这棵树转换 完成后 应该的有的 平衡因子
(*T)->bf = lc->bf = EH;
//再直接旋转，不必考虑平衡因子，因为上面已经提前一步调整好了平衡因子
R_Rotate(T);
break;
//bf 值为 -1，说明添加在以左子树为根结点的右子树中，需要进行双向先左旋后右旋（左右双旋转）的处理
case RH:
rd = lc->rchild;
//先调整好这棵树转换 完成后 应该的有的 平衡因子
switch (rd->bf)
{
case LH:
(*T)->bf = RH;
lc->bf = EH;
break;
case EH:
(*T)->bf = lc->bf = EH;
break;
case RH:
(*T)->bf = EH;
lc->bf = LH;
break;
}
rd->bf = EH;
//再直接旋转，不必考虑平衡因子，因为上面已经提前一步调整好了平衡因子
//先左旋 T的左子树
L_Rotate(&(*T)->lchild);
//再右旋T
R_Rotate(T);
break;
}
}

//右子树的平衡处理同左子树的平衡处理完全类似
// 需要这这里平很处理的结点 必定是已经不平衡了得结点
//对以指针 T 所指向结点为根结点的二叉树作右子树的平衡处理，令指针 T 指向新的根结点
// 需要这这里平很处理的结点 必定是已经不平衡了得结点
//也就是必须是平衡因子为-2 或者 2 的结点，又因为左旋，所以这里需要的 参数T的平衡因子必须为-2 ，才可以调用这个右旋函数
//这里是对T的右子树进行不平衡的旋转处理
//分为右右单旋转和右左双旋转
void RightBalance(BSTree* T)
{
BSTree lc, rd;
lc = (*T)->rchild;
//每一个都会有 rd->bf = EH; 这一步，所以补充在最后

//查看以 T 的右子树为根结点的子树，失去平衡的原因，
//如果 bf 值为 -1 ，则说明新节点添加在右子树为根结点的右子树中，需要对其进行右右单旋转旋处理；
//反之，如果 bf 值为 -1，说明添加在以右子树为根结点的左子树中，需要进行双向先右旋后左旋（右左双旋转）的处理
switch (lc->bf)
{
//bf 值为 1 ，则新节点说明添加在右子树为根结点的右子树中，需要对其进行右右单旋转旋处理；
case RH:
	//先调整好这棵树转换 完成后 应该的有的 平衡因子
	(*T)->bf = lc->bf = EH;
	//再直接旋转，不必考虑平衡因子，因为上面已经提前一步调整好了平衡因子
	L_Rotate(T);
	break;
//bf 值为 1，说明添加在以右子树为根结点的左子树中，需要进行双向先右旋后左旋（右左双旋转）的处理
case LH:
	rd = lc->lchild;
	//先调整好这棵树转换 完成后 应该的有的 平衡因子
	switch (rd->bf)
	{
		//(*T)->rchild;和 (*T)->rchild->lchild; 分别为 1 1
	case LH:
		(*T)->bf = EH;
		lc->bf = RH;
		break;
	case EH:
		(*T)->bf = lc->bf = EH;
		break;
		//1  -1
	case RH:
		(*T)->bf = EH;
		lc->bf = LH;
		//	(*T)->bf = LH;
		//  lc->bf = EH;
		break;
	}
	//每一个都会有这一步，所以补充在最后
	rd->bf = EH;  
	//再直接旋转，不必考虑平衡因子，因为上面已经提前一步调整好了平衡因子
	//先右旋 T的左子树
	R_Rotate(&(*T)->rchild);
	//再左旋T
	L_Rotate(T);
	break;
}

}

int InsertAVL(BSTree* T, ElemType e, bool* taller)
{
//如果本身为空树，则直接添加 e 为根结点
if ((*T) == NULL)
{
(*T) = (BSTree)malloc(sizeof(BSTNode));
(*T)->bf = EH;
(*T)->data = e;
(*T)->lchild = NULL;
(*T)->rchild = NULL;
*taller = true;
}
//如果二叉排序树中已经存在 e ，则不做任何处理
else if (e == (*T)->data)
{
*taller = false;
return 0;
}
//如果 e 小于结点 T 的数据域，则插入到 T 的左子树中
else if (e < (*T)->data)
{
//如果插入过程，不会影响树本身的平衡，则直接结束，返回上一层递归
//未能成功插入
//如果成功插入，则通过 taller的值去 判断 是否需要 调整结点平衡因子 和 旋转操作
if (!InsertAVL(&(*T)->lchild, e, taller))
return 0;
//判断插入过程是否会导致整棵树的深度 +1
if (*taller)
{
//判断根结点 T 的平衡因子是多少，
//由于是在其左子树添加新结点的过程中导致失去平衡，
//所以当 T 结点的平衡因子本身为 1 时，需要进行左子树的平衡处理，否则更新树中各结点的平衡因子数
//某个结点p1 的平衡因子为 LH，EH，RH 时候，在其左子树 插入 新的节点p2后，
//p2的平衡因子必定为EH，而p1的平衡因子就会变化，变化趋势为（因为p1的左子树被插入，所以p1的平衡因子
//会增加1）
//LH-> 2此时不平衡，需要调整
//EH-> LH 此时平衡，不需要调整
//RH-> EH 此时平衡，不需要调整
switch ((*T)->bf)
{
case LH:
//每次退到有节点的平衡因子即将 变为-1，0，1之外的时候，进行变换。也就是遇到平衡因子为-2或者2的时候，
//说明遇到了 最小不平衡树的跟结点，然后拿着根节点去变换
//又因为这里 是左子树插入，并且原先节点的平衡因子为1（LH），就是此节点左边比右边深度 深1，
//那么在此节点左子数插入后左边比右边深2，此时此节点的 平衡因子变为2，
//说明这是一颗最小不平衡树的 根节点，又因为是 左子数插入了结点，因此需要进行左子树的 变换
//这里变换时需要 输入的结点 必定是 最小不平衡树的根节点，
//也就是T的平衡因子 必须为-2 或者 2.又因为左旋，则需要平衡因子为2的结点
LeftBalance(T);
//最小不平衡树调整完成后，不会影响 再往上的节点的平衡因子，因此 taller变为false，
//后序退出递归的时候 直接退出，不再调整平衡因子
//而左旋或者右旋过程中，左旋右旋函数内 会调整好节点的平衡因子。
*taller = false;
break;
case EH:
(*T)->bf = LH;
//因为已知这是在左子树插入，那么原先的为0（EH）的父节点 会变为1（LH）
//又因为 平衡因子为1（LH）的结点 不是 最小不平衡树的 根节点，所以只需要调整不平衡因子后 往上回退。
//只有初次遇到 节点的平衡因子为-2或者2的时候，说明这是 最小不平衡树 根节点，
//拿着这个根节点去调整（左旋，右旋，左右旋，右左旋）
//因为这里需要进一步往上调整，所以 *taller = true;表明上一步需要继续调整
*taller = true;
break;
case RH:
(*T)->bf = EH;
//因为已知这是在左子树插入，那么原先的为-1（RH）的父节点 会变为0（EH）
//又因为 平衡因子为0（EH）的结点 不是 最小不平衡树的 根节点，所以只需要调整不平衡因子后 往上回退。
//只有初次遇到 节点的平衡因子为-2或者2的时候，说明这是 最小不平衡树 根节点，
//拿着这个根节点去调整（左旋，右旋，左右旋，右左旋）
//又因为这里 是左子树插入，并且原先节点的平衡因子为-1（RH），就是此节点右边比左边深度 深1，
//那么在此节点左子数插入后刚好左右平衡，则不需要再往上调整平衡因子了，
//此时 *taller = false;，也就是不再往上继续调整。到此处就平衡了。
//同时，此节点平衡因子调为0
*taller = false;
break;
}
}
}
//同样，当 e>T->data 时，需要插入到以 T 为根结点的树的右子树中，同样需要做和以上同样的操作
else
{
if (!InsertAVL(&(*T)->rchild, e, taller))
return 0;
//taller 是 判断 是否继续向上一层进行调整。
//也就是 如果 下面的这些调整 就能够 使得 树 平衡 ，而且 各个平衡因子也都 已经调整 完毕，
// 并且 再上之前的 下面节点的 平衡因子的 调整 不会影响 当前以及再往上 节点的数树的平衡以及 平衡因子
//那么就将taller设为 false，表明 不再需要向上进行调整，直接返回上一层即可。
if (*taller)
{
switch ((*T)->bf)
{
case LH:
(*T)->bf = EH;
//因为已知这是在右子树插入，那么原先的为1（LH）的父节点 会变为0（EH）
//又因为 平衡因子为0（EH）的结点 不是 最小不平衡树的 根节点，所以只需要调整不平衡因子后 往上回退。
//只有初次遇到 节点的平衡因子为-2或者2的时候，说明这是 最小不平衡树 根节点，
//拿着这个根节点去调整（左旋，右旋，左右旋，右左旋）
//又因为这里 是右子树插入，并且原先节点的平衡因子为1（LH），就是此节点左边比右边深度 深1，
//那么在此节点右子数插入后刚好左右平衡，则不需要再往上调整平衡因子了，
//此时 *taller = false;，也就是不再往上继续调整。到此处就平衡了。
//同时，此节点平衡因子调为0
*taller = false;
break;
case EH:
(*T)->bf = RH;
//因为已知这是在右子树插入，那么原先的为0（EH）的父节点 会变为-1（RH）
//又因为 平衡因子为-1（RH）的结点 不是 最小不平衡树的 根节点，所以只需要调整不平衡因子后 往上回退。
//只有初次遇到 节点的平衡因子为-2或者2的时候，说明这是 最小不平衡树 根节点，
//拿着这个根节点去调整（左旋，右旋，左右旋，右左旋）
//因为这里需要进一步往上调整，所以 *taller = true;表明上一步需要继续调整
*taller = true;
break;
case RH:
//每次退到有节点的平衡因子即将 变为-1，0，1之外的时候，进行变换。也就是遇到平衡因子为-2或者2的时候，
//说明遇到了 最小不平衡树的根结点，然后拿着根节点去变换
//又因为这里 是右子树插入，并且原先节点的平衡因子为-1（RH），就是此节点右边比左边深度 深1，
//那么在此节点右子数插入后右边比左边深2，此时此节点的 平衡因子变为-2，
//说明这是一颗最小不平衡树的 根节点，又因为是 右子数插入了结点，因此需要进行右子树的 变换
//这里变换时需要 输入的结点 必定是 最小不平衡树的根节点，
//也就是T的平衡因子 必须为-2 或者 2.又因为右旋，则需要平衡因子为-2的结点
RightBalance(T);
//最小不平衡树调整完成后，不会影响 再往上的节点的平衡因子，因此 taller变为false，
//后序退出递归的时候 直接退出，不再调整平衡因子
//而左旋或者右旋过程中，左旋右旋函数内 会调整好节点的平衡因子。

			*taller = false;
			break;
		}
	}
}
return 1;

}

//判断现有平衡二叉树中是否已经具有数据域为 e 的结点
bool FindNode(BSTree root, ElemType e, BSTree* pos)
{
BSTree pt = root;
(*pos) = NULL;
while (pt)
{
if (pt->data == e)
{
//找到节点，pos指向该节点并返回true
(*pos) = pt;
return true;
}
else if (pt->data>e)
{
pt = pt->lchild;
}
else
pt = pt->rchild;
}
return false;
}

//中序遍历平衡二叉树
void InorderTra(BSTree root)
{
if (root->lchild)
InorderTra(root->lchild);
printf("%d ", root->data);
if (root->rchild)
InorderTra(root->rchild);
}

int main()
{
int i, nArr[] = { 1,23,45,34,98,9,4,35,23 };
BSTree root = NULL, pos;
bool taller;
//用 nArr查找表构建平衡二叉树（不断插入数据的过程）
for (i = 0; i<9; i++)
{
InsertAVL(&root, nArr[i], &taller);
}
//中序遍历输出
InorderTra(root);
//判断平衡二叉树中是否含有数据域为 103 的数据
if (FindNode(root, 103, &pos))
printf("\n%d\n", pos->data);
else
printf("\nNot find this Node\n");
return 0;
}

相关标签： 二叉树 二叉树

上一篇： [转载]jquery-validation 使用

下一篇： java简介以及了解java（三一）

推荐阅读