数据结构——树——二叉树——大小堆

目录

1>>导言

2>>树

2.1>>树的相关术语

2.2>>树的表示和应用场景

3>>二叉树

3.1>>完全二叉树

3.2>>大小根堆

4>>结语

---

1>>导言

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

2>>树

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

这里能看到整个结构像是一颗倒挂的树，因此，我们把它叫做树。

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

每个结点指向的一块区域称作子树，两个不同子树之间不能相交，如：

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

如这张图，也就是说，一个结点只能有一个前驱结点。

2.1>>树的相关术语

父结点/双亲结点：若⼀个结点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点
子结点/孩子结点：⼀个结点含有的子树的根结点称为该结点的子结点；如上图：B是A的孩子结点
结点的度：⼀个结点有几个孩子，他的度就是多少；比如A的度为3，F的度为0
树的度：⼀棵树中，最大的结点的度称为树的度；如上图：树的度为3
叶子结点/终端结点：度为 0 的结点称为叶结点；如上图： J、F、K等结点为叶结点
分支结点/非终端结点：度不为 0 的结点；如上图：B、E、G等结点为分支结点
兄弟结点：具有相同父结点的结点互称为兄弟结点(亲兄弟)；如上图： B、C 是兄弟结点
结点的层次：从根开始定义起，根为第1层，根子节点为第2层；上图 J 为第四层
结点的高度或者深度：树中结点的最大层次；如上图：树高度为4
结点的祖先：从根到该节点所经分支上的所有结点；如上图：A是所有结点的祖先
路径：一条从树中任意结点出发，沿父节点-子节点链接，达到任意结点的序列；比如A到K路径为A-C-G-K
子孙：以某节点为根的子树中任一结点都称为该节点的子孙；如上图，所有结点都是A的子孙
森林：有很多棵互不相交树的集合称为森林

2.2>>树的表示和应用场景

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

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

3>>二叉树

二叉树具备一下两点：

1.二叉树不存在度大于2的结点

2.二叉树的子树有左右之分，不能颠倒，因此二叉树也是有序树

以上为二叉树的各种存在形式

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

对大家来说，满二叉树太难见到了，因此我们引申出了一个完全二叉树

3.1>>完全二叉树

完全二叉树除了叶子结点的上一个分支结点，其余所有结点都有两个度

这是什么意思呢？

来看这张图或许你就懂了。注意：这里的叶子结点必须从左到右有，不能3和5有叶子结点，而4位置是空的。

3.2>>大小根堆

堆是什么意思呢？就是在完全二叉树的基础上，在加上对数据的处理：

如图的小根堆，根部数据最小，因此得名小根堆，也叫小堆。小堆每个结点的数据均不小于其父节点的值。

如图的大根堆，根部数据最大，因此得名大根堆，也叫大堆。大堆每个结点的数据均不大于其父节点的值。

再来看它们的位置关系：

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

双亲：parent =（child-1）/2；

左孩子：leftchild=parent*2+1；

右孩子：rightchild=parent*2+2；

注意：（child-1）/2为0时无双亲结点。parent*2+1>=n无左孩子结点。parent*2+2>=n无右孩子结点

n表示有n个结点

4>>结语

        今天讲了树的相关概念和术语，二叉树的概念，二叉树的分类，还有堆的位置关系。希望宝子们能在本篇文章有所收获，能帮助到宝子们小编就非常开心啦。希望明天还能看到宝子们，明天跟着小编一起实现堆的代码吧。敬请期待...