- 使用树形结构可以大大提高效率
组织架构图, 文件目录结构
基本概念
- 节点, 根节点, 父节点, 子节点, 兄弟节点
- 空树, 子树, 左子树, 右子树
- 节点的度(degree): 子树的个数
- 树的度: 所有节点度中的最大值
- 叶子节点(leaf): 度为0的节点
- 非叶子节点: 度不为0的节点
- 层数(level): 根节点一般为第 0 / 1 层
- 节点的深度 (depth): 从根节点到当前节点的路径上的节点总数
- 节点的高度(Height): 从当前节点到最远叶子节点的路径上的节点总数
- 树的深度: 所有节点深度中的最大值
- 树的高度: 所有节点高度中的最大值
- 有序树
树中任意节点的子节点之间有顺序关系 - 无序树 - 自由树
- 森林: 有若干个有序树和自由树构成
二叉树 Binary Tree
特点
- 每个节点的度最大为2(最多有2个子树)
- 左子树和右子树是有顺序的
- 即使某个节点之后一棵子树, 也要区分左子树右子树
性质
- 非空二叉树的第i层, 最多有2^(n-1)个节点(n>=1)
- 在高度为h的二叉树上最多有2^h - 1 个节点(n>=1)
- 对于任何一棵非空二叉树, 如果叶子节点个数为n0, 度为2的节点个数为n2, 则有: n0 = n2 + 1
真二叉树
- 所有节点的度要么为0, 要么为2
满二叉树
- 所有节点的度要么为0, 要么为2, 所有的叶子节点都在最后一层
- 同样高度的二叉树中, 满二叉树的叶子节点数量最多, 节点数量最多
假设满二叉树的高度为h - 第i层节点数量 2^i - 1
- 叶子节点数量 2^(h - 1)
- 总节点数量 2^h - 1
- 高度 h = log2 (n+1)
完全二叉树 (complete binary tree)
- 叶子节点只会出现最后2层, 且最后一层的叶子节点都靠左对齐
- 完全二叉树从根节点到倒数第二层, 是满二叉树
- 满二叉树是完全二叉树
性质
- 度为1的节点只有左子树
- 度为1的节点要么是1个, 要么是0个
- 同样节点数量的二叉树, 完全二叉树的高度最小
- 假设完全二叉树的高度为h, 那么
- 至少有2^(h-1)个节点
- 至多有2^h - 1 个节点
- 总节点数量
2^(h-1) <= n < 2^h - 1
h - 1 <= log2n < h
h = floor(log2n) + 1
