二叉树 部分定义与性质

针对于知识回顾/复习，发现一些博客对于一些名词的定义各不相同，于是自己对于部分容易混淆的定义作一个简单的记录。

详细关于二叉树的内容可以看：二叉树-Hello算法，部分博客内容来自其中。

名词定义

1. 层

层（Level）：二叉树中的所有节点可以根据与根节点的距离分成不同的层次。根节点位于第 0 层，它的子节点位于第 1 层，依此类推。第 $ k $ 层的节点是与根节点的距离为 $ k $ 的节点集合。

2. 高度

树的高度（Height of the Tree）：从根节点到最远的叶子节点的最长路径上的边数。根节点的高度等于树的深度。

节点的高度（Height of a Node）：从某一节点到最远的叶子节点的路径上的边数。树的高度通常是根节点的高度。

3. 深度

树的深度（Depth of the Tree）：从根节点到最远的叶子节点的最长路径所经过的边数。一般来说，根节点的深度为 0。

节点的深度（Depth of a Node）：从根节点到该节点所经过的边的数量。

4. 度

节点的度（Degree of a Node）：一个节点拥有的子节点数量。二叉树中的节点度最大为 2。

性质

1. 节点总数

深度为 $ k $ 的二叉树最多有 $ 2^{k+1} - 1 $ 个节点。

2. 叶子节点数

一个有 $ n $ 个节点的二叉树的叶子节点数为 $ n - 内部节点数 $。

3. 层次关系

在二叉树中，第 $ i $ 层最多有 $ 2^i $ 个节点（ $ i $ 从 0 开始）。

4. 路径长度

二叉树的路径长度是树中所有节点到根节点的路径长度之和。

5. 满二叉树(完美二叉树)

如果一棵二叉树中所有的层次上的节点数都达到最大值，即第 $ i $ 层有 $ 2^i $ 个节点，则称为满二叉树或完美二叉树。

6. 完全二叉树

如果一棵二叉树中，除最后一层外的所有层上的节点数都达到最大值，并且最后一层的节点从左到右依次排列，这样的二叉树称为完全二叉树。

7. 完满二叉树

完满二叉树是一种二叉树，其中每个节点都有零个或两个子节点，没有只有一个子节点的节点。

8. 平衡二叉树

平衡二叉树中，任意节点的左子树和右子树的高度之差的绝对值不超过 1 。