二叉树 部分定义与性质

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

详细关于二叉树的内容可以看:二叉树-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 。

热门相关:九星毒奶   亿万老公,送上门!   北宋大丈夫   娘娘每天都在洗白   末日乐园