1. 分类
树分为二叉树和多叉树
其中，二叉树（每个节点最多有两个子节点）有
- 完全二叉树 ：数据从上到下，从左到右依次进行排列
- 满二叉树 ： 所有的叶子结点都在一层，且最后一层节点数为2^(n-1) n是层数
- 有序二叉树 ：左边节点值小于当前节点，右边节点值大于当前节点
- 平衡二叉树 ： 左边节点值小于当前节点，右边节点值大于当前节点 左子树的高度和右子树的高度差的绝对值不超过1
- 红黑树 ： 最优二叉树
- 哈夫曼树
多叉树有：B树 和 B+树
2. 二叉树搜索
2.1 深度优先搜索
2.1.1 先序遍历
先访问父亲节点，再访问左孩子，再访问右孩子
eg：
上述树，先序遍历访问结果：
A B D H E C F G
2.1.2 中序遍历
先访问左孩子，再访问父亲节点，再访问右孩子
eg：
上述树，中序遍历访问结果：
H D B E A F C G
2.1.3 后序遍历
先访问左孩子，再访问右孩子，再访问父亲节点
eg：
上述树，后序遍历访问结果：
H D E B F G C A
2.2 广度优先搜索
从上往下打印节点，同一层的节点从左往右打印
eg：
上述树，广度优先搜索访问结果：
A B C D E F G H
3. 相关关键词
- 节点：树当中存数据的单元
- 根节点：一种没有父节点的节点 eg： A
- 父节点 一个节点的上级节点叫做它的父级节点 一个节点最多有一个父节点
- 子节点：一个节点的下级节点叫作它的子节点，一个节点可以有多个子节点
- 叶子节点：没有子节点的节点 eg：E F G H
- 节点的权 ： 节点值
- 路径：从根节点开始到该节点所走过的路线 路径长度是多少取决于该路径上边的条数
- 边：父子节点之间的连线叫边
- 子树：以某一个节点（非根节点）作为根节点的树称为子树
- 森林：多棵子树构成森林