数据结构 - 树

2019-05-01 本文已影响0人 Longshihua

树的定义

树（Tree）是n（n≥0）个结点的有限集。n=0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当n＞1时，其余结点可分为m（m＞0）个互不相交的有限集T₁、T₂、……、T_m，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

108import.png

下图中子树T₁和子树T₂就是根结点A的子树。D、G、H、I组成的树又是B为根结点的子树，E、J组成的树是以C为根结点的子树

109import.png

树的定义还需要强调两点：

1、n>0时根结点是唯一的，不可能存在多个根结点，
2、m>0时，子树的个数没有限制，但它们一定是互不相交的。下图中的两个结构就不符合树的定义，因为它们都有相交的子树

110import.png

结点分类

树的结点包含一个数据元素及若干指向其子树的分支。

结点拥有的子树数称为结点的度（De-gree）；
度为0的结点称为叶结点（Leaf）或终端结点；
度不为0的结点称为非终端结点或分支结点；
除根结点之外，分支结点也称为内部结点；
树的度是树内各结点的度的最大值。

111import.png

上图这棵树，结点的度的最大值是结点D的度，为3，所以树的度也为3

结点间关系

结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲（Parent），同一个双亲的孩子之间互称兄弟（Sibling）。结点的祖先是从根到该结点所经分支上的所有结点。以某结点为根的子树中的任一结点都称为该结点的子孙。

112import.png

如图中，对于结点H而言，D、B、A都是它的祖先。对于结点B而言，B的子孙有D、G、H、I

树的其他相关概念

结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树就在第l+1层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度

113import.png

如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

森林（Forest）是m（m≥0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林

线性表与树的结构：

114import.png

树的抽象数据类型

相对于线性结构，树的操作就完全不同了，常用的一些基本操作如下

ADT 树 (tree)
Data:
      树是由一个根结点和若干棵子数构成.树中结点具有相同数据类型及层次关系
 Operation:
        InitTree (*T):构成空树T
        DestroyTree(*T):销毁树T
        CreateTree(*T,definition):按definition中给出的树的定义来构造树
        ClearTree(*T):若树T存在,则将树T请为空树
        TreeEmpty(T):若T为空树,返回true,否则返回false
        TreeDepth(T):返回T的深度
        Root(T):返回T的根结点
        Value(T,cur_e):cur_e是树T中一个结点,返回此结点的值
        Assign(T,cur_e,value):给树T的结点cur_e赋值为value
        Parent(T,cur_e):若cur_e是树T的非根结点,返回它的双亲,否则返回空
        LeftChild(T,cur_e):若cur_e是树T的非叶节点,则返回它的最左孩子,否则返回空
        RightSibling(T,cur_e):若cur_e有右兄弟,则返回他的右兄弟,否则返回空
        InsertChild(*T,*p,i,c):其中p指向树T的某个结点,T为所指结点p的度加上1,非空树c与T
                               不相交,操作结果为插入c为树T中p所指结点的第i棵子树
        DeleteChile(*T,*p,i):其中p指向树T的某个结点,i为所指结点p的度,
                             操作结果为删除T中p所指结点的第i棵子树
endADT

树的存储结构

3种表示法：双亲表示法、孩子表示法、孩子兄弟表示法

双亲表示法

假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。也就是说每个结点除了知道自己是谁以外，还知道它的双亲在哪里，结构如下所示

屏幕快照 2018-09-07 下午5.58.38.png

data	parent
数据域，存储结点的数据信息	指针域，存储该结点的双亲在数组中的下标

结点结构定义代码

//树的双亲表示法结点结构定义
#define MAX_TREE_SIZE 100
typedef int TElemType;   //树结点的数据类型,目前暂定义为整型
typedef struct PTNode   //结点结构
{
     TElemType data;     //结点数据
     int parent;         //双亲位置
}PTNode;
typedef struct                 //树结构
{
     PTNode nodes[MAX_TREE_SIZE];     //结点数组
     int r,n;                     //根的位置和结点数
}PTree;

由于根结点是没有双亲的,约定根结点的位置域设置为-1,这就意味着所有的结点都存有它双亲的结点：

树结构

屏幕快照 2018-09-07 下午7.05.00.png

树双亲表示

下标	data	parent
0	A	-1
1	B	0
2	C	0
3	D	1
4	E	2
5	F	2
6	G	3
7	H	3
8	I	3
9	J	4

这样进行存储，我们就可以根据结点的parent指针很容易找到它的双亲结点,所用时间复杂度为O(1),知道parent为-1,表示找到了树结点的根.如果要知道结点的孩子是什么,就必须遍历整个结构才行

改进：

增加一个结点最左边孩子的域，叫长子域，如果没有孩子的结点,这个长子域就设置为-1

下标	data	parent	firstchild
0	A	-1	1
1	B	0	3
2	C	0	4
3	D	1	6
4	E	2	9
5	F	2	-1
6	G	3	-1
7	H	3	-1
8	I	3	-1
9	J	4	-1

对于有0个或者1个孩子结点来说，这样的结构是解决来要找结点孩子的问题，甚至是有2个孩子，长子知道了，另外一个当然就是次子了。

另外一个场景，我们很关心兄弟之间的关系，双亲表示法无法体现这样的关系，那么我们应该怎么办？嗯，可以增加一个右兄弟来体现兄弟关系，也是就说，每一个结点如果存在右兄弟，则记录右兄弟的下标。同样的，如果右兄弟不存在，则赋值为-1.

下标	data	parent	rightsib
0	A	-1	-1
1	B	0	2
2	C	0	-1
3	D	1	-1
4	E	2	5
5	F	2	-1
6	G	3	7
7	H	3	8
8	I	3	-1
9	J	4	-1

但是如果结点的孩子很多，超过来2个，我们又要关注结点的双亲，又要关注结点的孩子，还要关注结点的兄弟，而且对时间遍历要求还比较高，那么可以进行扩展

孩子表示法

由于树中每个结点可能有多棵子树,可以考虑多重链表,即每个结点有多个指针域，其中每个指针指向一棵子数的根结点,这种方法叫多重链表表示法。不过树的每个结点的度，也就是它的孩子个数是不同的，所以可以设计两种方案来解决。

方案一

一种是指针域的个数等于树的度，树的度是树各个结点度的最大值，其结构如下：

851071-9aff0ffd7f66af3b.png

其中data是数据域，child1到childd是指针域，用来指向该结点的孩子结点

屏幕快照 2018-09-09 上午10.54.53.png

这种方法对于树中各结点的都相差很大时，显然是很浪费空间的，它的指针域是空的。如果树的各结点相差较小时，那就意味着开辟的空间被充分利用了，这时存储结构的缺点反而变成了优点。

既然很多指针域是空的，为什么不按需分配呢？也是有了第二种方案。

方案二

第二种方案每个结点指针域的个数等于该结点的度，我们专门取一个位置来存储结点指针域的个数，其结构如下：

屏幕快照 2018-09-09 上午10.46.24.png

其中data是数据域，degree是度，也就是该结点的孩子结点个数，child1到childd是指针域，用来指向该结点的孩子结点。比如：下图树的表现形式

4010043-024ebcd864341601.png

屏幕快照 2018-09-09 上午10.45.08.png

这种方法克服了浪费空间的缺点，对空间利用率是很高了，但是由于链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗。

那么能否有更好的办法，既可以减少了空指针的浪费又能使结点结构相同。仔细观察，我们为了遍历整棵树，把每个结点放到一个顺序存储结构的数组中是合理的，但每个结点的孩子有多少是不确定的，所以我们再对每个结点的孩子建立一个单链表体现它们的关系，这就是孩子表示法

孩子表示法：把每个结点的孩子结点排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点则此链表为空.然后n个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中，如下图

屏幕快照 2018-09-09 上午11.07.09.png

为此设置了两种结点结构：一个是孩子链表的孩子结点

屏幕快照 2018-09-09 上午11.11.32.png

其中child是数据域，用来存储某个结点在表头数组中的下标，next是指针域，用来存储指向某结点的下一个孩子结点的指针。

另一个是表头数组的表头结点

屏幕快照 2018-09-09 上午11.11.37.png

其中data是数据域，存储某结点的数据信息，firstchild是头指针域，存储该结点的孩子链表的头指针

孩子表示法结构定义

/*树的孩子表示法结构定义*/
#define MAX_TREE_SIZE 100
typedef int TElemType;
typedef struct CTNode //孩子结点
{
    int child;
    struct CTNode *next;
} *ChildPtr;
typedef  struct //表头结构
{
    TElemType data;
    ChildPtr firstchild;
}CTBox;
typedef struct //树结构
{
    CTBox nodes[MAX_TREE_SIZE]; //结点数组
    int r, n;   //根的位置和结点数
}CTree;

这样的结构对于要查找某个结点的某个孩子,或者找某结点的兄弟,只需要查找这个结点的孩子单链表即可.但要知道某结点的双亲是谁,比较麻烦,需要遍历整棵树才行。

但是，这也存在问题，如何知道某个结点的双亲呢？比较麻烦，需要调整整棵树遍历才行，但是我们可以把双亲表示法和孩子表示法综合一下，如下图

851071-ef0cbb402f488d56.png

这就是双亲孩子表示法，可以说是孩子表示法的改进

孩子兄弟表示法

任意一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的,因此,设置两个指针,分别指向该结点的第一个孩子和此结点的兄弟

结点结构

851071-2d9ad2191c3d90e8.png

结构定义代码如下

/* 树的孩子兄弟表示法结构定义 */
typedef struct CSNode
{
    TElemType data;
    struct CSNode *firstchild, *rightsib;
} CSNode, *CSTree;

方法实现效果图如下

115import.png

这种表示法，查找某个结点的某个孩子只需要通过fistchild找到此结点的长子，再通过长子结点的rightsib找到它的二弟，接着一直下去，直到找到具体的孩子。

这个表示法的最大好处是把一棵复杂的树变成了一棵二叉树

屏幕快照 2018-09-09 上午11.29.40.png

这样就可以充分利用二叉树的特性和算法来处理这棵树了。

二叉树

二叉树的定义

二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的,分别称为根结点的左子树和右子树的二叉树组成。

屏幕快照 2018-09-09 上午11.33.16.png

上图就是一个二叉树

二叉树的特点

1、每个结点最多有两棵子树,所以二叉树不存在度大于2的结点，注意：不是两棵子树，而是最多有。没有子树或者有一颗子树都是可以的
2、左子树和右子树是有顺序的,次序不能任意颠倒。
3、即使树中某结点只有一棵子树,也要区分左子树和右子树的

851071-44a8eb0d9731cb36.png

二叉树的五种基本形态：

1、空二叉树
2、只有一个根结点
3、根结点只有左子树
4、根结点只有右子树
5、树既有左子树也有右子树

只从形态上考虑，三个结点的树只有两种情况，图中有两层的树1和有三层的后四种的任意一种，对于二叉树来说，由于要区分左右，就演变成五种形态，树2、树3、树4和树5分别代表不同的二叉树

屏幕快照 2018-09-09 上午11.39.10.png

特殊二叉树

斜树

斜树一定是斜的,所有的结点都只有左子树的二叉树叫左斜树.所有的二叉树只有右子数的树叉树叫右斜树.两者统称为斜树。斜树每一层都只有一个结点,结点的个数跟二叉树的深度相同.

注意：线性表就是特殊的二叉树

满二叉树

在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树

屏幕快照 2018-09-09 上午11.41.49.png

满二叉树的特点:

1、叶子只能出现在最下一层,出现在其他层就不可能达到平衡
2、非叶子结点的度一定是2
3、在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多

完全二叉树

对一棵具有n个结点的二叉树按层序编号,如果编号为i(1<= i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树树完全二叉树

851071-14d589a906b5540d.png

上图尽管不是满二叉树，但是编号是连续的，所以它是完全二叉树。

注意：

首先从字面上要区分，“完全”和“满”的差异，满二叉树一定是完全二叉树,而完全二叉树不一定是满二叉树

另外，完全二叉树的所有结点与同样深度的满二叉树，它们按层序编号相同的结点，是一一对应的。关键词是按层序编号，树1因为5结点没有左子树，却有右子树，使得按层序编号的第10个编号空档。树2由于3结点没有子树，使得6、7编号的位置空档。树3因为5编号下没有子树造成第10和第11位置空档。所以这些都不是完全二叉树。

851071-ea935c12020d1891.png

完全二叉树的特点:

1、叶子结点只能出现在最下两层
2、最下层的叶子一定集中在左部连续位置
3、倒数两层,若有叶子结点,一定都在右部连续位置
4、若结点度为1,则该结点只有左孩子,即不存在只有右子树的情况
5、同样结点树的二叉树,完全二叉树的深度最小

二叉树的性质

性质1：在二叉树的第i层上至多有2^i-1个结点（ $i \geq 1$ ）

性质2：深度为k的二叉树至多有2^k-1个结点

性质3：对任何二叉树T，如果其终端结点数(叶子结点数)为n₀，度为2的结点数为n₂，则n₀=n₂+1

性质4：具有n个结点的完全二叉树的深度为|log₂n|+1(|n|表示不大于n的最大整数)

性质5：如果对一棵有n个结点的完全二叉树（其深度|log₂n|+1）的结点按层序编码（从第1层到第|log₂n|+1层，每层从左到右），对任一结点i（1 $\leq i\leq n$ ）有：

1、如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点|i/2|
2、如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i
3、如果2i+1>n，则结点i无左右孩子；否则其右孩子是结点2i+1

通过下图来理解该性质

屏幕快照 2018-09-27 上午9.38.03.png

对于第一条来说是很明显的，i=1时就是根结点，比如结点7，它的双亲就是|7/2|=3，结点9，它的双亲就是|9/2|=4

第二条，比如结点6，因为2x6=12超过结点总数10，所以结点6无左孩子，它是叶子结点。同样，对于结点5，因为2x5=10正好是结点总数10，所以它的左孩子是结点10

第三条，比如结点5，因为2x5+1=11，大于结点总数10，所以它无右孩子，而结点3，因为2x3+1=7小于10，所以它的右孩子是结点7.

二叉树的存储结构

二叉树的顺序存储

二叉树的顺序存储结构就是用一维数组存储二叉树的结点，并且结点的存储位置也就是数组的下标，能够体现结点之间的逻辑关系。

完全二叉树的顺序存储，如下图

屏幕快照 2018-09-27 上午9.44.23.png

将这棵树存储到数组中，相应的下标对应其同样的位置，如下图

屏幕快照 2018-09-27 上午9.45.50.png

这下可以看出完全二叉树的优越性来，由于它定义的严格，所以用顺序存储结构也可以表现二叉树的结构来

当然对于一般的二叉树，尽管层序编号不能反映逻辑关系，但是可以将其按完全二叉树编号，只不过，把不存在的结点设置为“^”而已。注意：浅色结点表示不存在

屏幕快照 2018-09-27 上午9.47.51.png

考虑一种极端情况，一棵深度为k的右斜树，它只有k个结点，却需要分配2^k -1个存储单元，这显然是对存储空间的浪费，如下图，所以顺序存储结构一般只用于完全二叉树

屏幕快照 2018-09-27 上午9.50.50.png

二叉链表

既然顺序存储适用性不强，我们就需要考虑使用链式存储结构，二叉树每个结点最多两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。结点结构图如下

屏幕快照 2018-09-27 上午9.53.27.png

其中data是数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针

二叉链表的结点结构定义

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

结构示意图如下

屏幕快照 2018-09-27 上午9.58.03.png

如果有需要，还可以再增加一个指向其双亲的指针域，那样就称为三叉链表

遍历二叉树

二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中所有结点，使得每个结点都被访问一次且仅被访问一次

二叉树的遍历方法

前序遍历

若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如下图，遍历的顺序为ABDGHCEIF

屏幕快照 2018-09-27 下午6.56.11.png

中序遍历

若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如下图，遍历的顺序为：GDHBAEICF

屏幕快照 2018-09-27 下午7.14.18.png

后序遍历

若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点，如下图，遍历的顺序为：

屏幕快照 2018-09-27 下午7.13.25.png

层级遍历

若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如下图

屏幕快照 2018-09-27 下午7.16.37.png

前序遍历算法

二叉树的定义是用递归的方式，所以，实现遍历算法也可以采用递归，而且极其简单。

void preOrderTraverse(BiTree T)
{
    if (T == NULL)
    return;
    printf("%c", T->data); // 显示结点数据
    preOrderTraverse(T->lchild); // 再先遍历左子树
    preOrderTraverse(T->rchild); // 最后遍历右子树
}

假设我们有下图这样一棵二叉树，该树已经用二叉树链表结构存储在内存当中

屏幕快照 2018-09-28 上午9.02.37.png

当调用preOrderTraverse(T)函数时，看看程序是如何运行的

1、调用preOrderTraverse(T)，T根结点不为null，所以执行printf，打印字母A，如下图

屏幕快照 2018-09-28 上午9.32.43.png

2、调用preOrderTraverse(T->lchild); 访问结点A的左孩子，不为null，执行printf打印字母B，如下图

屏幕快照 2018-09-28 上午9.34.46.png

3、此时再次调用preOrderTraverse(T->lchild);，访问结点B的左孩子，执行printf打印字母D

屏幕快照 2018-09-28 上午9.35.42.png

4、再次递归调用preOrderTraverse(T->lchild);，访问结点D的左孩子，执行printf打印字母H

屏幕快照 2018-09-28 上午9.37.04.png

5、再次递归调用preOrderTraverse(T->lchild);访问结点H的左孩子，此时结点H无左孩子，所以T == NULL，返回此函数，此时递归调用preOrderTraverse(T->rchild);，访问结点H的右孩子，执行printf打印字母K

屏幕快照 2018-09-28 上午9.39.02.png

6、再次递归调用preOrderTraverse(T->lchild)，访问结点K的左孩子，结点K无左孩子，返回，继续调用preOrderTraverse(T->rchild);，，访问结点K的右孩子，也是null，返回。

也是此函数执行完毕，返回上一级递归的函数（即结点H时的函数），也执行完毕，返回到打印结点D时的函数，调用preOrderTraverse(T->rchild);，访问结点D的右孩子，不存在，返回到结点B，调用preOrderTraverse(T->rchild);，找到了结点E，打印字母E

屏幕快照 2018-09-28 上午9.43.59.png

7、由于结点E没有左右孩子，返回打印结点B是的递归函数，递归执行完毕，返回到最初的preOrderTraverse，然后调用preOrderTraverse(T->rchild)，访问结点A的右孩子，打印字母C

屏幕快照 2018-09-28 上午9.45.35.png

8、之后类似签名的递归步骤，依次打印F、I、G 、J

综上，前序遍历这棵二叉树的结点顺序是：ABDHKECFIGJ

中序遍历算法

它和前序遍历算法仅仅只是代码的顺序上差异，换句话说是把调用左孩子的递归函数提前了。就这么简单。

void inOrderTraverse(BiTree T)
{
    if (T==NULL)
    return;
    inOrderTraverse(T->lchild); //中序遍历左子树
    printf("%c", T->data); // 显示结点数据
    inOrderTraverse(T->rchild); //最后遍历右子树
}

屏幕快照 2018-09-28 上午9.54.02.png

同样是上面的这棵二叉树，中序遍历的结果是：HKDBEAIFCGJ

后续遍历算法

void postOrderTraverse(BiTree T)
{
    if (T==NULL)
    return;
    postOrderTraverse(T->lchild); //先后续变量左子树
    postOrderTraverse(T->rchild); //再后续遍历右子树
    printf("%c",T->data); //显示结点数据
}

同样是上图，后序遍历结点的顺序为：KHDEBIFJGCA

推倒遍历结果

有一种题目为了考查你对二叉树遍历的掌握程度。比如：已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，请问这棵二叉树的后序遍历结果是多少？

三种遍历都是从根结点开始，前序遍历是先打印在递归左和右，所以前序遍历序列ABCDEF，第一个字母是A被打印出来，说明A是根结点的数据。

再由中序遍历序列CBAEDF，可以知道C和B是A的左子树的结点，E、D、F是右子树的结点。可以简单得到如下关系图

屏幕快照 2018-09-28 上午10.05.04.png

然后在看前序中的C、B，它的顺序是ABCDEF，先B再C，所以肯定B是A的左孩子，C是B的孩子，但是不能确定是左孩子还是右孩子，需要看中序CBAEDF，先打印C再打印B，这就说明C是B的左孩子

屏幕快照 2018-09-28 上午10.08.53.png

再看前序中的E、D、F，它的顺序是ABCDEF，意味着D是A的右孩子，E、F是D的子孙，可能是孩子也可能是孙子，所以需要配合中序CBAEDF来看，很明显先打印E，可以确定E是D的左孩子，F是D的右孩子，最终得到的二叉树如下

屏幕快照 2018-09-28 上午10.12.27.png

从这里可以得到两个性质：

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树
已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树

但是要注意：已知前序和后序遍历，是不能确定一棵二叉树的

二叉树的建立

如果要在内存中建立如图6-9-1左图这样的数，为了能够让每个结点确认是否有左右孩子，我们对它进行了扩展，编程图6-9-1右图的样子，也就是将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值，比如：“#”。我们称这种处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树。

比如图6-9-1的前序遍历序列就为AB#D##C##

屏幕快照 2018-09-30 上午8.46.15.png

生成二叉树，假设二叉树的结点均为一个字符，我们把刚才前序遍历序列AB#D##C##用键盘挨个输入。实现算法如下：

// 按前序输入二叉树中的结点的值（一个字符）
// #表示空树，构造二叉链表表示二叉树T
void createBitree(BiTree *T)
{
    TElemType ch;
    scanf("%c", &ch);
    if (ch=='#')
    {
        *T = NULL;
    } else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if (!*T)
            exit(OVERFLOW);
        (*T)->data = ch; // 生成根结点
        createBitree(&(*T)->lchild); // 构造左子树
        createBitree(&(*T)->rchild); //构造右子树
    }
}

其实建立二叉树也是利用递归的原理。只不过在原来应该是打印结点的地方，改成了生成结点、给结点赋值的操作而已。

当然也可以使用中序或后序遍历的方式实现二叉树的建立，只不过代码里面生成结点和构造左右子树的代码顺序交换一下。另外，输入的字符也要做相应的修改。比如上图的扩展二叉树的中序遍历字符串应该为#B#D#A#C# ，而后序字符串应该为###DB##CA

线索二叉树

线索二叉树原理

我们提倡节约型社会，一切都应该节约为本，对待我们的程序当然也不例外，能不浪费的时间或空间，都应该考虑节省。看看下图，会发现指针域并没有都充分的利用，有许许多多的"^”，也就是空指针域，这实在不是好现象，应该要想办法利用起来

屏幕快照 2018-09-30 上午9.17.51.png

首先我们要来看看这空指针有多少个？对于一个有n个结点的二叉链表，每个结点有指向左右孩子的两个指针域，所以一共有2n个指针域，而n的结点的二叉树一共有n-1条分支线数，也就是说，其实是存在2n-(n-1)=n+1个空指针域。比如上图有10个结点，空指针域为11，这些空间不存储任何事务，白白浪费着内存的资源

另一方面，我们在做遍历时，比如对上图做中序遍历，得到HDIBJEAFCG这样的字符序列，遍历过后我们可以知道，结点I的前驱是D，后继是B，结点F的前驱是A后继是C.也就是说，我们可以很清楚的知道任意一个结点，它的前驱和后继是哪一个

可是这是建立在已经遍历过的基础上，在二叉链表上，我们只能知道每个结点指向其左右孩子结点的地址，而不知道某个结点的前驱是谁，后继是谁。要想知道，必须遍历一次。以后每次需要知道时，都需要先遍历一次，为什么不考虑在创建时就记住这些前驱和后继呢。那将是多大的时间上的节省

综合上面两个角度的分析，我们可以考虑利用那些空地址，存放指向结点在某种遍历次序下的前驱和后继结点的地址，我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树

如下图，我们把这棵二叉树进行中序遍历后，将所有的空指针域中的rchild，改为指向它的后继结点。于是我们就可以通过指针知道H的后继是D,I的后继是B J的后继是E, E的后继是A,F的后继是C, G的后继是NULL。此时公有6个空指针域被利用

屏幕快照 2018-09-30 上午9.51.05.png

再看下图，我们将这棵二叉树的所有空指针中的lchild，改为指向当前结点的前驱。因此 H的前驱是NULL，I的前驱是D，J的前驱是B，F的前驱是A，G 的前驱是C ，一共5个空指针域被利用，正好和上面的后继加起来11个

屏幕快照 2018-09-30 上午9.58.35.png

下图中（空心箭头实线为前驱，虚线黑箭头为后继），更容易看出，其实线索二叉树等于是把一棵二叉树变成了一个双向链表，这样对我们的插入删除结点，查找某个结点都带来了方便，所以我们对二叉树以某种次序遍历使其变成线索二叉树的过程叫做线索化。

不过好事总是多磨，问题并没有彻底解决，我们如何知道某一结点的lchild是指向它的左孩子还是指向前驱？rchild是指向右孩子还是指向后继？比如E结点的lchild是指向它的左孩子J,而rchild却是指向它的后继A。显然我们在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继上是需要一个区分标志的。

因此，我们在每个结点再增设两个标志域ltag和rtag，注意ltag和rtag只是存放0或1数字的布尔值变量，其占用的内存空间要小于lchild和rchild的指针变量，结点结构如下图

屏幕快照 2018-09-30 上午10.07.46.png

其中：

ltag为0时指向该结点的左孩子，为1时指向该结点的前驱
rtag为0时指向该结点的右孩子，为1时指向该结点的后继
因此对于可以修改二叉链表图为如下

屏幕快照 2018-09-30 上午10.10.25.png

线索二叉树结构实现

二叉树的线索存储结构定义如下：

typedef enum {
    Link,
    Thread
} PointerTag;

// Link==0表示指向左右孩子指针
// Thread==1表示指向前驱或后继的线索

typedef struct BiThrNode
{
    TElemType data; //结点数据
    struct BiThrNode *lchild, *rchild; //左右孩子
    PointerTag LTag;
    PointerTag RTag; // 左右标志
} BiThrNode, *BiThrTree;

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历二叉树才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程

中序遍历线索化的递归函数代码

BiThrTree pre; //全局变量，始终指向刚刚访问过的结点
// 中序遍历进行中序线索化
void inThreading(BiThrTree p)
{
    if (p)
    {
        inThreading(p->lchild); // 递归左子树线索化
        if (!p->lchild) //没有左孩子
        {
            p->LTag = Thread; // 前驱线索
            p->lchild = pre; // 左孩子指针指向前驱
        }
        if (!pre->rchild) // 前驱没有右孩子
        {
            pre->RTag=Thread; //后继线索
            pre->rchild=p; //前驱右孩子指针指向后继
        }
        pre=p; //保持pre指向p的前驱
        inThreading(p->rchild); // 递归右子树线索化
    }
}

if (!p->lchild)表示如果某结点的左指针域为空，因为其前驱结点刚刚访问过，赋值给了pre，所以可以将pre赋值给p->child，并修改 p->LTag = Thread(也就是定义为1)以完成前驱结点的线索化

后继稍微麻烦一些，因为此时p结点的后继还没有访问到，因此只能对它的前驱结点pre的右指针rchild左判断，if(!pre->rchild)表示如果为空，则p就是pre的后继，于是 pre->rchild=p;并设置pre->RTag=Thread;完成后继结点的线索化

完成前驱和后继的判断后，别忘记将当前结点p赋值给pre，以便于下一次使用。有了线索二叉树后，我们对它进行遍历时发现，其实就等于是操作一个双向链表结构。

和双向链表结构一样，在二叉线索链表上添加一个头结点，如图6-10-6所示，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点，反之，令二叉树的中序序列中的第一个结点中，lchild域指针和最后一个结点rchild域指针均指向头结点（图中3和4），这样定义的好处就是我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点其顺前驱进行遍历

屏幕快照 2018-09-30 上午10.44.56.png

遍历的代码如下：

Status InOrderTraverse(BiThrTree T)
{
    BiThrTree p;
    p = T->lchild; // p
    while (p != T) {
        while (p->LTag==Link) { // 当LTag==0时循环到中序列第一个节点
            p = p->lchild;
            printf("%c", p->data); // 显示节点数据，可以更改为其他对节点操作
            while (p->RTag==Thread && p->rchild != T) {
                p = p->rchild;
                printf("%c", p->data);
            }
            p = p->rchild;   // p进至其右子树根
        }
        return OK;
    }
}

由于它充分利用了空指针于的空间（这等于节省了空间），又保证了创建时的一次遍历就可以终身受用前驱后继的信息。所以在实际问题中，如果所用的二叉树需要经常遍历或查找节点时需要某种遍历序列的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择

树、森林、二叉树的转换

树转换为二叉树

将树转换为二叉树的步骤如下：

1、加线。在所有兄弟节点之间加一条连线
2、去线。对树中每个节点，只保留它与第一个孩子节点的连线，删除它与其他孩子节点之间的连线。
3、层次调整。以树的根节点为轴心

例如图6-11-2，一棵树经过三个步骤转换为一棵二叉树。

屏幕快照 2019-04-30 上午9.31.32.png

森林转换为二叉树

森林是若干棵树组成的，所以完成可以理解为，森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作。步骤如下：

1、把每棵树转换为二叉树
2、第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树

例如图6-11-3，将森林的三棵树转换为一棵二叉树

屏幕快照 2019-04-30 上午9.37.33.png

二叉树转换为树

二叉树转换为树是树转换为二叉树的逆过程。步骤如下：

1、加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点。。。，反正就是左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来
2、去线。删除原二叉树中所有结点与其右孩子结点的连线
3、层次调整，使之结构层次分明

屏幕快照 2019-04-30 上午9.45.54.png

二叉树转换为森林

判断一棵二叉树能够转换成为一棵树还是森林，标准很简单，那就是只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。如果是转换为森林，步骤如下：

1、从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除...，直到所有右孩子连线都被删除为止，得到分离的二叉树
2、再将每棵分离后的二叉树转换为树即可

屏幕快照 2019-04-30 上午9.56.30.png

树与森林的遍历

树的遍历有两种方式：

1、先根遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树
2、后根遍历树，即先依次访问后根遍历每棵子树，然后再访问根结点。

比如图6-11-4中最右侧的树，它的先根遍历序列为ABEFCDG，后根遍历序列为EFBCGDA

森林的遍历也有两种：

1、前序遍历：先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林

比如图6-11-5右侧三棵树的森林，前序遍历序列的结果就是ABCDEFGHJI

2、后续遍历：先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林。

比如图6-11-5右侧三棵树的森林，后序遍历序列的结果就是BCDAFEJHIG

哈夫曼树及其应用

哈夫曼树定义与原理

先把两棵二叉树简化成为叶子结点带权的二叉树，如图6-12-4。其中A表示不及格、B表示及格、 C表示中等、D表示良好、E表示优秀。每个叶子的分支线上的数字是分数所占比例

屏幕快照 2019-04-30 下午2.14.56.png

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。

上图的二叉树a，根结点到结点D的路径长度为4，二叉树b的路径长度为2.

树的路径长度就是从树根到每个结点的路径长度之和。

二叉树a的树路径长度就为：1+1+2+2+3+3+4+4=20，二叉树b的树路径长度为：1+2+3+3+2+1+2+2=16

如果考虑到带权的结点，结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘机。树的待权路径长度为树中所有叶子结点的带权路径长度之和。

假设有n个权值{w₁，w₂，...，w_n }，构造一棵有n个叶子结点的二叉树，每个叶子结点带权w_k，每个叶子结点的长度为k，则其中带权路径长度WPL最小的二叉树为哈夫曼树。也成了最优二叉树

有了哈夫曼树定义，分别计算两棵树的WPL值

二叉树a的WPL = 5 x 1 + 15 x 2 + 40 x 3 + 30 x 4 + 10 x 4 = 315

注意：5是A结点的权，1是A结点的路径长度，其他同理

二叉树b的WPL = 5 x 3 + 15 x 3 + 40 x 2 + 30 x 2 + 10 x 2 = 220

这样的结果意味着什么？如果我们现在有10000个学生的百分制成绩需要计算五分制成绩，用二叉树a的判断方法，需要做31500此比较，而二叉树b的判断，只需要22000，性能上有很大提高

那么现在的问题是，二叉树b这样的树是如何构造出来的，这样的二叉树是不是最优的霍夫曼树？解决如下：

1、先把有权值的叶子结点按照从小到大的顺序排成一个有序序列，即A5，E10, B15, D30, C40.
2、取头两个最小权值的结点作为一个新结点N₁的两个子结点，注意相对较小的是左孩子，这里显然A为N₁的左孩子，E为N₁的右孩子，如下图所示，新结点的权值为两个叶子权值的和5 + 10 = 15

屏幕快照 2019-04-30 下午2.57.53.png

3、将N₁替换A和E，插入有序序列中，保持从小到到的排序。即：N₁15，B15, D30, C40.
4、重复步骤2，将N₁与B作为一个新结点N₂的两个子结点。如下图，N₂的权值为15 + 15=30

屏幕快照 2019-04-30 下午3.00.19.png

5、继续重复上述操作，最终完成构造哈夫曼树

屏幕快照 2019-04-30 下午3.02.51.png

此时二叉树的带权路径长度WPL=40 x 1+ 30 x 2 + 15 x 3 + 10 x 4 + 5 x 4 = 205，显然此时构造带二叉树才是最优的哈夫曼树

通过刚才的步骤，可以得到哈夫曼算法的描述

1、根据给定的n个权值{w₁,w₂,...,w_n}构成n棵二叉树的集合F={T₁,T₂,...,T_n}，其中每棵二叉树T_i中只有一个带权为w_i根结点，其左右子树均为空
2、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点权值之和
3、在F中删除这两棵树，同时将新得到的二叉树加入F中
4、重复步骤2和3，直到F值含一棵树为止。这棵树便是哈夫曼树

哈夫曼编码

哈夫曼树解决了当年远距离通信（主要是电报）的数据传输的最优化问题

比如：我们右一段文字内容为“BADCADFEED”要网络传输给别人，显示用二进制的数字（0和1）来表示是很自然的想法，如下

屏幕快照 2019-04-30 下午3.22.30.png

这样真正传输的数据就是编码后的“001000011010000011101100100011”，对方接收时可以按照3位一分来译码。如果一篇文章很长，这样的二进制串也将非常的可怕。而且事实上，不管是英文、中文、或是其他语言，字母或汉字出现频率是不相同的。

假设6个字母的频率为 A 27, B 8, C 15, D 15, E 30, F 5,合起来正好是100%，那就意味着，我们完全可以重新按照哈夫曼来规划它们

左图为构造哈夫曼树过程的权值表示，右图为将权值左分支改为0，右分支改为1后的哈夫曼树

屏幕快照 2019-04-30 下午3.31.27.png

此时，我们对这6个字母用其从树根到叶子所经过路径的0或1来编码，可以得到下表

屏幕快照 2019-04-30 下午3.32.58.png

将文字内容为“BADCADFEED”再次编码，对比可以看到结果串变小了。

原编码二进制串：001000011010000011101100100011 （共20个字符）
新编码二进制串：1001010010101001000111100 （共25个字符）

也就是说，我们的数据被压缩了，节约了大约17%的存储或传输成本，随着字符的增加和多字符权重的不同，这种压缩会更加显示出其优势

一般地，设需要编码的字符集为{d₁,d₂,...,d_n}，各个字符在电文中出现的次数或频率集合为{w₁,w₂,...,w_n},以d₁,d₂,...,d_n作为叶子结点，以w₁,w₂,...,w_n作为相应叶子结点的权值来构造一棵哈夫曼树。规定哈夫曼树的左分支代表0，右分支代表1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是哈夫曼编码

参考

《大话数据结构》