文章目录
- 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开始 结点的高度 从下往上数 结点的度 有几个分支 树的度 每个结点的最大值
有序树 无序树 森林 不通
5.1_2树的常考性质
结点数=总度数 1 m叉树-每个结点最多只有m个孩子 m的树最多有mi-1次方个结点
5.2_十二叉树的定义和基本术语
或空二叉树 2 或者只有左子树，右子树 只有跟结点
特殊二叉树 满二叉树 完全二叉树 二叉排序树。 左树上所有结点的关键字都小于根节点的关键值 右子树上所有结点的关键字都大于根节点的关键值
平衡二叉树 左子树和右子树的深度只有不超过1
5.2_2 二叉树的性质
5.2_3 二叉树的储存结构
![插入图片描述](https://img-blog.csdnimg.cn/b04821ce64e64f0ebea71b1d60afa2a8.png
5.3_1 二叉树的先、中、后历
先序遍历：根左右 NLR 前缀表达式 中序遍历： 左跟右LNR 中缀表达式 需要加界限符 后序遍历：左右跟 LRN 后缀表达式
5.3_2 二叉树的层次遍历
5.3_3 由遍历序列构造二叉树
只有一个遍历序列不能唯一确定一棵二叉树
如果没有中序遍历，二叉树是唯一无法确认的。
5.3_4 二叉树的概念
线索二叉树用于找结点前驱后继，左结点指向前驱，右结点指向后继
5.3_5 二叉树的线索化
5.3_6 在线索二叉树中寻找前驱和后驱
找指定结点p前驱，p的左子树中最右下结点 找指定结点p后继，p右子树最左边的一棵
找指定结点p前驱，找不到前驱 找指定结点p后继，p右子树最左边的一棵
找到指定点p前驱 找指定结点p后继，找不到
5.4_1 树的存储结构
5.4_2 树木和森林的遍历
树的先根遍历二叉树对应的先序遍历 森林的先序遍历对应二叉树的先序遍历
5.5_1 哈夫曼树
5.5_2 并查集
5.5_3 并进一步优化收集