分布式 Markdown regex Minjs 建造师报考条件 vue数据绑定 管理后台框架 华为路由器ipv6配置 idea整理代码格式 cad怎么重复上一次命令 solr索引 oracle查询数据库 二分查找python python3教程 python正则匹配 python正则匹配数字 python打开文件夹 java新特性 java当前时间 java的输入 java集合类型 java字符比较 asp建站系统 球中的小鬼 python输入数字 js延迟加载的方式 魔兽改图工具 iar下载 脚本编程 苹果内存怎么看 数据库密码忘了怎么办 大话5g 桌面cpu性能天梯图 python求平均值 mapinfo下载 优酷网打不开 mysql数据备份 ttf字体怎么安装 pr视频旋转 php获取当前域名
当前位置: 首页 > 学习教程  > 编程语言

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

2020/11/24 10:49:24 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

平衡二叉树(C语言简单实现) 本文参考自《大话数据结构》 平衡二叉树是一种二叉排序树,其中每一个结点的左子树和右子树的高度差至多等于1 。 将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor)。 平衡二叉树首先…

平衡二叉树(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;

右旋

/* 对以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指向新的根结点
}

左旋

/* 对以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指向新的根结点
}

左平衡旋转处理

#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;
                    L->bf = LH;
                    break;
            }
		Lr->bf = EH;
		L_Rotate(&(*T)->lchild);	//对T的左子树作左旋平衡处理
		R_Rotate(T);	//对T作右旋平衡处理
	}
}

主函数

/* 若在平衡的二叉排序树T中不存在和e有相同关键字的结点,则插入一个 */
/* 数据元素为e的新结点并返回1,否则返回0。若因插入而使二叉排序树失去平衡,则作平衡旋转处理,布尔变量taller反映T长高与否 */
Status InsertAVL(BiTree *T, int e, Status *taller){
	if(!*T){	//插入新结点,树“长高”,置taller为TRUE
		*T = (BiTree)malloc(sizeof(BiTNode));
		(*T)->data = e;
		(*T)->lchild = (*T)->rchild = NULL;
		(*T)->bf = EH;
		*taller = TRUE;
	}else{
		if(e == (*T)->data){	//树中已存在和e有相同关键字的结点则不再插入
			*taller = FALSE;
			return FALSE;
		}
		if(e < (*T)->data){	//应继续在T的左子树中进行搜索
			if(!InsertAVL(&(*T)->lchild, e, taller))	//未插入
				return FALSE;
			if(taller){	//已插入到T的左子树中且左子树“长高”
				switch((*T)->bf){	//检查T的平衡度
					case LH:	//原本左子树比右子树高,需要作左平衡处理
						LeftBalance(T);	
						*taller = FALSE;
						break;
					case EH:	//原本左右子树等高,现因左子树增高而树增高
						(*T)->bf = LH;
						*taller = TRUE;
						break;
					case RH:	//原本右子树比左子树高,现在左右子树等高
						(*T)->bf = EH;
						*taller = FALSE;
						break;
				}
			}			
		}else{	//继续在T的右子树中进行搜索
			if(!InsertAVL(&(*T)->rchild, e, taller))	//未插入
				return FALSE;
			if(*taller){	//已插入到T的右子树且右子树“长高”
				switch((*T)->bf){	//检查T的平衡度
					case LH:	//原本左子树比右子树高
						(*T)->bf = EH;
						*taller = FALSE;
						break;
					case EH:	//原本左右子树等高,现因右子树增高而树增高
						(*T)->bf = RH;
						*taller = TRUE;
						break;
					case RH:	//原本右子树比左子树高,需要作右平衡处理
						RightBalance(T);
						*taller = FALSE;
						break;
				}
			}
		}		
	}
	return TRUE;
}

调用构建平衡二叉树代码:

int i;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
BiTree T = NULL;
Status taller;
for(i=0;i<10;i++)
	InsertAVL(&T, a[i], &taller);

如果需要查找的集合本身没有顺序,在频繁查找的同时也需要经常地插入和删除操作,显然我们需要构建一棵二叉排序树,但是不平衡的二叉排序树,查找效率是非常低的,因此我们需要在构建时,就让这棵二叉排序树是平衡二叉树,此时我们的查找时间复杂度就为O(logn),而插入和删除也为O(logn)。这是比较理想的一种动态查找算法。

示例

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef int Status;
#define LH +1
#define EH 0
#define RH -1

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

/* 对以p为根的二叉排序树作右旋处理,
	处理之后p指向新的树根节点,即旋转处理之前的左子树的根节点 */
void R_Rotate(BiTree *p){
	BiTree L;
	L = (*p)->lchild;	//L指向P的左子树根节点 
	(*p)->lchild = L->rchild;
	L->rchild = (*p);
	*p = L;	//P指向新的根节点 
}

/* 左旋 */
void L_Rotate(BiTree *p){
	BiTree R;
	R = (*p)->rchild;	//指向p的右子树根结点
	(*p)->rchild = R->lchild;
	R->lchild = (*p);
	*p = R; 
}

/* 左平衡处理 */
void LeftBalance(BiTree *T){
	BiTree L, Lr;
	L = (*T)->lchild;	//L指向T的左子树根结点,也就是新插入结点的父节点 
	switch(L->bf){	//检查T的左子树的平衡度,并作相应平衡处理
		case LH:	//新结点插入在T的左孩子的左子树上,要作单右旋处理,单右旋的结果就是,平衡度变为0,0,0
			(*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;
                    L->bf = LH;
                    break;
            }
		Lr->bf = EH;	//平衡因子设为0 
		L_Rotate(&(*T)->lchild);	//对T的左子树作左旋平衡处理,这步是为了平衡因子bf的符号统一 
		R_Rotate(T);	//对T作右旋平衡处理
	}
}

/* 右平衡处理 */
void RightBalance(BiTree *T){
	BiTree R, Rl;
	R = (*T)->rchild;	//L指向T的左子树根结点
	switch(R->bf){	//检查T的左子树的平衡度,并作相应平衡处理
		case RH:		//新结点插入在T的左孩子的右子树上,要作左旋处理
			(*T)->bf = R->bf = EH;
			L_Rotate(T);
			break;
		case LH:	//新结点插入在T的左孩子的左子树上,要作单右旋处理
			Rl = R->lchild;	//Lr指向T的左孩子的右子树根
			switch(Rl->bf){	//修改T及其左孩子的平衡因子
                case LH:
                    (*T)->bf = RH;
                    R->bf = EH;
                    break;
                case EH:
                    (*T)->bf = R->bf = EH;
                    break;
                case RH:
                    (*T)->bf = EH;
                    R->bf = LH;
                    break;
            }
		Rl->bf = EH;	//平衡因子设为0 
		R_Rotate(&(*T)->rchild);	//对T的右子树作右旋平衡处理
		L_Rotate(T);	//对T作左旋平衡处理
	}
}

/* 若在平衡的二叉排序树T中不存在和e有相同关键字的结点,则插入一个 */
/* 数据元素为e的新结点并返回1,否则返回0。若因插入而使二叉排序树失去平衡,则作平衡旋转处理,布尔变量taller反映T长高与否 */
Status InsertAVL(BiTree *T, int e, Status *taller){
	if(!*T){	//插入新结点,树"长高",置taller为TRUE
		*T = (BiTree)malloc(sizeof(BiTNode));
		(*T)->data = e;
		(*T)->lchild = (*T)->rchild = NULL;	//新结点左右孩子为空 
		(*T)->bf = EH;	//新结点平衡因子为0 
		*taller = TRUE;	//插入结点后,树长高 
	}else{
		if(e == (*T)->data){	//树中已存在和e有相同关键字的结点则不再插入
			*taller = FALSE;	//有相同的结点,所以没有插入,树没有长高 
			return FALSE;
		}
		if(e < (*T)->data){	//应继续在T的左子树中进行搜索
			if(!InsertAVL(&(*T)->lchild, e, taller))	//未插入结点 
				return FALSE;
			//已插入到T的左子树中且左子树"长高",如果已经插入了结点,但是树没有长高(即在子树中已经调整了平衡度 
			if(taller){	
				switch((*T)->bf){	//检查T的平衡度
					case LH:	
					//原本左子树比右子树高,需要作左平衡处理,那么插入一个结点在左子树里,
					//左子树高度变为2,需要调整 
						LeftBalance(T);		//左平衡调整 
						*taller = FALSE;	//调整后树没有长高 
						break;
					case EH:	//原本左右子树等高,现因左子树增高而树增高
						(*T)->bf = LH;
						*taller = TRUE;	//左子树多了一个孩子,肯定长高了,但是平衡度为1,是最小不平衡树,无需调整 
						break;
					case RH:	//原本右子树比左子树高,现在左右子树等高
						(*T)->bf = EH;
						*taller = FALSE; 
						break;
				}
			}			
		}else{	//继续在T的右子树中进行搜索
			if(!InsertAVL(&(*T)->rchild, e, taller))	//未插入
				return FALSE;
			if(*taller){	//已插入到T的右子树且右子树"长高"
				switch((*T)->bf){	//检查T的平衡度
					case LH:	//原本左子树比右子树高
						(*T)->bf = EH;
						*taller = FALSE;
						break;
					case EH:	//原本左右子树等高,现因右子树增高而树增高
						(*T)->bf = RH;
						*taller = TRUE;
						break;
					case RH:	//原本右子树比左子树高,需要作右平衡处理
						RightBalance(T);
						*taller = FALSE;
						break;
				}
			}
		}		
	}
	return TRUE;
}

int main(){
	int i;
	int a[10] = {1,2,3,4,5,6,7,10,9,8};
	BiTree T = NULL;	//指向BiTNode的指向置空 
	Status taller;	//树是否长高标志 
	for(i=0;i<10;i++)
		InsertAVL(&T, a[i], &taller);	//插入结点到AVL树 
	return 0;
} 

结果

AVL实验结果

最后,AVL树真的好难啊,理解起来不难,但是要自己想出和写出代码真的不容易,路漫漫其修远兮,吾将上下而求索,加油!


本文链接: http://www.dtmao.cc/news_show_400358.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?