易混淆的概念
| 树的度 | 树中各结点度的最大值 |
|---|---|
| 结点的度 | 结点的分支数目 |
| 结点的高度 | 从下往上，默认从1开始 |
| 结点的深度/层次 | 从上往下，默认从1开始 |
| 树的路径长度 | 根节点到每个节点的路径长度之和 |
| 终端节点 | 等价为叶子结点（度为0的结点） |
| 非终端节点 | 非叶子结点，也叫分支结点 |
树的性质的常见考点
- 节点数=总度数+1
- 度为m的树VS m叉树
考点6和考点4是一个反解关系
树，森林
树的存储结构
双亲存储表示法（顺序存储）
孩子表示法（顺序+链式）
孩子兄弟法
左孩子右兄弟
树，森林，二叉树的转化
秉承左孩子右兄弟
==森林中的叶节点的个数等于对应二叉树的左孩子指针为空的节点个数==
树和森林的遍历
树的遍历
| 先根遍历 | 与这棵树相应二叉树的先序序列相同 |
|---|---|
| 后根遍历 | 与这棵树相应二叉树的中序序列相同 |
| 层次遍历 | 就一层一层编号呗 |
森林的遍历
| 先序遍历 | 从左到右依次对树先根遍历 |
|---|---|
| 中序遍历 | 从左到右依次对树后根遍历 |
二叉树
概念
可为空树，左右子树不可颠倒
二叉树 VS 度为2的树：
1. 度为2的树结点个数至少是3个
2. 度为2的树如果只有一个孩子，这个孩子无须区分左右，但是二叉树左右孩子的次序是固定的
特殊二叉树
- 满二叉树：所有叶子节点都在二叉树的最下一层
- 完全二叉树：与满二叉树编号相同的子树
- 二叉排序树（二叉查找树）（BST）：左子树上的所有结点的关键字均小于根节点
- 平衡二叉树（AVL）：在二叉排序树的基础上，左右子树深度之差不超过1
二叉树的性质：
- n0=n2+1
- 二叉树的第i层最多2的i-1次方个结点
- 高度为h的二叉树最多有2的h次方-1个结点
完全二叉树的性质：
- 完全二叉树最多只会有一个度为一的结点
- 编号为i的左儿子为2i，右儿子为 2i+1
- 完全二叉树的最后一个分支节点的序号为n/2向下取整
二叉树的存储结构
顺序存储结构：（比较适合完全二叉树，不然太浪费空间了）
链式存储：
