第5章：树与二叉树
时间：2022-11-02 09:30:00
文章目录
- 5 树与二叉树
-
- 5.1_1 树的定义和基本术语
- 5.1_2树的常考性质
- 5.2_十二叉树的定义和基本术语
- 5.2_2 二叉树的性质
- 5.2_3 二叉树的储存结构
- 5.3_1 二叉树的先、中、后历
- 5.3_2 二叉树的层次遍历
- 5.3_3 二叉树由遍历序列构造
- 5.3_4 线索二叉树的概念
- 5.3_5 二叉树的线索化
- 5.3_6 在线索二叉树中寻找前驱和后驱
- 5.4_1 树的储存结构
- 5.4_2 树木和森林的遍历
- 5.5_1 哈夫曼树
- 5.5_2 并查集
- 5.5_3 并进一步优化收集
5 树与二叉树
5.1_1 树的定义和基本术语
1.树的基本概念
除根节点外，树的每个结点只有一个前驱
2.基本术语
祖先结点
子孙结点
双亲结点
孩子结点
兄弟结点
堂兄弟结点
结点的层次 (深度)默认从1开始
结点的高度 从下往上数
结点的度 有几个分支
树的度 每个结点的最大值
有序树
无序树
森林 不通
3 小结
5.1_2树的常考性质
结点数=总度数 1
m叉树-每个结点最多只有m个孩子
m的树最多有mi-1次方个结点
5.2_十二叉树的定义和基本术语
1.二叉树的基本概念
或空二叉树
2 或者只有左子树，右子树 只有跟结点
特殊二叉树
满二叉树
完全二叉树
二叉排序树。
左树上所有结点的关键字都小于根节点的关键值
右子树上所有结点的关键字都大于根节点的关键值
平衡二叉树
左子树和右子树的深度只有不超过1
2.小结
5.2_2 二叉树的性质
5.2_3 二叉树的储存结构
1.二叉树的顺序存储
