Tree
基本概念
树
- 在非空树中
- 根节点 (root node)：最顶端的节点（只有一个）
- 子节点 (child node)：除根节点之外，下面还连接有节点的节点
- 叶子节点 (leaf node)：下面不再连接有节点的节点
- 结点的分支数称为度
- 从节点 到 的路径 (path) 定义为节点 的一个序列。
- 这条路径的长 (length) 是为该路径上的边的条数， 即
- 从每一个节点到它自己有一条长为0 的路径
- 一棵树中从根到每个节点恰好存在唯一一条路径
- 对任意节点 ，它的的深度 (depth) 为从根到 的唯一的路径的长。因此，根的探度为0。 它的高 (height) 是从 到一片树叶的最长路径的长。因此所有的树叶的高都是0。一棵树的高等于它的根的高。
- 例如，图片上的树高为3；E 的深度为1，而高为2；F 的深度为1，高是1。
二叉树
Binary tree：子节点最多为两个的树
- 深度为 的二叉树至多有 个结点
- 包含 个结点的二叉树的高度至少为
- 每层都被塞满时，查找效率最高，为 。 当二叉查找树退化为单链表时，查找效率最低，为 。
- 叶子结点数为 ，度为 2 的结点数为 ，则
树的种类
二叉查找树平衡树红黑树哈夫曼树