【数据结构(邓俊辉)学习笔记】二叉树01——二叉树表示与实现

2024-05-13 03:12

本文主要是介绍【数据结构(邓俊辉)学习笔记】二叉树01——二叉树表示与实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 0.概述
  • 1.树
    • 1.1 应用
    • 1.2 有根树
    • 1.3 有序树
    • 1.4 路径+环路
    • 1.5 深度 + 层。
    • 1.6 树的表示
  • 2. 二叉树的概述
  • 3 二叉树实现
    • 3.1 二叉树节点
    • 3.2 二叉树节点操作接口
    • 3.3 二叉树的实现

0.概述

介绍下二叉树的表示与实现。

1.树

1.1 应用

在这里插入图片描述

后缀表达式。
相对于线性结构O(n),树结构中元素的查找、插入、删除操作几乎提高了一个线性因子O(logn)。
结论:对二任何 ϵ \epsilon ϵ > 0,都有 logn = O( n ϵ n^\epsilon nϵ)。

1.2 有根树

在这里插入图片描述
从图论的角度看,树等价于连通无环图。

1.3 有序树

在这里插入图片描述
重要结论:任何一棵树中所含的边数应该恰好等于所有顶点的度数之和,同时也恰好等于顶点总数减1。即,任何一颗树中的边数与顶点数是同阶的——一棵树的总体规模如果可以度量为其中的点数在加上边数(n+e),从渐进意义上讲,这个规模也是和其中的顶点数或者是边数同阶的。故此后讨论到时间复杂度的时候,都是以顶点的数目n作为参照。

1.4 路径+环路

在这里插入图片描述
以边的数目度量路径长度,相对顶点而言会使算法描述以及理解更加的简明。
在这里插入图片描述
基本结论:

  • 树就是在无环和连通之间达到一个平衡的一种特定的图。

因为无环,所以它的边数不会太大,反之,正因为它又是连通的,所以边数又不能太少。 保证连通的情况下,边数能达到最少。 杜绝环路的情况下,它又能使用经可能多的边。

树中一旦指定了根,其它的节点都将获得一个确定的指标,通过这个指标,进一步将所有的顶点划分为不同的几类。故同一类顶点所具有的指标都是相等的,所以也称为等价类。

1.5 深度 + 层。

在这里插入图片描述
path(v): path from root to v
subtree(v): subtree rooted at v
即然任何一个节点都会以它所对应的那条通路的长度作为指标,而这样一个指标也很好体现了,任何一个节点V从根节点开始向下深入的程度,故v节点的指标称为深度。
在这里插入图片描述
叶子节点所对应的那个最大的深度,称为这棵树的高度。
树的高度也可以推广至其中的任何一颗子树,如此定义的子树高度,也称为根节点高度。所以任何一棵子树的高度就是它的根节点高度。
全树的高度也可以当作是全树根节点高度。

1.6 树的表示

一般地,树中各节点的孩子数目并不确定。每个节点的孩子均不超过k个的有根树,称作k叉树(k-ary tree)。
~  
~  
在这里插入图片描述

在这里插入图片描述
孩子节点的查找却不得不花费O(n)时间访遍所有节点。

在这里插入图片描述
将各节点组织为向量或列表,其中每个元素除保存节点本身的信息(data)外,还需要保存父节点(parent)的秩或位置。
向上查找父节点比较方便,向下查找长子和兄弟节点,便需要O(n),便是改进点。
在这里插入图片描述
令各节点将其所有的孩子组织为一个向量或列表。如此,对于拥有r个孩子的节点,可在O(r + 1)时间内列举出其所有的孩子。
向下查找解决了,向上查找优势丧失殆尽。
在这里插入图片描述
以上父节点表示法和孩子节点表示法各有所长,但也各有所短。为综合二者的优势,消除缺点,可令各节点既记录父节点,同时也维护一个序列以保存所有孩子。
~~   
~~   
美中不足,每一个节点的children引用所指向的那个数据集在规模上可能相差极其悬殊,每一个数据集的长度都恰好是这个节点所对应的出度,引用结论:
在这里插入图片描述
平均而言小的数据集规模,就是O(1),但这种组织方式有时需要O(n)。根源是每个节点出度是不尽相同的,找到新办法更加规范整洁高效。

~~   
~~   
有序多叉树 = 二叉树
为了保证作为多叉树特例的二叉树有足够的能力表示任何一棵多叉树,我们只需给多叉树增加一项约束条件——同一节点的所有孩子之间必须具有某一线性次序。
凡符合这一条件的多叉树也称作有序树(ordered tree)
在这里插入图片描述
长子兄弟法不仅是树的一种很好表示方法,而且也是对树本质的最深刻理解。
在此后介绍二叉树,并且用二叉树代表所有树的时候,会再次使用此方法。
对于树这样的全集,尽管二叉树只是它的一个特殊的子集,但在施加某些条件后,二叉树却足以用来表示和实现所有的树。而这种方法背后的原理在很大程度上就是长子兄弟法。

2. 二叉树的概述

在这里插入图片描述
不难看出二叉树肯定是树的一种特例,但饶有趣味的是在有跟性以及有序性能够保证的前提下,二叉树却足以描述所有树。
不含一度节点的二叉树称作真二叉树(proper binary tree)
在这里插入图片描述
一棵二叉树在横向上的宽度与他在纵向上的高度是呈一个指数关系,宽度是高度指数 w = 2 h w = 2^h w=2h,指数意味着 爆炸,意味着剧烈增长,所以如果节点的总数固定,宽度大致与它相当,但是高度会增长异常缓慢,反过来呈对数的形式——二叉树更加倾向于长宽,长宽很快,高度控制得当会长的异常缓慢。这个是二叉收索树的重要理论基础。
在这里插入图片描述
这样一般性的二叉树在很多操作包括算法实现以及对算法的理解上都会引来一些不必要的麻烦,而反过来一个比较有效的改进方法是将任何一颗一般性的二叉树转换为一颗真二叉树。
在这里插入图片描述
尽管添加很多节点,但是从渐进意义上讲他们的总数依然保持与原先规模相当。
更重要的是实现相应的算法的时候就会看到这种添加实际上完全是假想的,并不需要真正引入他们,只需要假想他们存在,算法便可以更加简洁实现且更加简洁被理解。
在这里插入图片描述
由此可见,描述并且实现以及利用树结构的话,不如说我们只需研究并实现二叉树。

3 二叉树实现

3.1 二叉树节点

作为图的特殊形式,二叉树的基本组成单元是节点与边;作为数据结构,其基本的组成实体是二叉树节点(binary tree node),而边则对应于节点之间的相互引用。

  • BinNode模板类
    在这里插入图片描述
    记录重要指标height,npl和color指标是为后面基于二叉树实现二叉搜索树和优先级队列等数据结构留有余地。
    每个节点通过引用指向其他节点,反过来每个节点也通过引用被其他节点指向。
    笼统地称节点占据的空间为一个位置。
    size():包括它在内所有后代的总数。
    insertAsLC() insertAsRC():它与其他节点相互作用使得整个二叉树在拓扑结构上发生变化地操作接口 。
    succ():后继接口,与线性结构中一样,返回的是当前节点在后面介绍的中序遍历意义下的直接后继。
    树形结构的四种遍历接口。

3.2 二叉树节点操作接口

在这里插入图片描述
size():递归实现方式,递推统计当前节点对应左子树size,以及对称地右子树size,两项合计再加上自身。

3.3 二叉树的实现

完成了对二叉树节点类定义后,基于它实现整体地bin tree。
在这里插入图片描述
内部接口

  • 成员变量
    通过内部两个变量 _size _root 分别记录当前树中地节点总数——规模,最为整棵树的入口树根节点位置。
  • 高度更新

算法思想:
一旦有节点加入或离开二叉树,则更新其所有祖先的高度。
在每一节点v处,只需读出其左、右孩子的高度并取二者之间的大者,再计入当前节点本身, 就得到了v的新高度。

在这里插入图片描述
更新每一节点本身的高度,只需执行两次getHeight()操作、两次加法以及两次取最大操作,不过常数时间,故updateHeight()算法总体运行时间也是O(depth(v) + 1),其中depth(v)为节点v的深度。

优化思路:在逆行向上依次更新 x 各祖先高度癿过秳中,一旦収现某一祖先癿高度没有収生发化,
算法即可提前终止;

在某些种类的二叉树(例如8.3节将要介绍的红黑树)中,高度的定义有所不同,因此这里将updateHeight()定义为保护级的虚方法,以便派生类在必要时重写(override)。
~~   
对外开放接口
size() empty() root() 都可以通过内部变量直接查询返回。
~~   

  • 节点插入
    在这里插入图片描述
    调用x->insertAsRC()接口,将二 者 按 照 父 子 关 系 相 互 联 接 , 同 时 通 过updateHeightAbove()接口更新x所有祖先的高度,并更新全树规模。
    注意这里的两个同名insertAsRC()接口,它们各自所属的对象类型不同。
    ~~   

  • 子树接入
    在这里插入图片描述
    若二叉树T中节点x的右孩子为空,则attachAsRC()接口首先将待植入的二叉树S的根节点作为x的右孩子,同时令x作
    为该根节点的父亲;然后,更新全树规模以及节点x所有祖先的高度;最后,将树S中除已接入的各节点之外的其余部分归还系统。

  • 子树删除
    在这里插入图片描述
    子树接入过程恰好相反。不同之处在于,需要将被摘除子树中的节点,逐一释放并归还系统。

  • 子树分离
    在这里插入图片描述

  • 复杂度
    就二叉树拓扑结构的变化范围而言,以上算法均只涉及局部的常数个节点。因此,除了更新祖先高度和释放节点等操作,只需常数时间。

这篇关于【数据结构(邓俊辉)学习笔记】二叉树01——二叉树表示与实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo