数据结构（4）原来这个叫树

Dionysus_go 发布于2021-09-14 17:57 / 1007人阅读

摘要：树是啥现实中的树吗，是这个小王子里面的猴面包树又或者是北欧神话里面的世界树其实不是，在计算机中，树是一种数据结构，他的逻辑结构呈现了一棵树的状态，如图这个看着像北欧神话里面的世界树根呀，对其实也可以看成树的根，或是倒过

树是啥,现实中的树吗，是这个小王子里面的猴面包树？？

又或者是北欧神话里面的世界树

其实不是，在计算机中，树是一种数据结构，他的逻辑结构呈现了一棵树的状态，如图：

这个看着像北欧神话里面的世界树根呀，对其实也可以看成树的根，或是倒过来的树
如图：

在生活中树的结构也无处不在,比如常用的思维导图，家里的族谱，计算机的文件系统……

树

树是一种非线性存储的结构
且树的节点个数是 ≥0 的, 等于0则为空树
根有且只有一个

树的概念

父节点

他含有儿子(含有子节点)

节点的度

有多少个儿子(该节点有多少个子节点)

叶节点or终端节点

孤寡老人(他没有儿子，度为 0 )

兄弟节点

同一个爹生的就是（俩子节点都指向同一个父节点）

堂兄弟节点

同辈兄弟不是一个爹生的(同一层上面的节点，但不是同一个父节点)

祖先节点

就是根节点

树的度

祖先有多少个儿子(祖先节点有多少个子节点)

树的深度

家族到了第几代了（有多少层）

子孙节点

除根节点以外的都是

森林

一棵树叫树，那么多棵树那么就是森(且不相交)

图解:

注：
这儿一个孩子只有一个父亲（不可以认别认做干爹），反之父亲节点也不可以认干儿子，

既然树是一种数据结构那么他是如何存储的呢？

树的存储

树是如何存储的呢？他是非线性的如何存，上图看着似乎不太好存，用顺序表吗？或者用链表吗？单单用简单的顺序表与链表是无发体现出树的逻辑结构毕竟之前顺序表与链表似乎每个节点后面都只有一个，如果是单节点的树(后面会说到)用顺序表真的是完美，可是他有多个孩子咋办

这里就有一种方法可以解决叫做双亲表示法

双亲表示法：
父节点只存他左边的孩子的地址(第一个孩子)，然后左孩子指向他旁边的兄弟节点，如此反复，如果没有兄弟那么就指向空

图解结构

左边为逻辑结构，右边为物理结构

双亲表示法的结构代码

typedef  int DataTypestruct Node{   struct Node*firstChild;//一层里面第一个孩子(左孩子)   struct Node*borther;//其他亲兄弟节点   DataType data;//数据}

二叉树

树里面有一种特殊的树，二叉树，是啥样的呢？怎么理解吧，前面的树是计划生育前，你想要几个孩子都可以，计划生育后你最多只能有俩个孩子如图：

上面看到其实不是每一个节点都是俩个(现实中一个孩子的也很多，家里独宠)，其实以下情况也是二叉树

二叉树中里有俩特殊二叉树

满二叉树完全二叉树

上图对比可以得出完全二叉树其实就是节点不是满的，且完全二叉树也是严格要求的，他的节点之间必须挨着存放的，错误与正确示范如图：

二叉树和树一样也有一些定义

节点个数的计算
2^(H)-1 h为二叉树的深度or高度

二叉树个数就和卵细胞分裂类似但是差点,二叉树第一层只有一个节点，而细胞分裂一次就是俩个所以公式是2^H-1

如图：

二叉树的高度计算
log₂(n+1)->这里的log是以二为底(一些书中会写成lgN+1)，n为节点个数
这儿就和上面是差不多就是反过推就好了

叶子节点的计算
N0=N2+1,N0为叶子节点，而N2为度为2的节点，知道N0的节点也可以反推N2的节点个数

如图：

完全二叉树的最少/最多，有多少个节点
最少与最多的情况：

如图：

由上面可以看出满二叉树其实也是完全二叉树是最多的情况(公式如上)，那么最少的情况如何算呢： 2^(H-2):

2^(H-1) 就是从完全二叉树那里推出来的，满二叉树公式2^(H)-1,最少的情况比他少一层，所以高度减1，但他必须有一个节点所以要加回去2^(h-1)+1-1 -->2^(H-1)

第i层的节点个数：
2(i-1) 假设我们要求第一层的节点 2^(1-1)=1，因为层数是从 1 开始而节点个数的指数是从 0所以减一

切瓜环节

某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为( )
A 不存在这样的二叉树
B 200
C 198
D 199

在具有 2n 个结点的完全二叉树中，叶子结点个数为( )
An
B n+1
C n-1
D n/2

一棵完全二叉树的节点数位为531个，那么这棵树的高度为( )
A 11
B 10
C8
D 12

一个具有767个节点的完全二叉树，其叶子节点个数为()
A 383
B 384
C 385
D 386

第一题B，度为 2 的节点有199,求叶子节点，知道度为二的节点求叶子，套用公式犹如砍菜切瓜N0=N2+1

第二题A，这道推理题且要记住一个公式 N0+N2+N1=N （N0叶子,N2度为二的节点……）

图解：

第三题B，求树的高度还告诉了你节点个数，你说说这是啥，送分题呀，套公式log(N+1)–>log(531) 2¹⁰=1024 2⁹=512

第四题B，通过上面推导得出N₀+N₁+N₂=N,且N₁=节点奇数为0，偶数为1
2N₀+N₁=767 2N=767

学到这里对树已经有一个基础的认识了，可以算是下了一个新的副本的前几层，显然副本的难度并不是很高，这里算是暴风前的宁静了，下一层就是boss就是（顺序表二叉树）：堆，下下层为究极boss（链式二叉树），递归，记得拾起装备迎接后续的挑战

idc机房托管服务器托管原来有的数据怎样做统计阿里云服务器升级原来数据要转移数据分析这个专业如何云存储的原来

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/119941.html

当初我要是这么学习二叉树就好了

摘要：目录树形结构概念了解概念重要树的表示形式树的应用二叉树重点概念二叉树的种基本形态两种特殊的二叉树斜树满二叉树完全二叉树二叉树的性质第层结点个数树的所有最大点个数叶子结点和非叶子结点数量关系根据结点求树深度父子结点编号关系小 ...

chengjianhua 2021-11-23 09:51 评论0 收藏0
js的浅拷贝和深拷贝

摘要：拷贝分为浅拷贝和深拷贝。浅拷贝是引用复制，深拷贝是完全单纯拷贝数据的值。所以，这种方法只是简单绕过第一层箱子的引用复制深拷贝目前比较好的方法就是大法，要么就是自己写递归的深拷贝函数。附带深拷贝的自定义函数源自大佬的经常遇到数组或对象等引用类型作为函数的参数的情况，但又不想修改原来的数据，这时候就需要拷贝（基本类型的变量不需要考虑）。拷贝分为浅拷贝和深拷贝。浅拷贝是引用复制，深拷贝是完...

jsliang 2019-08-23 10:26 评论0 收藏0
差点掉坑，MySQL一致性读原来是有条件的

摘要：众所周知，在设定了隔离等级为及以上时，可以实现数据的一致性读。换句话来说，就是事务执行的任意时刻，读取到的数据是同一个快照，不会受到其他事务的更新影响。以前一直以为在事务内读到的数据不会受其他事务影响，后来发现只有普通的语句才是一致性读。众所周知，在设定了隔离等级为Repeatable Read及以上时，InnoDB 可以实现数据的一致性读。换句话来说，就是事务执行的任意时刻，读取...

cjie 2019-08-06 14:26 评论0 收藏0
差点掉坑，MySQL一致性读原来是有条件的

摘要：众所周知，在设定了隔离等级为及以上时，可以实现数据的一致性读。换句话来说，就是事务执行的任意时刻，读取到的数据是同一个快照，不会受到其他事务的更新影响。以前一直以为在事务内读到的数据不会受其他事务影响，后来发现只有普通的语句才是一致性读。众所周知，在设定了隔离等级为Repeatable Read及以上时，InnoDB 可以实现数据的一致性读。换句话来说，就是事务执行的任意时刻，读取...

Joyven 2019-06-25 19:00 评论0 收藏0
差点掉坑，MySQL一致性读原来是有条件的

摘要：众所周知，在设定了隔离等级为及以上时，可以实现数据的一致性读。换句话来说，就是事务执行的任意时刻，读取到的数据是同一个快照，不会受到其他事务的更新影响。以前一直以为在事务内读到的数据不会受其他事务影响，后来发现只有普通的语句才是一致性读。众所周知，在设定了隔离等级为Repeatable Read及以上时，InnoDB 可以实现数据的一致性读。换句话来说，就是事务执行的任意时刻，读取...

xcc3641 2019-08-01 10:17 评论0 收藏0