https://blog.csdn.net/sinat_41144773/article/details/89530403

1、树的定义

  • n个结点的有限集合
  • 有且仅有一个根结点
  • 其余结点可分为m个根结点的子树。

2、二叉树

  • 每个节点最多拥有两个子节点
  • 左子树和右子树是有顺序的不能任意颠倒。

3、二叉树遍历

前序遍历（前根遍历）：根——>左——>右

中序遍历（中根遍历）：左——>根——>右

后序遍历（后根遍历）：左——>右——>根

4、满二叉树

  • 高度为h
  • 由2^h-1个节点构成的二叉树

5、完全二叉树

  • 完全二叉树是由满二叉树而引出来的

  • 深度为h，

  • 除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数
    (即1~h-1层为一个满二叉树)，

  • 第 h 层所有的结点都连续集中在最左边

堆一般都是用完全二叉树来实现的。


【完全二叉树如何储存】

完全二叉树中父亲和儿子之间有着神奇的规律，我们只需用一个一维数组就可以存储完全二叉树。

首先将完全二叉树进行从上到下，从左到右编号。
完全二叉树的一个父结点编号为k，那么它左儿子的编号就是2k，右儿子的编号就是2k+1。如果已知儿子（左儿子或右儿子）的编号是x，那么它父结点的编号就是x/2。

6、堆

堆是什么？堆是一种特殊的完全二叉树。

  • 所有父结点都比子结点要小的完全二叉树我们称为<mark>最小堆</mark>。
  • 反之，如果所有父结点都比子结点要大，这样的完全二叉树称为<mark>最大堆</mark>。

如下图所示，左边为最小堆，右边为最大堆。


为什么是堆？

归档

  • https://blog.csdn.net/qq_41117236/article/details/81029618