树的定义
树是一种数据结构，用来模拟具有树状结构性质的数据集合。由 n（n>0）个有限节点组成一个具有层次关系的集合。
树的特点
- 每个节点都只有有限个子节点或者无子节点
- 没有父节点的节点称为根节点
- 每一个非根节点有且只有一个父节点
- 除了根节点外，每个子节点可以分为多个不相交的子树
- 树没有回路（cycle）
树的术语
- 节点的度：一个节点含有的子树的个数称为该节点的度
- 树的度：一个树中，最大的节点的度称为树的度
- 叶子节点：度为 0 的节点
- 分支节点：度不为 0 的节点
- 父节点：若一个节点还有子节点，则这个节点是其子节点的父节点
- 子节点：一个节点含有的子树的根节点称为该节点的子节点
- 兄弟节点：具有相同父节点的节点互称为兄弟节点
- 节点的层次：从根开始定义起，根为第一层，根的子节点为第二层，以此类推
- 深度：对于任意节点 n，n 的深度为从根到 n 的唯一路径长，根的深度为 0
- 高度：对于任意节点 n，n 的高度为从 n 到该树的一个叶子节点的最长路径长，所有的叶子节点高度为 0
- 堂兄弟节点：父节点互为兄弟节点的节点称为堂兄弟节点
- 节点的祖先：从根到该节点所经历分支上的所有节点
- 子孙：以某节点为根的子树中任一节点都成为该节点的子孙
- 森林：由 m（m>=0）棵互不相交的树的集合称为森林
树的种类
- 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称自由树
有序树：树中任意节点的子节点之间有顺序关系
- 二叉树：任意节点的度<=2 的树
- 完全二叉树：深度为 d 的二叉树，除了第 d 层外，其他各层的节点数都达到最大值，且第 d 层所有节点从左向右紧密排列
- 满二叉树：最后一层节点达到最大值的完全二叉树
- 平衡二叉树（AVL 树）：当且仅当任何节点的两棵子树高度差不大于 1
- 排序二叉树（BST 树）：也称二叉搜索树，有序二叉树
- 霍夫曼树：带权路径最短的二叉树称为霍夫曼树或最优二叉树
- B 树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。