1. 第三章 树和二叉树
1.1. 树的基本概念
线性结构中的一个结点至多只有一个直接后继，而树形结构中一个结点可以有一个或多个直接后继。因此，树形结构可以表示更复杂的数据。
1.1.1. 树的概念
树是一类重要的数据接哦股，其定义如下：
树是n(n>=0)个结点的有限集合，一棵树满足以下两个条件：
- 当n=0时，称为空树；
- 当n>0时，有且仅有一个称为根的结点，除根结点外，其余结点分为m（m>=0)个互不相交的非空集合T1,T2,...，Tm，这些集合中的每一个都是一棵树，称为根的子树。
1.1.2. 树的相关术语
结点的度：树上任意结点所拥有的子树的数目称为该结点的度。
叶子：度为0的结点称为叶子或终端结点。
一个结点结点的子树的根称为该结点的孩子（或称子结点）。相应地该结点称为孩子的双亲（也称父结点）。
结点的层次：从根开始算起，根的层次为1，其余结点的层次为其双亲的层次加1。
树的高度：一棵树中所有结点层次数的最大值称为该树的高度或深度。
有序树：若书中各结点的子树从左到右时有次序的，不能互换，称为有序树。有序树中最左边子树的根称为第1个孩子，左边第i个子树的根称为第i个孩子。
无序树：若树中各结点的子树是无次序的，可以互换，则称为无序树。
树的基本运算：
- 求根
- 求双亲
- 求孩子
- 建树
- 剪枝
- 遍历
1.2. 二叉树
1.2.1. 二叉树的基本概念
二叉树（Binary Tree）是n（n>=）个元素的有限集合，该集合或者为空，或者由一个根及两颗互不相交的左子树和右子树组成，其中左子树和右子树也均为二叉树。
二叉树的任一结点都有两颗子树（它们中的任何一个都可以是空子树），并且这两颗子树之间有次序关系，即如果互换了位置就成为一颗不同的二叉树。
二叉树的基本运算：
- 初始化
- 求双亲
- 求左孩子
- 建二叉树
- 先序遍历
- 中序遍历
- 后序遍历
- 层次遍历
1.2.2. 二叉树的性质
性质一：二叉树第i（i>=1）层上至多有2^(i-1)个结点。
性质二：深度为k（k>=1）的二叉树至多有2^(k)-1个结点。
性质三：对任何一棵二叉树，若度数为0的结点（叶结点）个数为n0，度数为2的结点个数为n2，则n0=n2+1。
满二叉树：深度为k（k>=1）且有2^(k)-1个结点的二叉树称为满二叉树。
完全二叉树：如果对满二叉树丛上到下，从左到右的顺序编号，并在最下面一层删去部分结点（删除最后一层仍有结点），如果删除的这些结点的编号是连续的且删除的结点中含有最大编号的结点，那么这颗二叉树就是完全二叉树。
完全二叉树的性质：
性质四：含有n个结点的完全二叉树的深度为log2^(n)+1。
性质五：如果将一棵有n个结点的完全二叉树按层编号，按层编号是指：将一棵二叉树中的所有n个结点按从第一层到最大层，每层从左到右的顺序依次标记为1，2，...，n。则对任一编号为i（1<=i<=n）的结点A有：
- 若i=1，则结点A是根；若i>1，则A的双亲Parent（A）的编号为i/2；
- 若2i>n，则结点A既无左孩子，也无右孩子；否则A的左孩子的编号为2i；
- 若2i+1>n，则结点A无右孩子；否则，A的右孩子的编号为2i+1。
1.3. 二叉树的存储结构
二叉树通常有两类存储结构：顺序存储结构和链式存储结构。
1.3.1. 二叉树的顺序存储结构
二叉树的顺序存储结构可以用一维数组来实现，二叉树上的结点按某种次序分别存入该数组的各个单元中。
1.3.2. 二叉树的链式存储结构
二叉树有不同的链式存储结构，其中最常用的是二叉链表与三叉链表。
二叉链表的类型定义如下：
typedef struct btnode
{
DataType data;
struct btnnode *lchild, *rchild;
} *BinTree;
三叉链表的类型定义如下：
typedef struct ttnode
{
DataType data;
struct ttnode *lchild, *parent, *rchild;
} * TBinTree;
1.4. 二叉树的遍历
1.4.1. 二叉树遍历的递归实现
二叉树的遍历是指按某种次序访问二叉树的的所有结点，使每个结点被访问一次且仅被访问一次。
先序遍历
若被遍历的二叉树为空，执行空操作；否则，依次执行下列操作；
- 访问根结点；
- 先序遍历左子树；
- 先序遍历右子树。
void preorder(BinTree bt)
{
if(bt!=NULL)
{
visit(bt);
preorder(bt->lchild);
preorder(bt->rchild);
}
}
中序遍历
若被遍历的二叉树为空，执行空操作；否则，依次执行下列操作：
- 中序遍历左子树；
- 访问根结点；
- 中序遍历右子树。
void inorder(BinTree bt)
{
if (bt!=NULL)
{
inorder(bt->lchild);
visit(bt);
inorder(bt->rchild);
}
}
后序遍历
若被遍历的二叉树为空，执行空操作；否则，依次执行下列操作：
- 后序遍历左子树；
- 后序遍历右子树；
- 访问根结点。
void posterder(BinTree bt)
{
if (bt!=NULL)
{
posterder(bt->lchild);
posterder(bt->rchild);
visit(bt);
}
}
层次遍历
所谓二叉树的层次遍历，是指从二叉树的根结点的这一层开始，逐层向下遍历，在每一层上按从左到右的顺序对结点逐个访问。
1.5. 树和森林
1.5.1. 树的存储结构
孩子链表表示法
孩子链表表示法是树的一种链式存储结构。它的主体是一个数组元素个数和树中结点个数相同的一维数组。树上的一个结点x以及该结点的所有孩子结点组成一个带头结点的单链表，单链表的头结点含有两个域：数据域和指针域。其中，数据域用于存储结点x中的数据元素，指针域用于存储指向x第一个孩子结点的指针。
孩子兄弟链表表示法
存储时每个结点除了数据域外，还有指向该结点的第一个孩子和下一个兄弟结点的指针。
双亲表示法
双亲表示法由一个一维数组构成。数组的每个分量包含两个域：数据域和双亲域。数组域用于存储树上一个结点中数据元素，双亲域用于存储本结点的双亲结点在数组中的序号（下标值）。
1.5.2. 树、森林与二叉树的关系
树转换成二叉树
任何一棵树可唯一地与一棵二叉树对应。相应地，一棵二叉树也唯一地对应一棵树，即树与二叉树可以互相转换。
将树转换成二叉树的方法如下：
- 将所有兄弟结点连接起来；
- 保留第一个兄弟结点与父结点的连接，断开其他兄弟结点与父结点的连接，然后以根结点为轴心按顺时针的方向旋转45度角。
森林转换成二叉树
- 将每棵树转换成相应的二叉树；
- 将1中得到的各棵二叉树的根结点看作是兄弟连接起来。
二叉树转换成森林
1.5.3. 树和森林的遍历
先序遍历
后序遍历
层次遍历
1.5.4. 森林的遍历
先序遍历
中序遍历
1.6. 判定树和哈夫曼树
1.7. 练习
1.7.1. 先序遍历ABCDEF，中序遍历CBAEDF，后序遍历结果为：
CBEFDA
a
b d
c e f
1.7.2. 中序遍历BACDEFGH，后序遍历BCAEDGHF，建立该二叉树
F
E H
A D B C G