上篇小编将队列的内容给大家讲完了这篇要步入新的篇章请宝子们做好上高速的准备随我一起上高速~今天来讲树的概念满二叉树完全二叉树以及堆的概念还要手动实现堆的代码废话不多说系好安全带。

树是一种非线性的数据结构这是何意就是它的物理结构和逻辑结构都不是连续的那为什么把它叫做树不叫什么草、花呢这就要来看看它的结构了

最上面的结点叫做根结点每个结点都有一个前驱结点和若干个后继结点。

子树1的结点不能和子树2相连否则就是图数据结构了这个后面学到会说。

父结点/双亲结点若⼀个结点含有子结点则这个结点称为其子结点的父结点如上图A是B的父结点子结点/孩子结点⼀个结点含有的子树的根结点称为该结点的子结点如上图B是A的孩子结点结点的度⼀个结点有几个孩子他的度就是多少比如A的度为3F的度为0树的度⼀棵树中最大的结点的度称为树的度如上图树的度为3叶子结点/终端结点度为

的结点如上图B、E、G等结点为分支结点兄弟结点具有相同父结点的结点互称为兄弟结点(亲兄弟)如上图

B、C

是兄弟结点结点的层次从根开始定义起根为第1层根子节点为第2层上图

为第四层结点的高度或者深度树中结点的最大层次如上图树高度为4结点的祖先从根到该节点所经分支上的所有结点如上图A是所有结点的祖先路径一条从树中任意结点出发沿父节点-子节点链接达到任意结点的序列比如A到K路径为A-C-G-K子孙以某节点为根的子树中任一结点都称为该节点的子孙如上图所有结点都是A的子孙森林有很多棵互不相交树的集合称为森林

一般使用兄弟孩子表示法就是孩子child指向孩子结点bro***r兄弟指向右边那个结点。

我们的硬盘存储就是树应用的一种根结点为c盘/d盘里面一个一个文件夹就是分支到文件就是叶子结点

3二叉树

这是现实中的二叉树这一棵还是满二叉树也就是说除了叶子结点所有结点都有两个度。

3.1完全二叉树

来看这张图或许你就懂了。

注意这里的叶子结点必须从左到右有不能3和5有叶子结点而4位置是空的。

3.2大小根堆

如图的小根堆根部数据最小因此得名小根堆也叫小堆。

小堆每个结点的数据均不小于其父节点的值。

如图的大根堆根部数据最大因此得名大根堆也叫大堆。

大堆每个结点的数据均不大于其父节点的值。

根据逻辑结构和存储结构能看出来双亲结点parent和孩子结点child的对应关系

双亲parent

注意child-1/2为0时无双亲结点。

parent*21n无左孩子结点。

parent*22n无右孩子结点

n表示有n个结点

今天讲了树的相关概念和术语二叉树的概念二叉树的分类还有堆的位置关系。

希望宝子们能在本篇文章有所收获能帮助到宝子们小编就非常开心啦。

希望明天还能看到宝子们明天跟着小编一起实现堆的代码吧。

敬请期待...