C语言之平衡二叉树详解

目录
  • 什么是平衡二叉树
  • 平衡二叉树的基本特点
  • 为什么会出现平衡二叉树
  • 二叉树四种不平衡的情况
  • C语言实现平衡二叉树

什么是平衡二叉树

平衡二叉树是具有平衡属性的有序二叉树,所谓的平衡即当前树的左右子树高度差的绝对值不超过1。因为平衡二叉树是由苏联数学家Adelson-Velskii和Landis提出,所以又称为AVL树。

平衡二叉树的基本特点

  • 是特殊的有序二叉树
  • 左右子树高度差的绝对值不超过1
  • 左右子树仍然是平衡二叉树

为什么会出现平衡二叉树

在学习平衡二叉树之前必定已经学过有序二叉树,有序二叉树的结构特点就是将数据有序的排好,查找起来快,但是有序二叉树有一个缺点,就是当节点呈现的状态是一边倒,那查找数据的时候就没有发挥出二叉树折半查找的优势了,这个时候是线性的查找(类似于链表的查找)。平衡二叉树就是解决有序二叉树一边倒的问题。如果有序二叉树是平衡的,那么查找数据就很快。时间复杂度为O ( l o g n ) O(logn)O(logn)。这样就充分发挥了二叉树的优势。

二叉树四种不平衡的情况

当树的左右子树高度差的绝对值大于1的时候就需要进行旋转操作,将不平衡的树变成平衡的树。以下是会出现的四种不平衡的情况。

  • 左左不平衡
  • 右右不平衡
  • 左右不平衡
  • 右左不平衡

左左不平衡旋转成平衡状态:

右右不平衡旋转成平衡状态:

左右不平衡旋转成平衡状态:

右左不平衡旋转成平衡状态:

上面是图解这四种不平衡状态旋转成平衡状态的情况。

C语言实现平衡二叉树

平衡二叉树的结构体描述:

#define Ty int  //以整型数据为例
typedef struct Node
{
	Ty data;             //数据
	int height;          //高度
	struct Node* LChild; //左子树
	struct Node* RChild; //右子树
}Node,AVLTree;

初始化函数:

AVLTree* creatAVLTree(Ty data)
{
    AVLTree* tree = (AVLTree*)malloc(sizeof(AVLTree));
    assert(tree);
    tree->data = data;
    tree->height = 0;
    tree->LChild = NULL;
    tree->RChild = NULL;
    return tree;
}

辅助宏函数:

//辅助函数
#define HEIGHT(x) ((x==NULL)?(-1):(x->height))
#define MAX(a,b)  ((a>b)?(a):(b))
//获取树的新高度
#define GET_NEW_HEIGHT(x) (MAX(HEIGHT(x->LChild),HEIGHT(x->RChild)) + 1)

使用宏函数的好处是运行过程中不需要进行函数压栈的操作,效率快一点。

前序遍历平衡二叉树:

//前序打印
void show_pre(AVLTree* root)
{
	if(root==NULL)
		return;
	printf("data:%d\theight:%d\n",root->data,root->height);
	show_pre(root->LChild);
	show_pre(root->RChild);
}

使用前序遍历能更好地看出节点的高度,更方便还原平衡二叉树。

四种不平衡状态旋转的算法实现:

算法核心思想:找到新根的位置,然后进行对应的调整,最后返回新根的地址,这样就实现了旋转的操作,因为旋转后节点的高度改变了,所以在返回之前先调整一下节点的高度。

例如:左左不平衡进行旋转操作

因为是左左不平衡,所以新根的位置是当前根的左子树,那就使用一个指针(newRoot)去接收当前根的左子树,然后使劲将当前根拉下来,让新根代替当前根的位置,那就必须将当前根的LChild指向newRoot的右子树(因为newRoot不一定是空的所以不能直接让curRoot→LChild指向空)。最后就是将newRoot→RChild指向curRoot这样就把位置调整好了。在返回newRoot之前把curRoot和newRoot的高度调整一下。保持树的准确性。

其他的不平衡情况也是类似的操作。

//出现不平衡的情况
//左左不平衡
Node *LL_Rotation(Node *curRoot)
{
	Node *newRoot = curRoot->LChild;
	curRoot->LChild = newRoot->RChild;
	newRoot->RChild = curRoot;

	curRoot->height = GET_NEW_HEIGHT(curRoot);
	newRoot->height = GET_NEW_HEIGHT(newRoot);
	return newRoot;
}

//右右不平衡
Node *RR_Rotation(Node *curRoot)
{
	Node *newRoot = curRoot->RChild;
	curRoot->RChild = newRoot->LChild;
	newRoot->LChild = curRoot;

	curRoot->height = GET_NEW_HEIGHT(curRoot);
	newRoot->height = GET_NEW_HEIGHT(newRoot);
	return newRoot;
}
//左右不平衡
Node *LR_Rotation(Node *curRoot)
{
	curRoot->LChild = RR_Rotation(curRoot->LChild);
	return LL_Rotation(curRoot);
}
//右左不平衡
Node *RL_Rotation(Node *curRoot)
{
	curRoot->RChild = LL_Rotation(curRoot->RChild);
	return RR_Rotation(curRoot);
}

平衡二叉树的插入操作:

插入操作需要考虑到四种情况:

  • 当前节点是空的
  • 要插入进来的数据比当前节点的数据小
  • 要插入进来的数据比当前节点的数据大
  • 要插入进来的数据和当前节点的数据一样大

情况一的解决方案:直接申请一个节点内存。

情况二的解决方案:递归往左边跑,然后跑到对应的位置就申请内存,插入完成后判断需不需要调整。

情况三的解决方案:递归往右边跑,然后跑到对应的位置就申请内存,插入完成后判断需不需要调整。

情况四的解决方案:因为我们做的是一棵没有重复数据的平衡二叉树所以遇到这种情况的时候不进行插入操作。当然如果做的是一棵可以有重复数据的平衡二叉树,那遇到这种情况的时候可以个人的想法放左边放右边都可以。

源代码:

//插入数据
Node *insertNode(Node *curRoot, Ty data)
{
	//插入分有四个大情况
	if (curRoot == NULL)			  //当前节点是空的
		curRoot = creatAVLTree(data); //如果是空就直接创建一个新的节点
	else if (data < curRoot->data)	  //要插入的数据比当前节点的数据小
	{
		//往左边跑
		curRoot->LChild = insertNode(curRoot->LChild, data);
		//插入完成之后,判断需不需要调整树
		if (HEIGHT(curRoot->LChild) - HEIGHT(curRoot->RChild) == 2)
			//因为插入的位置在左边,所以插入完成之后,左子树的高度大于等于右子树高度
			curRoot = data < curRoot->LChild->data ? LL_Rotation(curRoot) : LR_Rotation(curRoot);
	}
	else if (data > curRoot->data) //要插入的数据比当前节点的数据大
	{
		//往右边跑
		curRoot->RChild = insertNode(curRoot->RChild, data);
		if (HEIGHT(curRoot->RChild) - HEIGHT(curRoot->LChild) == 2)
			//因为插入的位置在右边,所以插入完成之后,右子树的高度大于等于左子树高度
			curRoot = data > curRoot->RChild->data ? RR_Rotation(curRoot) : RL_Rotation(curRoot);
	}
	else //要插入的数据和当前节点的数据一样大
		printf("无法插入数据\n");
	//获取新高度
	curRoot->height = GET_NEW_HEIGHT(curRoot);
	return curRoot; //插入完成之后返回当前节点的指针
}

平衡二叉树的删除操作:

删除操作也是要考虑四个大情况:

  • 当前节点是空的
  • 要删除的数据比当前数据小
  • 要删除的数据比当前数据大
  • 要删除的数据和当前数据一样大

情况一的解决方案:没有删除的必要了,结束掉函数

情况二的解决方案:往左边递归找到对应位置,然后进行删除操作

情况三的解决方案:往右边递归找到对应位置,然后进行删除操作

情况四的解决方案:针对这个情况又要分为两个小情况

  • 当前节点的左子树和右子树都存在
  • 当前节点的左右子树至多有一个存在

具体解决方案看代码和注释

源代码:

//查找节点
//找最大节点
Node *maxNode(Node *curRoot)
{
	if (curRoot == NULL)
		return NULL;
	//往右边找
	while (curRoot->RChild)
		curRoot = curRoot->RChild;
	return curRoot;
}

//找最小节点
Node *minNode(Node *curRoot)
{
	if (curRoot == NULL)
		return NULL;
	while (curRoot->LChild)
		curRoot = curRoot->LChild;
	return curRoot;
}

//删除数据
Node *deleteNode(Node *curRoot, Ty data)
{
	//删除数据有四个大情况
	if (curRoot == NULL)	  //当前节点是空的
		return NULL;		  //删除了个寂寞直接结束掉整个函数
	if (data < curRoot->data) //要删除的数据比当前节点的数据小
	{
		//往左边跑
		curRoot->LChild = deleteNode(curRoot->LChild, data);
		//获取新高度
		curRoot->height = GET_NEW_HEIGHT(curRoot);
		//判断需不需要调整
		if (HEIGHT(curRoot->RChild) - HEIGHT(curRoot->LChild) == 2)
			curRoot = HEIGHT(curRoot->RChild->LChild) > HEIGHT(curRoot->RChild->RChild) ? RL_Rotation(curRoot) : RR_Rotation(curRoot);
	}
	else if (data > curRoot->data) //要删除的数据比当前节点的数据大
	{
		//往右边跑
		curRoot->RChild = deleteNode(curRoot->RChild, data);
		curRoot->height = GET_NEW_HEIGHT(curRoot);
		if (HEIGHT(curRoot->LChild) - HEIGHT(curRoot->RChild) == 2)
			curRoot = HEIGHT(curRoot->LChild->RChild) > HEIGHT(curRoot->LChild->LChild) ? LR_Rotation(curRoot) : LL_Rotation(curRoot);
	}
	else
	{ //要删除的数据和当前节点的数据一样大
		//针对于curRoot这个节点做删除操作
		//主要有两个主要的情况
		if (curRoot->LChild && curRoot->RChild) // curRoot有左子树和右子树
		{
			//先判断左右子树的高度,将高度比较高的子树的节点拿到上面来
			if (HEIGHT(curRoot->LChild) > HEIGHT(curRoot->RChild))
			{ //左子树的高度比右子树的高度高
				//找到左子树的最大节点
				Node *max = maxNode(curRoot->LChild);
				//找到之后就将max的数据替换curRoot的数据
				curRoot->data = max->data;
				//赋值完成之后继续递归,然后释放掉max对应的节点,不能直接在这里释放,因为要调整树的高度
				curRoot->LChild = deleteNode(curRoot->LChild, max->data);
			}
			else
			{ //左子树的高度小于等于右子树的高度
				//找到右子树的最小节点
				Node *min = minNode(curRoot->RChild);
				curRoot->data = min->data;
				curRoot->RChild = deleteNode(curRoot->RChild, min->data);
			}
		}
		else //上一种情况的否定,即curRoot没有子树或者只有一边
		{
			//释放内存
			Node *temp = curRoot;
			// curRoot拿到存在的子树
			curRoot = curRoot->LChild ? curRoot->LChild : curRoot->RChild;
			free(temp);
		}
	}

	return curRoot; //删除完成之后就返回当前节点
}

主函数测试:

int main()
{
	AVLTree *tree = NULL;
	for (int i = 1; i < 10; i++)
		tree = insertNode(tree, i);
	show_pre(tree); //前序打印树
	printf("----------------------------\n");
	//删除6这个节点
	tree = deleteNode(tree, 6);
	show_pre(tree);
	printf("程序结束\n");
	return 0;
}

运行结果:

删除前和删除后的平衡二叉树:

到此这篇关于C语言之平衡二叉树详解的文章就介绍到这了,更多相关C++平衡二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言平衡二叉树详解

    目录 调整措施: 一.单旋转 二.双旋转 AVL树的删除操作: 删除分为以下几种情况: 1.要删除的节点是当前根节点T. 2.要删除的节点元素值小于当前根节点T值,在左子树中进行删除. 3.要删除的节点元素值大于当前根节点T值,在右子树中进行删除. 总结 平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树.这个方案很好的解决了二叉查找树退化成链表的

  • C语言数据结构之平衡二叉树(AVL树)实现方法示例

    本文实例讲述了C语言数据结构之平衡二叉树(AVL树)实现方法.分享给大家供大家参考,具体如下: AVL树是每个结点的左子树和右子树的高度最多差1的二叉查找树. 要维持这个树,必须在插入和删除的时候都检测是否出现破坏树结构的情况.然后立刻进行调整. 看了好久,网上各种各种的AVL树,千奇百怪. 关键是要理解插入的时候旋转的概念. // // AvlTree.h // HelloWorld // Created by feiyin001 on 17/1/9. // Copyright (c) 201

  • C语言 数据结构平衡二叉树实例详解

    数据结构平衡二叉树 参考代码如下: /* 名称:平衡二叉树 语言:数据结构C语言版 编译环境:VC++ 6.0 日期: 2014-3-26 */ #include <stdio.h> #include <malloc.h> #include <windows.h> #define LH +1 // 左高 #define EH 0 // 等高 #define RH -1 // 右高 #define N 5 // 数据元素个数 typedef char KeyType; /

  • 如何使用C语言实现平衡二叉树数据结构算法

    目录 前言 一.平衡二叉树实现原理 二.平衡二叉树实现算法 三.全部代码 前言 对于一个二叉排序树而言 它们的结构都是根据了二叉树的特性从最左子树开始在回到该结点上继续往右结点走 通过该方式进行递归操作,并且该二叉排序树的结构也是从小到大依次显示 那么我们假设a[10]={ 3,2,1,4,5,6,7,10,9,8 };我们需要查找改列表中的某一个结点的值 那么我们通过二叉排序树的展示,会展示成如图: 可以发现,如果我们想通过二叉排序树这个深度为8的树来查找某个数 我们需要走到最后,这是最坏的打

  • C语言平衡二叉树真题练习

    目录 一.题目描述 二.解题思路 自顶向下的递归(暴力解法) 自底向上的递归(最优解法) 题目难度:简单 LeetCode链接:平衡二叉树 一.题目描述 给定一个二叉树,判断它是否是高度平衡的二叉树. 本题中,一棵高度平衡二叉树定义为:一个二叉树 每个节点 的左右两个子树的高度差的绝对值不超过 1 . 二.解题思路 一棵二叉树是平衡二叉树,当且仅当其所有子树也都是平衡二叉树,因此我们使用递归的方式依次判断其所有子树是否为平衡二叉树,就知道这棵二叉树是不是平衡二叉树了. 自顶向下的递归(暴力解法)

  • C语言之平衡二叉树详解

    目录 什么是平衡二叉树 平衡二叉树的基本特点 为什么会出现平衡二叉树 二叉树四种不平衡的情况 C语言实现平衡二叉树 什么是平衡二叉树 平衡二叉树是具有平衡属性的有序二叉树,所谓的平衡即当前树的左右子树高度差的绝对值不超过1.因为平衡二叉树是由苏联数学家Adelson-Velskii和Landis提出,所以又称为AVL树. 平衡二叉树的基本特点 是特殊的有序二叉树 左右子树高度差的绝对值不超过1 左右子树仍然是平衡二叉树 为什么会出现平衡二叉树 在学习平衡二叉树之前必定已经学过有序二叉树,有序二叉

  • 易语言子程序知识点详解

    将程序分割成较小的逻辑组件就可以简化程序设计任务,这些逻辑组件被称为子程序. 子程序可用于压缩重复任务或共享任务,例如,压缩频繁的计算处理等等. 用子程序编程有两大好处: 子程序可使程序划分成离散的逻辑组件,每个组件都比无子程序的整个程序容易调试及理解: 一个应用程序中的子程序,往往不必修改或只需稍作改动,便可以成为另一个程序的子程序. 每次调用子程序时,子程序中的所有语句都将被从第一条开始顺序执行,当执行到子程序尾部或者遇到"返回"命令时即返回到调用此子程序语句的下一条语句处. 子程

  • Spring表达式语言SpEL用法详解

    这篇文章主要介绍了spring表达式语言SpEL用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 (1)spring表达式语言是一个支持运行时查询和操作对象图得我强大表达式语言. (2)语言类似于EL:SpEL使用#{...}作为定界符.所有在大括号中的字符串均被认为是SpEL. (3)SpEL为bean的属性进行动态赋值提供了便利. (4)通过SpEL可以实现: 通过Bean的id对Bean进行引用 调用方法及引用对象的属性 计算表达式

  • R语言数据类型深入详解

    R语言用来存储数据的对象包括: 向量, 因子, 数组, 矩阵, 数据框, 时间序列(ts)以及列表 意义介绍 1. 向量(一维数据): 只能存放同一类型的数据 语法: c(data1, data2, ...),访问的时候下标从1开始(和Matlab相同);向量里面只能存放相同类型的数据. > x <- c(1,5,8,9,1,2,5) > x [1] 1 5 8 9 1 2 5 > y <- c(1,"zhao") # 这里面有integer和字符串, 整

  • R语言关联规则深入详解

    在用R语言做关联规则分析之前,我们先了解下关联规则的相关定义和解释. 关联规则的用途是从数据背后发现事物之间可能存在的关联或者联系,是无监督的机器学习方法,用于知识发现,而非预测. 关联规则挖掘过程主要包含两个阶段:第一阶段从资料集合中找出所有的高频项目组,第二阶段再由这些高频项目组中产生关联规则. 接下来,我们了解下关联规则的两个主要参数:支持度和置信度. 用简化的方式来理解这两个指标,支持度是两个关联物品同时出现的概率,而置信度是当一物品出现,则另一个物品也出现的概率. 假如有一条规则:牛肉

  • R语言“循环”知识点详解

    可能有一种情况,当你需要执行一段代码几次. 通常,顺序执行语句. 首先执行函数中的第一个语句,然后执行第二个语句,依此类推. 编程语言提供允许更复杂的执行路径的各种控制结构. 循环语句允许我们多次执行一个语句或一组语句,以下是大多数编程语言中循环语句的一般形式 - R编程语言提供以下种类的循环来处理循环需求. 单击以下链接以检查其详细信息. Sr.No. 循环类型和描述 1 repeat循环 多次执行一系列语句,并简化管理循环变量的代码. 2 while循环 在给定条件为真时,重复语句或语句组.

  • C语言字符串数组详解

    C语言字符串数组 字符串是连续的字符序列,最后以空字符'\0'作为终止符.一个字符串的长度指所有字符的数量,但不包括终止符.在 C 语言中,没有字符串类型,自然也就没有运算符以字符串为操作数. 字符串被存储在元素类型为 char 或宽字符类型数组中(宽字符类型指 wchar_t.char16_t 或 char32_t).宽字符组成的字符串也称为宽字符串(wide string). C 标准库提供了大量的函数,它们可以对字符串进行基本操作,例如字符串的比较.复制和连接等.在这些传统的字符串函数以外

  • C语言lseek()函数详解

     头文件: #include <sys/types.h> #include <unistd.h> 函数原型: off_t lseek(int fd, off_t offset, int whence);//打开一个文件的下一次读写的开始位置 参数: fd 表示要操作的文件描述符 offset是相对于whence(基准)的偏移量 whence 可以是SEEK_SET(文件指针开始),SEEK_CUR(文件指针当前位置) ,SEEK_END为文件指针尾 返回值: 文件读写指针距文件开头

  • 关于C语言qsort函数详解

    目录 C语言qsort函数详解 一.qsort函数是什么 二.使用qsort排序-以升序为例 1.整形数组排序 2.字符数组排序 3.字符指针数组排序 4.结构体数组排序 5.浮点型数组排序 三.使用冒泡排序思想模拟实现qsort函数 1.什么是冒泡排序 2.冒泡排序代码 3. 使用冒泡排序思想模拟实现qsort函数 C语言qsort函数详解 一.qsort函数是什么 我们可以使用  搜索库函数网址或者MSDN软件进行查找. qsort()函数:快速排序的函数  -引用stdlib.h头文件 参

  • Go语言--切片(Slice)详解

    目录 一.定义切片 1.声明一个未指定大小的数组来定义切片 2.使用make()函数来创建切片 二.切片是可索引的 1.len() 和 cap() 函数 三.切片截取 四.增加切片的容量 说明: Go 语言切片是对数组的抽象. Go 数组的长度不可改变,在特定场景中这样的集合就不太适用,Go中提供了一种灵活,功能强悍的内置类型切片("动态数组"),与数组相比切片的长度是不固定的,可以追加元素,在追加时可能使切片的容量增大. 一.定义切片 注意:切片不需要说明长度 1.声明一个未指定大小

随机推荐