【LeetCode】七、树、堆、图

1、树结构

节点、根节点、叶子节点：

高度、深度、层三者的示意图：

2、二叉树

相比其他树，二叉树即每个节点最多两个孩子（两个分支）：

如下图：满二叉树一定是完全二叉树，完全二叉树却不一定是满二叉树

补充：上面对满二叉树的定义不准确，满二叉树还要满足：所有的叶子节点在同一层

以上这个，虽然满足：除了叶子节点，每个节点都有两个孩子，但不满足所有叶子节点都在同一层，因此不是满二叉树。

3、二叉树的遍历

• 前序遍历，即根节点在前：前左右
• 中序遍历，即根节点在中：左中右
• 后序遍历，即根节点在后：左右后
  

如下：整个树看成三块，A、A的左子树、A的右子树，在两块子树里，继续按中序的左根右遍历，结果就是：D ⇒ B ⇒ E ⇒ A ⇒ F ⇒ C ⇒ G

同理，如果下面还有，那就继续分：

一句话，从根节点入手，把整个树看成左、根、右三大块，按左根右中序遍历，左右每块子树里，按子树的根节点继续分成左、根、右三大块，每块子树里依旧按照左根右中序遍历

4、堆结构（Heap）

堆即一种二叉树：完全二叉树。前面提到完全二叉树即从上到下、从左到右依次填满的二叉树，即可以左上有节点而右下无节点（图A、B），但：

• 不能同一层左边无节点，但右边有节点（图C），这样不满足从左到右，不是完全二叉树
• 不能同一层，左边有节点，但右边无节点，但下一层左边又有节点（图D），这样不满足从上到下，不是完全二叉树

堆有两个特点：

• 首先得是一个完全二叉树
• 其次，每个节点 >= 其所有孩子节点 （最大堆），或， 每个节点 <= 其所有孩子节点 （最小堆）

对最大堆，堆顶元素是整个堆的最大值，对最小堆，堆顶元素是整个堆的最小值

堆的时间复杂度：

比如删除一个最小堆的根节点：

干掉1以后，把右下角的7放上来，先保持完全二叉树的结构：

再向下比较，把7放到该放的位置。这是个最小堆，因此，先将7和最小的孩子节点2交换：

又发现7比孩子节点4和5打，因此，再把7和最小的孩子节点4交换，删除完成：

5、堆化

堆化，即把一组无序的数加到堆里去。可先把一组数转成完全二叉树，再将完全二叉树调整为最大堆或者最小堆。

如下，一个数组转为一个完全二叉树，其结果是唯一的（遍历数组，从上到下、从左到右的摆放），即0号元素当根节点，后面两个1、2号元素当根节点的左右子节点，3、4、5、6号元素分别当1、2号元素所在节点的左右子节点

将这个二叉树转为最小堆，核心思想是：把每个节点和其孩子节点进行对比，看每个节点是否满足：值小于等于任何它的一个子节点，不满足时，则把该节点和其最小的孩子节点交换。

因为叶子节点没有子节点，所以从倒数第二层开始看：9和7两个节点，9符合条件，均小于其两个子节点，7则不符，因此，7和5交换：

交换完成，再往上看上一层：10 > 5 也 10 > 9，选更小的5这个节点交换：

同理，换完后，第二层不再满足最小堆，需要再交换，10 > 8 也有 10 > 7，选最小的7这个节点进行交换。

6、图

和树的父子关系相比，图则类似邻居关系。对于图，有一个度的概念（degree），如下，顶点上有两条边与其相连，该顶点的度为2

分类：

前面提到了顶点的度，对于有向图，则是：

• 入度：指向该顶点的边的数量
• 出度：从该顶点出发的边的数量

如下：丁节点，入度为2，出度为0

再说权重图：如下，求杭州到北京的最短路径