第五章：二叉树（上）
OVERVIEW
一、二叉树定义
1.树的定义
2.树的基本概念
| 概念 | 说明 |
|---|---|
| 根结点root | 非空树中无前驱结点的结点 |
| 分支结点 | 度!=0则称为分支结点 |
| 内部结点 | 除开根节点以外的分支结点称为内部结点 |
| 叶子结点leaf | 度==0则称为叶子结点 |
| 树的度Degree | 树内各节点度的最大值 |
| 树的深度/高度Depth | 树中结点的最大层次level |
3.二叉树定义
二叉树的结构最简单、且具有强的规律性，若多叉树（普通树）不转化为二叉树，则运算很难实现。
4.二叉树形态
注意：虽然二叉树与树的概念不同，但是有关树的基本术语对二叉树都是适用的。
5.树与二叉树对比
二、二叉树ADT
三、二叉树性质
1.二叉树性质
注意：在二叉树的第
i层上至少有得有i个结点
注意：深度为
k的二叉树至少有k个结点
注意：运用这种分析方法可以分析很多二叉树的特点（从下向上、从上向下分析）
2.满二叉树性质
注意：性质4表明了完全二叉树结点数
n与完全二叉树深度k之间的关系
3.完全二叉树性质：
注意：性质5表明了完全二叉树双亲结点编号与孩子结点编号之间的关系
四、二叉树存储结构
1.顺序二叉树
2.链式二叉树
（1）二叉链表：
（2）三叉链表：
五、二叉树遍历
- 遍历定义：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均&仅被访问一次（又称周游）
- 遍历目的：得到树中所有结点的一个线性排列
- 遍历用途：遍历是数结构插入、删除、修改、查找和排序的前提，是二叉树一切运算的基础和核心
依次遍历二叉树中的3个组成部分，便是遍历了整个二叉树：
1.先根遍历
二叉链表实现先序遍历二叉树：
具体分析：
2.中根遍历
3.后根遍历
三种遍历算法的访问路径是相同的，只是访问结点的时机不相同：
4.遍历序列确定二叉树
- 若二叉树中各节点的值均不相同，则二叉树结点的先序遍历、中序遍历和后序遍历都是唯一的。
- 由二叉树的先序序列、中序遍历序列，or 由二叉树的中序遍历、后序遍历序列可以确定唯一的二叉树。
5.非递归遍历（栈）
非递归算法的关键：在中序遍历过某个结点的整个左子树之后，如何找到该结点的根以及其右子树？
基本思路：
- 建立一个栈
- 根结点进栈，遍历左子树
- 根结点出栈输出根结点，遍历右子树
6.层次遍历算法（队列）
对于一棵二叉树，从根节点开始按照从上到下、从左到右的顺序访问每一个结点（每个结点仅访问一次）：
算法思路：
- 将根节点入队
- 队列不为空时：从队列中出队一个结点*p，访问它
- 如果它有左孩子结点，将左孩子结点入队
- 如果它有右孩子结点，将右孩子结点入队
注意：二叉树的层次遍历其实也可以使用栈实现（比队列实现稍复杂）
六、二叉树遍历算法应用
1.二叉树的建立
按照先序遍历序列建立二叉树的二叉链表：
2.二叉树的复制
按照先序遍历的思想，复制二叉树：
3.二叉树深度计算
4.二叉树结点个数计算
5.二叉树叶子结点个数计算
七、线索二叉树
1.线索化引入
当使用二叉链表作为二叉树的存储结构时，可以很方便的找到某个结点的左右孩子，
但是一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点：
- 通过遍历寻找（增加时间负担）
- 再增设前驱、后继指针域（增加存储负担）
- 利用二叉树链表中的空指针域
如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱，
如果某个结点的右孩子为空，则将空的右孩子指针域改为指向其后继，
- 这种改变指向的指针被称为线索。
- 按某种遍历次序使二叉树变为线索二叉树的过程称为线索化（Threaded Binary Tree）
2.线索二叉树
