树形结构-二叉树

这是我参与更文挑战的第5天，活动详情查看：更文挑战

至多2个分叉，如果有3个或以上，叫多叉树

生活上的树形结构

使用树形结构可以大大提高效率，也是面试中的重点。

树的基本概念

节点、根节点、父节点、子节点、兄弟节点

• 节点：1、2、3、4、。。。
• 根节点：1
• 父节点：1是2、3、4、5、6的父节点，2是21、22的父节点
• 兄弟节点：2、3、4、5、6互为兄弟节点

一棵树可以没有任何节点，称为空树。

一棵树可以只有1个节点，也就是只有根节点。

子树：例如2-21就是一颗子树

左子树右子树：21是2的左子树，22是2的右子树

**节点的度：**子树的个数。2的度为2，6的度为1，61的度为0

**树的度：**所有节点度中最大的值。如图中最大的度为5，也就是1的度。

**叶子节点：**度为0的节点

**非叶子节点：**度不为0的节点

**层数：**根节点在第1层，跟节点的子 节点在第2层，以此类推

节点的深度：从根节点到当前节点的唯一路径上的节点总数。2的深度为2，31的深度为3

节点的高度：从当前节点到最远叶子节点路径上的节点总数。2的高度为3

**树的深度：**所有节点深度中的最大值，图的深度为4

**树的高度：**所有节点中高度的最大值，图的高度为4

树的深度等于树的高度

有序树、无序树、森林

有序树：树中任意节点的子节点之间是有顺序关系的

无序树：树中任意节点的子节点之间是没有顺序关系的

森林： 由 m 颗互不相交的树组成的集合

二叉树

• 每个节点的度最大为2（最多拥有2棵子树）

• 左子树和右子树的有顺序的

• 即使某节点只有一颗子树，也要区分左右子树

二叉树是有序树，因为左右子树是严格区分的。

非空二叉树的第 i 层，最多有 2^(i-1) 个节点（i >= 1）

在高度为 h 的二叉树上最多有 2^h-1 个节点（h >= 1）

对于任何一棵非空二叉树，如果叶子节点个数为 n0，度为 2 的节点个数为 n2，则有：n0 = n2 + 1，如何推导？

• 假设度为 1 的节点个数为 n1，那么二叉树的节点总数 n = n0 + n1 + n2
• 二叉树的边数 T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 -1

真二叉树

所有节点的度要么为0，要么为2

满二叉树

所有节点的度要么为0，要么为2。且所有的叶子节点都在最后一层。

在同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数量最多

满二叉树一定是真二叉树，真二叉树不一定是满二叉树。

假设满二叉树的高度为 h(h>=1)

• 第 i 层的节点数量：2^(i-1)
• 叶子节点数量：2^(h-1)
• 总节点：2^h-1

完全二叉树

叶子节点只会出现在最后2层，且最后1层的叶子节点都靠左对齐。

完全二叉树从根节点至倒数第2层是一棵满二叉树。

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

性质

• 度为 1 的节点 -> 只有左子树

• 度为 1 的节点要么 1 个，要么是 0 个

• 同样节点数量的二叉树，完全二叉树的高度最小

• 假设完全二叉树的高度为 h(h>=1)，那么

  • 至少有 2^(h-1) 个节点
  • 至多有 2^h -1 个节点
  • 若总节点数量为 n，则 2^(h-1) <= n < 2^h，h-1 <= log2^n < h，h = floor(log2^n) + 1，floor() 是向下取整，ceiling() 是向上取整。

还有两个关于二叉树的重要性质，在后面二叉堆会用到。如下图

面试题

老外教材的说法：