数据结构之树（一）

本部分主要介绍树的相关知识，将分为3篇博文介绍。本文将着重介绍二叉树的一些基本概念，以及在其基础上的一些特殊的树形式：满二叉树、完全二叉树、线索二叉树、二叉排序树、平衡二叉树等。

树的基本概念

树的定义

树是$N（N \ge 0）$个结点的有限集合，$N=0$时，称为空树。$N$不为0时，树满足：

有且仅有一个特定的称为根结点的结点
当$N \ge 1$时，其余的结点可以分为$m（m>0）$个互不相交的有限集合$T_1,T_2,…,T_m$，其中每一个集合则是根结点的子树。

树是一种递归的数据结构，具有以下2个特点：

树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点
树中所有的结点可以有零个或者多个后继结点
$n$个结点的树中只有$n-1$条边

基本术语

结点的度：一个结点的子结点的个数
树的度：树中结点的最大度数
叶子结点：度为$0$的结点
结点深度：自顶向下逐层累加；结点高度：自底向上逐层累加
树的高度：树中结点的最大层数
路径：两结点之间所经过的结点序列构成；路径长度：路径上所有经过边的个数
森林：$m(m \ge 0)$棵不相交的树的集合。

把树的根结点删去就成了森林。

树的性质

树中的结点数等于所有结点的度数加1
度为$m$的树中第$i$层上至多有$m^{i-1}$个结点，$(i \ge 1)$
高度为$h$的$m$叉树至多有$\frac{m^h-1}{m-1}$个结点
具有$n$个结点的$m$叉树最小高度为$\lceil log_m^{(n(m-1)+1)} \rceil$

二叉树

定义根结点的编号为1

二叉树的定义

与树类似，二叉树也以递归的形式定义。二叉树是$n(n \ge 0)$个结点的有限集合：

或者为空二叉树，即$n=0$
或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树中每个结点至多有2棵子树，其结点次序是确定的，不是相对另一结点而言。

满二叉树

一棵高度为$h$，并且含有$2^h-1$个结点的二叉树称为满二叉树。(定义根结点的编号为1)起，
对于编号为$i$的结点：

若有双亲为$\lfloor i/2 \rfloor$
若有孩子结点，左孩子为$2i$，右孩子为$2i+1$

完全二叉树

高为$h$，有$n$个结点的二叉树，当且仅当每一个结点都与高为$h$的满二叉树中编号为$1到n$的结点一一对应时，称为完全二叉树。

完全二叉树的性质

若$i \le \lfloor \frac{n}{2} \rfloor$，结点$i$为分支结点，否则为叶子结点
如果有高度为1的结点，只可能有1个，且该结点只有左孩子
一旦出现某一结点$i$为叶子结点或者只有左孩子，则编号大于$i$的结点均为叶子结点
若$n$为奇数，每个分支结点都有左右孩子；若$n$为偶数，编号最大的分支结点$\frac{n}{2}$只有左孩子

下面是一张满二叉树和完全二叉树的对比图：

二叉排序树

一棵二叉树：

或者空树
或者左子树所有结点的值均小于根结点的值，右子树所有结点的值均大于根结点的值，左子树和右子树又各是一棵二叉排序树

平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1。

满二叉树 —–> 完全二叉树 —–> 平衡二叉树

二叉树的性质

非空二叉树的叶子结点（度为0）数等于度为2的结点数加1，即$N_0 = N_2 +1$
非空二叉树第$k$层至多有$2^k-1$个结点
结点$i$所在的层次深度为$\lfloor log_2^i \rfloor +1 $
具有$N$个$(N>0)$结点的完全二叉树的高度为$\lfloor log_2^N \rfloor +1$或$\lceil log_2^{(N+1)} \rceil$

二叉树的存储结构

顺序存储结构

二叉树的顺序存储结构就是用一组连续地址的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为$i$的结点元素存储在某个数组下标为$i-1$的分量中。（数组下标要从1开始）

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，因为树中结点的序号可以唯一的反映出结点之间的逻辑关系，这样既能最大的节省存储空间，又可以利用数组元素下标确定结点在二叉树中的位置，以及结点之间的关系。

如果对于一般的二叉树，也采用顺序存储的话，只能添加一些并不存在的空结点，这样才能满足我们上面所讲的逻辑关系。

如下图所示，其中$0$表示并不存在的空结点。

链式存储结构

由于顺序存储对空间利用效率低，因此一般二叉树都采用链式存储结构。链式结构是指用一个链表来存储一棵二叉树，二叉树中的每一个结点用链表的一个链结点来存储。在二叉树中，结点结构通常包括若干数据域及若干个指针域。二叉链表至少包含3个域：数据域data、左指针域lchild和右指针域rchild。如下图所示：

二叉树的链式存储结构描述如下：

typedef struct BiTNode{
    ElemType data;                    //数据域
    struct BiTNode *lchild,*rchild;   //左右孩子指针
}BiTNode,*BiTree;

在含有$n$个结点的二叉链表中含有$n+1$个空链域。如上图中含有5个结点的二叉链表有6个空链域。