1.属性
- 树是由n（n>=1）个有限节点组成一个具有层次关系的集合，形状像树。
- 节点属性：
- 度 这个节点所包含的子树个数。
- 关系 这个节点与父节点、子节点、兄弟节点、堂兄弟节点关系。祖先和子孙的关系。
- 层次 根为第1层，根的子节点为第2层，依次类推。
| 名词 | 含义 |
|---|---|
| 叶节点 | 度为0 |
| 分支节点 | 度不为0 |
| 兄弟关系 | 同一个父节点 |
| 堂兄弟关系 | 双亲同一层 |
| 祖先 | 从该节点到根节点所有分支节点 |
| 子孙 | 以某节点为根的子树中，任意节点都是根节点的子孙 |
- 树的属性
- 度 一棵树中，最大的节点的度称为树的度；
- 层次 树中节点的最大层次；
- n(n>0)个不相交的树的集合为森林！
2.树的分类
2.1 无序树
-
一个父节点下的子节点没有顺序关系，称为无序树，也是自由树。
无序树
2.1 有序树
- 一个父节点下的子节点有严格的顺序关系，称为有序树。
2.1.1 二叉树
- 二叉树属于有序树，并且每个节点最多含有两个子节点。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。
二叉树第i层至多有2^(i-1)个节点，深度为h时，最多有
下图中有一个节点拥有三个子节点，所以不是二叉树。
非二叉树
-
满二叉树
二叉树的最下面一层元素全部满就是满二叉树。
满二叉树 -
完全二叉树
二叉树的n-1层全满，n层元素全部连续集中在最左边。
完全二叉树 -
二叉查找树(二叉排序\搜索树)
特点：- 没有相同键值的节点。
- 若左子树不空，那么其所有子孙都比根节点小。
- 若右子树不空，那么其所有子孙都比根节点大。
- 左右子树也分别为二叉排序树。
如图：
二叉查找树 -
平衡二叉树
平衡二叉树是一种结构平衡的二叉查找树，左右子树的高度之差的绝对值最大为1。-
AVL树
最早被发明的平衡二叉树。
非平衡二叉树，绝对值之差大于1
平衡二叉树，绝对值之差为1 红黑树
一种被赋予颜色含义的平衡二叉树。每个节点的颜色为红色或黑色。
根节点为黑色。
每个叶子节点都有两个空的黑色节点。如果一个节点只有左孩子，那么它的右孩子填充一个空的黑色节点。相对，如果一个节点只有右孩子，那么它的左孩子填充一个空的黑色节点。
如果一个节点是红色的，那么它的两个孩子节点都是黑色的。
-
对于每个节点，到子孙叶节点的所有路径上包含相同数目的黑色节点。
错误的红黑树，不满足第5个条件
正确的红黑树 -
树堆
树堆一个节点拥有两个参数，一为本身的值key，一为优先级priority。key满足二叉查找树规则，priority满足堆的规则——孩子节点大于该节点。
树堆
-
2.1.2 哈夫曼树
- 哈夫曼树是一种针对权值的二叉树。一般为了减少计算机运算速度，将权重大的放在最前面。
- 构造
- 首先将元素排序。
- 取前两个元素构成树，其和作为根节点放入元素中。
- 只剩下两个元素，用根节点连接构成哈夫曼树。
例子：
给定数组 6、3、7、23、8，求其哈夫曼树。
排序：
结合最前的两个元素成为一棵树。
将第一排元素进行排序
结合最前的两个元素成为一棵树。
将第一排元素进行排序
结合最前的两个元素成为一棵树。
只有两个元素了，使用根节点将它们连接起来，构成哈夫曼树。
3.问题
- 树的深度和层次到底有什么区别呢？求解答。
