请要相信我,30分钟让你掌握AVL树(平衡二叉树)

2024-06-09 04:08

本文主要是介绍请要相信我,30分钟让你掌握AVL树(平衡二叉树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 

                    请要相信我,30分钟让你掌握AVL树(平衡二叉树)

前言:本文不适合 给一组数据15分钟就能实现AVL的插入和删除操作的大牛(也请大牛不要打击小菜)

本文适合,对avl还不了解,还没有亲自实现avl的插入和删除操作的同学

ps,你在嘲笑楼主的题目时,你已证明了自己正在嘲笑自己的智商。我们要善于征服陌生的事物。你如果有半个小时时间就心无杂念的开始吧,建议那些读10分钟文章就心燥还是关闭浏览器吧。


文章结构:


什么是二叉排序树(bst)
二叉排序树(Binary Sort Tree)又称二叉查找树。 它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树;
 

好了二叉排序树定义很好理解(如果还不理解,为了不浪费时间,先暂停一下,去google or baidu 下,理解了再继续),再此就不举别的例子了,下面我实现下BST的一些基本操作算法。
BST的基本操作
typedef struct _BitNode
{
int data;
struct _BitNode *lchild,*rchild;
}BitNode,*BiTree;
1.1 ,BST的搜索:
为什么先实现搜索呢?一般BST里面没有重复的元素,你增添或者删除元素,都必须要先查找一下,看有没有呀,所以BST搜索要先实现,这个搜索是很简单的,慢慢看我讲解吧,
我们先看这张图

假如你想找到数值为3的节点并给你这个树的根节点,且规定你只能看到这个根节点左右孩子(其他你们权限看到,也看不到)。那不就是很容易啦,先用3和根节点(此为6)比,显然比6小。那我就去找他的左孩子比,注意,此时4就是6的左子树的根了,那我们就和4这个新的树根比吧,显然又比4小。那我们就继续找这个新根的左孩子比,而此时3就是4的左子树的根了,那我们就和这个根比,哇塞,我们顺藤摸瓜,终于找到了哦!!,那我们就提炼一下这个过程吧,注意哦,我们每次都是和树根相比较的哦!
规则:
1.先和这棵树的根比
2.如果比这个树根小就和这个树根的左子树的根比,否则就和这个树根的右子树比。
3.重复2过程,直到根为空为止。
        根据3个步骤很容易实现递归代码。
//搜索元素,参数依次为0: 根节点,1: 查找的元素,2: 找到目标元素的前一个节点指针,初始值为NULL
// 3:如果返回真把目标到元素的指针指向n,返回假,就把pre复制给n)(参数如果不明白,先不要细究,往下看吧)
 bool SearchBST(BiTree T,int key,BiTree pre,BiTree&n);
 bool SearchBST(BiTree T,int key,BiTree pre,BiTree&n)
{
if(!T)
{
n=pre;       //如果此数为空树,那我们就把前一个元素指针pre(此时为NULL)复制给n,注意树为空时,n才为NULL。
return false;   //返回假没有找到
}
else if(key==T->data)
{
n=T;        //找到了就把目标元素指针给n
return true;
}
if(key<T->data)
SearchBST(T->lchild,key,T,n) ;//去找他的左子树根比
else
{
SearchBST(T->rchild,key,T,n);//去找他的右子树根比。
}
}
1.2 BST的增添元素算法实现

这篇关于请要相信我,30分钟让你掌握AVL树(平衡二叉树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1044181

相关文章

30常用 Maven 命令

Maven 是一个强大的项目管理和构建工具,它广泛用于 Java 项目的依赖管理、构建流程和插件集成。Maven 的命令行工具提供了大量的命令来帮助开发人员管理项目的生命周期、依赖和插件。以下是 常用 Maven 命令的使用场景及其详细解释。 1. mvn clean 使用场景:清理项目的生成目录,通常用于删除项目中自动生成的文件(如 target/ 目录)。共性规律:清理操作

2024网安周今日开幕,亚信安全亮相30城

2024年国家网络安全宣传周今天在广州拉开帷幕。今年网安周继续以“网络安全为人民,网络安全靠人民”为主题。2024年国家网络安全宣传周涵盖了1场开幕式、1场高峰论坛、5个重要活动、15场分论坛/座谈会/闭门会、6个主题日活动和网络安全“六进”活动。亚信安全出席2024年国家网络安全宣传周开幕式和主论坛,并将通过线下宣讲、创意科普、成果展示等多种形式,让广大民众看得懂、记得住安全知识,同时还

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

生信代码入门:从零开始掌握生物信息学编程技能

少走弯路,高效分析;了解生信云,访问 【生信圆桌x生信专用云服务器】 : www.tebteb.cc 介绍 生物信息学是一个高度跨学科的领域,结合了生物学、计算机科学和统计学。随着高通量测序技术的发展,海量的生物数据需要通过编程来进行处理和分析。因此,掌握生信编程技能,成为每一个生物信息学研究者的必备能力。 生信代码入门,旨在帮助初学者从零开始学习生物信息学中的编程基础。通过学习常用

软件架构模式:5 分钟阅读

原文: https://orkhanscience.medium.com/software-architecture-patterns-5-mins-read-e9e3c8eb47d2 软件架构模式:5 分钟阅读 当有人潜入软件工程世界时,有一天他需要学习软件架构模式的基础知识。当我刚接触编码时,我不知道从哪里获得简要介绍现有架构模式的资源,这样它就不会太详细和混乱,而是非常抽象和易

如何掌握面向对象编程的四大特性、Lambda 表达式及 I/O 流:全面指南

这里写目录标题 OOP语言的四大特性lambda输入/输出流(I/O流) OOP语言的四大特性 面向对象编程(OOP)是一种编程范式,它通过使用“对象”来组织代码。OOP 的四大特性是封装、继承、多态和抽象。这些特性帮助程序员更好地管理复杂的代码,使程序更易于理解和维护。 类-》实体的抽象类型 实体(属性,行为) -》 ADT(abstract data type) 属性-》成

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

c++习题30-求10000以内N的阶乘

目录 一,题目  二,思路 三,代码    一,题目  描述 求10000以内n的阶乘。 输入描述 只有一行输入,整数n(0≤n≤10000)。 输出描述 一行,即n!的值。 用例输入 1  4 用例输出 1  24   二,思路 n    n!           0    1 1    1*1=1 2    1*2=2 3    2*3=6 4

嵌入式面试经典30问:二

1. 嵌入式系统中,如何选择合适的微控制器或微处理器? 在嵌入式系统中选择合适的微控制器(MCU)或微处理器(MPU)时,需要考虑多个因素以确保所选组件能够满足项目的具体需求。以下是一些关键步骤和考虑因素: 1.1 确定项目需求 性能要求:根据项目的复杂度、处理速度和数据吞吐量等要求,确定所需的处理器性能。功耗:评估系统的功耗需求,选择低功耗的MCU或MPU以延长电池寿命或减少能源消耗。成本

JAVA初级掌握的J2SE知识(二)和Java核心的API

/** 这篇文章送给所有学习java的同学,请大家检验一下自己,不要自满,你们正在学习java的路上,你们要加油,蜕变是个痛苦的过程,忍受过后,才会蜕变! */ Java的核心API是非常庞大的,这给开发者来说带来了很大的方便,经常人有评论,java让程序员变傻。 但是一些内容我认为是必须掌握的,否则不可以熟练运用java,也不会使用就很难办了。 1、java.lang包下的80%以上的类