一、前言
堆是一种特殊的二叉树（完全二叉树），所以先了解一下树的概念，再来了解堆。
二、树的概念及结构
1、树的概念
树是一种非线性的数据结构，它是由n（n>0）个有限节点组成一个具有层次关系的集合，把它叫做树是因为他看起来像一棵倒挂的树，也就是说他是根朝上，而叶朝下的。
-
有一个特殊的节点，称为根节点，根节点没有前驱节点。
-
除根节点外，其余结点被分成M（M>0）个互不相交的集合T1、T2…、Tm，其中每一个集合又是一颗结构与树类似的子树。每棵子树有且只有一个前驱，可以有0个或多个后继。
-
因此，树是递归定义的。
-
树形结构中，子树之间不能有交集，否则就不是树形结构（除根节点外，每个结点只有父节点一个前驱）。
-
非树如下图
2、树的相关概念
- 节点的度：一个节点含有的子树的个数成为该节点的度。
- 层次：树的层次是从1开始的，所以如果是空树，那么该树的高度（深度）为0，如果该树只有1个结点，那么就是一层，那么高度就是1。
- 叶节点或终端节点：度为0的节点成为叶节点。
- 非终端节点或分支节点：度不为0的节点。
- 双亲结点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。
- 兄弟节点：指的是亲兄弟，也就是一个父亲。不是一个父亲的叫堂兄弟结点。
- 树：树的子树是不相交的。除根结点外每个子树只有一个父结点。一个N个结点的树有N-1条边。
- 树的度：一棵树中，最大的节点的度称为树的度。
- 节点的层次：从根开始定义起，根为第一层，根的子节点为第2层，以此类推。
- 树的高度或深度：树中节点的最大层次。
- 堂兄弟节点：双亲在同一层的节点互为堂兄弟。
- 祖先：从该点连着的向上都是祖先。
- 子孙：以某节点为根的子树中任一节点都成为该节点的子孙。
- 森林：由m棵互不相交的树的集合称为森林。
3、树的表示
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦，既要保存值域，也要保存节点和节点之间的关系，表示方式有很多种：双亲表示法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们一般采用最常见的孩子兄弟表示法。
4、树在实际中的应用
三、二叉树的概念及性质
1、概念
一棵二叉树是节点的一个有限集合，该集合：或者为空、或者由一个根节点加上两棵分别称为（根节点的）左子树和右子树的二叉树组成。
二叉树不存在度大于2的节点。
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。
2、特殊二叉树
- 满二叉树：一个二叉树，如果每一层的节点都达到最大值，则这个二叉树为满二叉树。也就是说，如果一个二叉树有k层，且节点总数为2^k-1，则为满二叉树。
- 完全二叉树：假设有k层，前k-1层都是满的，最后一层是连续的，这样的二叉树叫做完全二叉树。满二叉树是特殊的完全二叉树。
3、二叉树的性质
四、二叉树的存储结构
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
-
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费,如下图所示。而现实中使用中只有堆（特殊的完全二叉树，下一篇博客会详细讲解），才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
-
五、总结
- 博主长期更新，博主的目标是不断提升阅读体验和内容质量，如果你喜欢博主的文章，请点个赞或者关注博主支持一波，我会更加努力的为你呈现精彩的内容。
🌈专栏推荐
更新不易，希望得到友友的三连支持一波。收藏这篇文章，意味着你将永久拥有它，无论何时何地，都可以立即找到重新阅读；关注博主，意味着无论何时何地，博主将永久和你一起学习进步，为你带来有价值的内容。
