Chapter 05 二叉树
1. 概念¶
- 度数即有多少个孩子.
- 层数从 0 开始.
1.1 满二叉树¶
如果一棵二叉树没有 1 度节点, 则是满二叉树.
1.2 完全二叉树¶
只有最下面一层没有填满.
最下面一层的结点集中分布在最左边, 连续的位置上.
特点:
- 叶结点只有可能在最下面两层出现
- 路径长度和是相同结点数目的二叉树中最小的
1.3 扩充二叉树¶
当二叉树节点出现空指针时，就增加一个特殊结点——空树叶
度为1的结点，在它下面增加1个空树叶
度为0的树叶，在它下面增加2个空树叶
扩充的二叉树是满二叉树，新增加空树叶(外部结点L)的个数等于原来二叉树结点个数(内部结点N)加1
这里的 L 和 N 指的是相对扩充后的二叉树而言的
证明: 利用 \(n_0=n_2+1\), 新增加的节点数为 \(2n_0+n_1=n_0+n_1+n_2+1\)
\(n_0=n_2+1\) 的证明:
这里第一个计算方式显然, 第二个计算方式是利用计算孩子总数加上根节点得到. 两式相减即得.
2. 二叉树的主要性质¶
(分支结点是度数大于0的节点, 满二叉树度数要么是0, 要么是2)
3. 二叉树的周游¶
遍历（Traversal）,也称“周游”
- 按照一定的次序（规律）系统地访问二叉树中的结点
- 每个结点都正好被访问(输出，修改节点信息等) 一次
二叉树的线性化
- 实质是把二叉树的结点放入一个线性序列的过程
- “非线性”->“线性”的过程
线性化方式，是对非线性结构的访问方式
- 深度优先：一棵一棵子树的纵深遍历
- 广度优先：一层一层的自左而右的逐层横向遍历
Warning
已知先序序列和中序序列可以唯一确定一棵二叉树, 已知后序序列和中序序列可以唯一确定一棵二叉树, 但是已知先序和后序序列不能唯一确定一棵二叉树. (先序和后序无法区分左右)
4. 非递归遍历二叉树¶
4.1 前序¶
4.2 中序¶
4.3 后序¶
5. 二叉树的存储结构¶
5.1 动态链式存储¶
各结点随机存储在内存空间，结点之间关系用指针表示。
除存储结点本身数据外，每个结点再设置两个指针字段left和right，分别指向左孩子和右孩子；
子女为空时指针为空指针
这种存储结构称为二叉链表表示法
三叉链表
除 left 和 right 指针外，每个结点再增加一个指向父节点的指针 parent，形成“三叉链表”
提供了“向上”访问的能力
5.2 静态数组存储(完全二叉树)¶
6. 二叉搜索树¶
二叉搜索树（BST），也称二叉排序树
- 或者是一颗空树；
- 或者是具有下列性质的二叉树：
- 对于任何一个结点，设其值为K，则该结点的左子树(若不空)的任意一个结点的值都小于K；
- 该结点的右子树(若不空)的任意一个结点的值都大于K；
- 而且它的左右子树也分别为二叉搜索树
二叉搜索树的性质
- 按照中序周游将各结点打印出来，将得到由小到大的排列
- 树中结点的值唯一
7. 堆与优先队列¶
7.1 堆的性质¶
- 堆中储存的数据局部有序（与BST树不同）
- 结点与其子女值之间存在大小比较关系
- 两种堆（最大、最小）
- 兄弟之间没有限定大小关系
- 堆不唯一
- 是一棵可用数组表示的完全二叉树