当前位置:   article > 正文

平衡二叉树(C语言简单实现)_画出将13,21,24,16,9,21,12,55,7, 10依次插入到初始为空的平衡二叉树中的结果

画出将13,21,24,16,9,21,12,55,7, 10依次插入到初始为空的平衡二叉树中的结果。

平衡二叉树(C语言简单实现)

本文参考自《大话数据结构》

平衡二叉树是一种二叉排序树,其中每一个结点的左子树和右子树的高度差至多等于1

将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor)。

平衡二叉树首先必须是一棵二叉排序树,同时任一结点的左子树和右子树的高度差最多等于1

距离插入结点最近的,且平衡因子的绝对值大于1的结点为根的子树,我们称为最小不平衡子树

平衡二叉树实现原理

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中,每当插入一个结点时,先检查是否因插入而破坏了树的平衡性,若是,则找出最小不平衡子树。在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树。

当最小不平衡子树根结点的平衡银子BF是大于1时,就右旋;小于-1时就左旋

第一种:也是最简单的,图1结点3平衡因子变成了2,此时需要调整平衡度,右旋之后平衡度降为0
(AVL原理图1
AVL原理图2

这是第二种情况:插入9的时候,就变成了图11那样子,这时候发现结点7的平衡度为-2,此时需要调整平衡度,正常来说,平衡度-2,是右子树高,要进行左旋,但是左旋之后,会结点9会变成结点10的右孩子,不符合二叉排序树的大小关系,这种情况需要先进行平衡度符号调整:即结点7的平衡度为-2,而结点10的平衡度为+1,此时需将结点7子树的符号调整成的,所以这里先对结点10结点9进行右旋,然后再进行左旋,得到的树就不会违反二叉排序树的规则(图13-16同理)。
AVL原理图3
AVL原理图4

平衡二叉树实现算法

结构定义

/* 二叉树的二叉链表结点结构定义 */
typedef struct BiTNode{
   
	int data;
	int bf;	//平衡因子
	struct BiTNode *lchild, *rchild;	//左右孩子
}BiTNode, *BiTree;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

右旋

/* 对以p为根的二叉排序树作右旋处理,处理之后p指向新的树根结点,即旋转处理之前的左子树的根结点 */
void R_Rotate(BiTree *p){
   
	BiTree L;
	L = (*p)->lchild;	//L指向p的左子树根结点
	(*p)->lchild=L->rchild;	//L的右子树挂接为p的左子树
	L->rchilld = (*p);
	*p = L;	//p指向新的根结点
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

左旋

/* 对以p为根的二叉排序树作左旋处理,处理之后p指向新的树根结点,即旋转处理之前的右子树的根结点 */
void L_Rotate(BiTree *p){
   
	BiTree R;
	R = (*p)->rchild;	//R指向p的右子树根结点
	(*p)->rchild = R->lchild;	//R的左子树挂接为p的右子树
	R->lchild = (*p);
	*p = R;	//p指向新的根结点
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

左平衡旋转处理

#define LH +1	//左高
#define EH 0	//等高
#define RH -1	//右高
/* 对以指针T所指结点为根的二叉树作左平衡旋转处理 */
/* 本算法结束时,指针T指向新的根结点 */
void LeftBalance(BiTree *T){
   
	BiTree L, Lr;
	L = (*T)->lchild;	//L指向T的左子树根结点
	switch(L->bf){
   	//检查T的左子树的平衡度,并作相应平衡处理
		case LH:	//新结点插入在T的左孩子的左子树上,要作单右旋处理
			(*T)->bf = L->bf = EH;
			R_Rotate(T);
			break;
		case RH:		//新结点插入在T的左孩子的右子树上,要作双旋处理
			Lr = L->rchild;	//Lr指向T的左孩子的右子树根
			switch(Lr->bf){
   	//修改T及其左孩子的平衡因子
                case LH:
                    (*T)->bf = RH;
                    L->bf = EH;
                    break;
                case EH:
                    (*T)->bf = L->bf = EH;
                    break;
                case RH:
                    (*T)->bf = EH
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号