树、二叉树

2023-02-02 本文已影响0人 iOS小洁

树的概念

节点、根节点、父节点、子节点、兄弟节点、子树、左子树、右子树、空树

节点的度（degree）：子树的个数

树的度：所有节点度中的最大值

叶子节点（leaf）：度为 0 的节点

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

层数（level）：根节点在第 1 层，根节点的子节点在第 2 层，以此类推（有些教程也从第 0 层开始计算）

节点的深度（depth）：从根节点到当前节点的唯一路径上的节点总数

节点的高度（height）：从当前节点到最远叶子节点的路径上的节点总数

树的深度：所有节点深度中的最大值

树的高度：所有节点高度中的最大值

树的深度等于树的高度

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

无序树树中任意节点的子节点之间没有顺序关系也称为“自由树”

森林由 m（m ≥ 0）棵互不相交的树组成的集合

二叉树

二叉树的特点每个节点的度最大为 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

因此 n0 = n2 + 1

真二叉树 / Full Binary Tree：完满二叉树

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

满二叉树 / Perfect Binary Tree：完美二叉树

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

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

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

完全二叉树 / Complete Binary Tree：完全二叉树

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

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

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

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

题目

如果一棵完全二叉树有 768 个节点，求叶子节点的个数 
假设叶子节点个数为 n0，度为 1 的节点个数为 n1，度为 2 的节点个数为 n2 
总结点个数 n = n0 + n1 + n2，而且 n0 = n2 + 1 n = 2n0 + n1 – 1

完全二叉树的 n1 要么为 0，要么为 1 
n1为1时，n = 2n0，n 必然是偶数 
叶子节点个数 n0 = n / 2，非叶子节点个数 n1 + n2 = n / 2
n1为0时，n = 2n0 – 1，n 必然是奇数
叶子节点个数 n0 = (n + 1) / 2，非叶子节点个数 n1 + n2 = (n – 1) / 2

叶子节点个数 n0 = floor( (n + 1) / 2 ) = ceiling( n / 2 ) 
非叶子节点个数 n1 + n2 = floor( n / 2 ) = ceiling( (n – 1) / 2 )
因此叶子节点个数为 384