树形结构
树（Tree）的基本概念
- 节点、根节点、父节点、子节点、兄弟节点
- 一棵树可以没有任何节点，称为空树
- 一颗树可以只有一个节点，也就是根节点
- 子树、左子树、右子树
- 节点的度（degree）：子树的个数
- 树的度：所有节点度的最大值
- 叶子节点：度为0的节点
- 非叶子节点：度不是0的节点
- 层数（level）：根节点在第一层，根节点的子节点在第二层，以此类推（有些教材也从第0层开始计算）
- 节点的深度（depth）：从根节点到当前节点的唯一路径上的节点总数
- 节点的高度（height）：从当前节点到最远叶子节点路径上的节点总数
- 树的深度：所有节点深度中的最大值
- 树的高度：所有节点高度中的最大值
- 树的深度等于树的高度
有序树、无序树、森林
二叉树的特点
- 每个节点的度最大是2（最多有2个子树）
- 左子树和右子树是有顺序的
- 即使某节点只有一个子树，也是要区分左右子树
- 二叉树是有序树
- 二叉树的性质
- 非空二叉树的第 i 层，最多有 2**个节点（i>=1）**
- 在高度为h的二叉树上最多有 2-1个节点(h>=1)
- 对于任何一颗非空二叉树，如果叶子节点的个数是n0，度为2的节点个数是n2，则有 **n0 = n2 +1。求证：假设度是1的节点个数是n1，那么二叉树的总节点数 n = n0 + n1 + n2。二叉树的边数（二叉树中叶子节点没有边，度为1的节点一条边，度为2的节点两条边）则 t = n1 + 2*n2， 从二叉树的每个节点看，除了根节点头顶没有边以外，其余所有节点都顶着一条边，则 t = n - 1 = n0 + n1 + n2 - 1。由此得出： n1 + 2*n2 = n0 + n1 + n2 - 1，即 n2 = n0 - 1 。**
真二叉树（proper binary tree）
- 真二叉树中所有节点的度要么是0，要么是2。有叉一定是2个叉，才为真。
满二叉树（full binary tree）
- 所有节点的度要么是0，要么是2。并且所有叶子节点都在最后一层。
- 假设满二叉树的高度是 h（h>=1） ，那么：
- 第 i 层的节点数量 ： 2**
- 叶子节点数量： 2**
- 总节点的数量 n： n = 2**-1 = 2+2+2+ … + 2**，h = log(n + 1)**
- 在同样高度的二叉树中，满二叉树的叶子节点的数量最多、总节点数量最多
- 满二叉树一定是真二叉树，但是真二叉树不一定是满二叉树。
完全二叉树（complete binary tree）
- 叶子节点只会出现在最后两层，并且最后一层的叶子节点都靠左分布
- 对节点从上到下、从左到右开始编号，其所有编号都能与相同高度的满二叉树的编号对应
- 完全二叉树从根节点至倒数第二层是一棵满二叉树
-
完全二叉树的性质
度为1的节点只有左子树
- 度为1的节点要么只有1个，要么0个
- 同样节点数量的二叉树，完全二叉树的高度最小
- 假设完全二叉树的高度为h（h>=1），那么
- 至少有 2 个节点（**2+2+2+ … + 2**+1**）
- 最多有 2- 1 个节点(满二叉树，**2+2+2+ … + 2**）**
- 总节点的数量为 n ：
面试题
若有收获，就点个赞吧
0 人点赞
