大话数据结构第六章树

本文最后更新于：2020年7月10日下午

6.1-6.2 树的定义

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

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

n>0时根结点是唯一的，不可能存在多个根结点，数据结构中的树是只能有一个根结点。
m>0时，子树的个数没有限制，但它们一定是互不相交的。

6.2.1 结点分类

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度（Degree）。度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。如图6-2-4所示，因为这棵树结点的度的最大值是结点D的度为3，所以树的度也为3。
6-2-4

6.2.2 结点间关系

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

6.2.3 树的其他相关概念

结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度。
如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
森林（Forest）是m（m>0）棵互不相交的树的集合。
对比线性表与树的结构，它们有很大的不同，如图6-2-7所示。
6-2-7

6.3 树的抽象数据类型

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，cure）：若cur_e是树T的非叶结点，则返回它的最左孩子，否则返回空。
  RightSibling（T，cur_e）：若cur_e有右兄弟，则返回它的右兄弟，否则返回空。
  InsertChild（*T，*p，i，c）：其中p指向树T的某个结点，i为所指结点p的度加上1，非空树c与T不相交，操作结果为插入c为树T中p指结点的第i棵子树。
  DeleteChild（*T，*p，i）：其中p指向树T的某个结点，i为所指结点p的度，操作结果为删除T中p所指结点的第i棵子树。
endADT

6.4 树的存储结构

充分利用顺序存储和链式存储结构的特点，可以实现对树的存储结构的表示。我们这里要介绍三种不同的表示法：双亲表示法、孩子表示法、孩子兄弟表示法。

6.4.1 双亲表示法

树除了根结点外，其余每个结点，它不一定有孩子，但是一定有且仅有一个双亲。
我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里。
data数据域，存储结点的数据信息。而parent指针域，存储该结点的双亲在数组中的下标。
以下是我们的双亲表示法的结点结构定义代码:

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

有了这样的结构定义，我们就可以来实现双亲表示法了。由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1，这也就意味着，我们所有的结点都存有它双亲的位置。如图6-4-1中的树结构和表6-4-2中的树双亲表示所示。
6-4-1

这样的存储结构，我们可以根据结点的parent指针很容易找到它的双亲结点，所用的时间复杂度为O(1)，直到parent为-1时，表示找到了树结点的根。可如果我们要知道结点的孩子是什么，请遍历整个结构才行。如何改进呢？
我们增加一个结点最左边孩子的域，不妨叫它长子域，这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为-1，如表6-4-3所示。
6-4-3

对于有0个或1个孩子结点来说，这样的结构是解决了要找结点孩子的问题了。甚至是有2个孩子，知道了长子是谁，另一个当然就是次子了。
另外一个问题是，我们很关注各兄弟之间的关系，双亲表示法无法体现这样的关系，那我们怎么办？嗯，可以增加一个右兄弟域来体现兄弟关系，也就是说，每一个结点如果它存在右兄弟，则记录下右兄弟的下标。同样的，如果右兄弟不存在，则赋值为-1。
但如果结点的孩子很多，超过了2个。我们又关注结点的双亲、又关注结点的孩子、还关注结点的兄弟，而且对时间遍历要求还比较高，那么我们还可以把此结构扩展为有双亲域、长子域、再有右兄弟域。存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理，取决于基于该存储结构的运算是否适合、是否方便，时间复杂度好不好等。注意也不是越多越好，有需要时再设计相应的结构。

6.4.2 孩子表示法

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

6.4.2.1 方案一

一种是指针域的个数就等于树的度，复习一下，树的度是树各个结点度的最大值。其结构如表6-4-5所示。
6-4-5
其中data是数据域。child1到child d是指针域，用来指向该结点的孩子结点。
对于图6-4-1的树来说，树的度是3，所以我们的指针域的个数是3，这种方法实现如图6-4-2所示。
6-4-2
这种方法对于树中各结点的度相差很大时，显然是很浪费空间的，因为有很多的结点，它的指针域都是空的。不过如果树的各结点度相差很小时，那就意味着开辟的空间被充分利用了，这时存储结构的缺点反而变成了优点。
既然很多指针域都可能为空，那么我们可以按需分配空间。

6.4.2.2 方案二

第二种方案每个结点指针域的个数等于该结点的度，我们专门取一个位置来存储结点指针域的个数，其结构如表6-4-6所示。
6-4-6
其中data为数据域，degree为度域，也就是存储该结点的孩子结点的个数，child1到child d为指针域，指向该结点的各个孩子的结点。
对于图6-4-2的树来说，这种方法实现如图6-4-3所示。
6-4-7
这种方法克服了浪费空间的缺点，对空间利用率是很高了，但是由于各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗。

孩子表示法。具体办法是，把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中，如图6-4-4所示。
6-4-8
以下是我们的孩子表示法的结构定义代码:

/*树的孩子表示法结构定义*/
#define MAX_TREE_SIZE 100
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;

这样的结构对于我们要查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的，对头结点的数组循环即可。
但是，这也存在着问题，我如何知道某个结点的双亲是谁呢？比较麻烦，需要整棵树遍历才行，难道就不可以把双亲表示法和孩子表示法综合一下吗？当然是可以。如图6-4-5所示。
6-4-9
我们把这种方法称为双亲孩子表示法。

6.4.3 孩子兄弟表示法

我们观察后发现，任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。
结点结构如下所示。
data | firstChild | rightSib
—–|————|———
其中data是数据域，firstChild为指针域，存储该结点的第一个孩子结点的存储地址，rightSib是指针域，存储该结点的右兄弟结点的存储地址。
结构定义代码如下:

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

对于图6-4-1的树来说，这种方法实现的示意图如图6-4-6所示。
6-4-10
这种表示法，给查找某个结点的某个孩子带来了方便，只需要通过firstChild找到此结点的长子，然后再通过长子结点的rightSib找到它的二弟，接着一直下去，直到找到具体的孩子。

6.5 二叉树的定义

二叉树（Binary Tree）是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

6.5.1 二叉树特点

二叉树的特点有：

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

二叉树具有五种基本形态：

空二叉树。
只有一个根结点。
根结点只有左子树。
根结点只有右子树。
根结点既有左子树又有右子树。

6.5.2 特殊二叉树

一、斜树:所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

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

叶子只能出现在最下一层。出现在其他层就不可能达成平衡。
非叶子结点的度一定是2。否则就是“缺胳膊少腿”了。
在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

三、完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
完全二叉树的特点：

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

6.6 二叉树的性质

二叉树有一些需要理解并记住的特性，以便于我们更好地使用它。

6.6.1 二叉树性质1

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

6.6.2 二叉树性质2

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

6.6.3 二叉树性质3

性质3：对任何一棵二叉树T，如果其叶子结点数为$n_0$，度为2的结点数为$n_2$，则$n_0=n_2+1$。

6.6.4 二叉树性质4

性质4：具有n个结点的完全二叉树的深度为[㏒$_2$n]+1（[x]表示不大于x的最大整数）。

6.6.5 二叉树性质5

性质5：如果对一棵有n个结点的完全二叉树（其深度为[㏒$_2$n]+1）的结点按层序编号（从第1层到第[㏒$_2$n]+1层，每层从左到右），对任一结点i（1≤i≤n）有：

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

6.7 二叉树的存储结构

6.7.1 二叉树顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系。
所以用来表示完全二叉树比较好。由于它定义的严格，所以用顺序结构也可以表现出二叉树的结构来。
当然对于一般的二叉树，尽管层序编号不能反映逻辑关系，但是可以将其按完全二叉树编号，只不过，把不存在的结点设置为“^”而已。如图6-7-3所示，浅色结点表示不存在。
6-7-3
但是对于一般二叉树，一棵深度为k的右斜树，它只有k个结点，却需要分配$2^k$-1个存储单元空间，这显然是对存储空间的浪费。
所以，顺序存储结构一般只用于完全二叉树。

6.7.2 二叉链表

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

就如同树的存储结构中讨论的一样，如果有需要，还可以再增加一个指向其双亲的指针域，那样就称之为三叉链表。

6.8遍历二叉树

6.8.1二叉树遍历原理

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

6.8.2二叉树遍历方法

二叉树的遍历方式可以很多，如果我们限制了从左到右的习惯方式，那么主要就分为四种：

前序遍历-根左右
规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。
中序遍历-左根右
规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。
后序遍历-左右根
规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。
层序遍历
规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

技巧：每个结点单独看。比如后序遍历，每个右结点的左边是该结点的左节点，右边必然是对应的根结点。

6.8.3 前序遍历算法

二叉树的定义是用递归的方式，所以，实现遍历算法也可以采用递归，而且极其简洁明了。先来看看二叉树的前序遍历算法。代码如下：

/* 二叉树的前序遍历递归算法 */
void PreOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    printf("%c", T->data); /* 显示结点数据，可以更改为其它对结点操作 */
    PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
    PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}

6.8.4 中序遍历算法

二叉树的中序遍历算法和前序遍历算法仅仅只是代码的顺序上的差异。

/* 二叉树的中序遍历递归算法 */
void InOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    InOrderTraverse(T->lchild); /* 中序遍历左子树 */
    printf("%c", T->data);/* 显示结点数据，可以更改为其它对结点操作 */
    InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}

6.8.5后序遍历算法

那么同样的，后序遍历也就很容易想到应该如何写代码了。

/* 二叉树的后序遍历递归算法 */
void PostOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    PostOrderTraverse(T->lchild); /* 先后序遍历左子树  */
    PostOrderTraverse(T->rchild); /* 再后序遍历右子树  */
    printf("%c", T->data);/* 显示结点数据，可以更改为其它对结点操作 */
}

6.8.6 推导遍历结果

两个二叉树遍历的性质。

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

但要注意了，已知前序和后序遍历，是不能确定一棵二叉树的，原因也很简单，比如前序序列是ABC，后序序列是CBA。我们可以确定A一定是根结点，但接下来，我们无法知道，哪个结点是左子树，哪个是右子树。这棵树可能有如图6-8-24所示的四种可能。
6-8-24

推导遍历结果的具体方法如下：

根据前序或后续遍历序列确定二叉树的各子树的根；
根据中序遍历序列确定各子树根的左、右子树。

【例】二叉树的中序序列是ABCDEFG，后序序列是BDCAFGE，求前序序列？

由后序的BDCAFG|E，得到E是根结点，因此前序首字母是E。
以中序序列的根节点E将中序序列分为两棵树ABCD和FG，后序序列分为BDCA和FG，知道A是E的左孩子。
再由中序序列的A|BCD，知道BCD是A结点的右孩子，再由后序序列的BDC|A，知道C结点是A结点的右孩子。
中序序列AB|C|D，得到B是C的左孩子，D是C的右孩子。
由后序序列F|G|E，得到G是E的右孩子；在看中序序列F|G，F就是G的左孩子。
至此，二叉树画出来了。前序遍历序列的最终结果就是EACBDGF。

6.9 二叉树的建立

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

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

当然，你完全也可以用中序或后序遍历的方式实现二叉树的建立，只不过代码里生成结点和构造左右子树的代码顺序交换一下。另外，输入的字符也要做相应的更改。

6.10 线索二叉树

6.10.1 线索二叉树原理

指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree）。
其实线索二叉树，等于是把一棵二叉树转变成了一个双向链表，这样对我们的插入删除结点、查找某个结点都带来了方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。
但是变为线索二叉树，我们并不知道某个结点的lChild是指向它的左孩子还是指向前驱…
因此，我们在每个结点再增设两个标志域lTag和rTag，注意lTag和rTag只是存放0或1数字的布尔型变量，其占用的内存空间要小于像lchild和rchild的指针变量。结点结构如下表所示。
lChild|lTag|data|rTag|rChild
-|-|-|-|-
其中：

lTag为0时指向该结点的左孩子，为1时指向该结点的前驱。
rTag为0时指向该结点的右孩子，为1时指向该结点的后继。

6.10.2 线索二叉树结构实现

由此二叉树的线索存储结构定义代码如下：

/* 二叉树的二叉线索存储结构定义 */
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; /* 前驱右孩子指针指向后继(当前结点p) */
        }
        pre = p; /* 保持pre指向p的前驱 */
        InThreading(p->rchild); /* 递归右子树线索化 */
    }
}

if（!p->lChild）表示如果某结点的左指针域为空，因为其前驱结点刚刚访问过，赋值给了pre，所以可以将pre赋值给p->lChild，并修改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 域指针均指向头结点（图中的③和④）。这样定义的好处就是我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。
6-10-6

遍历的代码如下：

/*T指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的*/
/*最后一个结点。中序遍历二叉线索链表表示的二叉树T*/
Status InOrderTraverse_Thr(BiThrTree T)
{
    BiThrTree p;
    p = T->lchild; /* p指向根结点 */
    while (p != T) /* 空树或遍历结束时，p==T */
    { /* 空树或遍历结束时,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;
}

从这段代码也可以看出，它等于是一个链表的扫描，所以时间复杂度为O(n)。
由于它充分利用了空指针域的空间（这等于节省了空间），又保证了创建时的一次遍历就可以终生受用前驱后继的信息（这意味着节省了时间）。所以在实际问题中，如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

6.11 树、森林与二叉树的转换

6.11.1 树转换为二叉树

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

加线。在所有兄弟结点之间加一条连线。
去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。

6.11.2 森林转换为二叉树

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

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

6.11.3 二叉树转换为树

二叉树转换为树是树转换为二叉树的逆过程，也就是反过来做而已。如图6-11-4所示。步骤如下：

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

6-11-4

6.11.4 二叉树转换为森林

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

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

6-11-5

6.11.5 树与森林的遍历

树的遍历分为两种方式。

一种是先根遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树。
另一种是后根遍历，即先依次后根遍历每棵子树，然后再访问根结点。比如图6-11-4中最右侧的树，它的先根遍历序列为ABEFCDG，后根遍历序列为EFBCGDA。

森林的遍历也分为两种方式：

前序遍历：先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林。比如图6-11-5右侧三棵树的森林，前序遍历序列的结果就是ABCDEFGHJI。
后序遍历：是先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林。比如图6-11-5右侧三棵树的森林，后序遍历序列的结果就是BCDAFEJHIG。

可如果我们对二叉树进行分析就会发现，森林的前序遍历和二叉树的前序遍历结果相同，森林的后序遍历和二叉树的中序遍历结果相同。
这也就告诉我们，当以二叉链表作树的存储结构时，树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。这其实也就证实，我们找到了对树和森林这种复杂问题的简单解决办法。

6.12 赫夫曼(也有称为哈夫曼)树及其应用

6.12.1 赫夫曼树

压缩软件如何做到压缩而不出错的呢？简单说，就是把我们要压缩的文本进行重新编码，以减少不必要的空间。我们今天就来介绍一下最基本的压缩编码方法——赫夫曼编码。
由美国数学家赫夫曼（David Huffman）在1952年发明了赫夫曼编码。他在编码中用到的特殊的二叉树称之为赫夫曼树，他的编码方法称为赫夫曼编码。

6.12.2 赫夫曼树定义与原理

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。
树的路径长度就是从树根到每一结点的路径长度之和。
如果考虑到带权的结点，结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。假设有n个权值{w1，w2，…，Wn}，构造一棵有n个叶子结点的二叉树，每个叶子结点带权Wk，每个叶子的路径长度为lk，我们通常记作，则其中带权路径长度WPL最小的二叉树称做赫夫曼树。
6-12-4
有了赫夫曼对带权路径长度的定义，我们来计算一下图6-12-4这两棵树的WPL值。
二叉树a的WPL=5×1+15×2+40×3+30×4+10×4=315
注意：这里5是A结点的权，1是A结点的路径长度，其他同理。
二叉树b的WPL=5×3+15×3+40×2+30×2+10×2=220
参考图6-12-4的二叉树b，最优赫夫曼树的解法如下：

先把有权值的叶子结点按照从小到大的顺序排列成一个有序序列，即：A5，E10，B15，D30，C40。
取头两个最小权值的结点作为一个新节点N1的两个子结点，注意相对较小的是左孩子，这里就是A为N1的左孩子，E为N1的右孩子，如图6-12-5所示。新结点的权值为两个叶子权值的和5+10=15。
将N1替换A与E，插入有序序列中，保持从小到大排列。即：N1 15，B15，D30，C40。
重复步骤2。将N1与B作为一个新节点N2的两个子结点。如图6-12-6所示。N2的权值=15+15=30。
将N2替换N1与B，插入有序序列中，保持从小到大排列。即：N2 30，D30，C40。
重复步骤2。将N2与D作为一个新节点N3的两个子结点。如图6-12-7所示。N3的权值=30+30=60。
将N3替换N2与D，插入有序序列中，保持从小到大排列。即：C40，N3 60。
重复步骤2。将C与N3作为一个新节点T的两个子结点，如图6-12-8所示。由于T即是根结点，完成赫夫曼树的构造。

此时的图6-12-8二叉树的带权路径长度WPL=40×1+30×2+15×3+10×4+5×4=205。与图6-12-4的二叉树b的WPL值220相比，还少了15。显然此时构造出来的二叉树才是最优的赫夫曼树。

通过刚才的步骤，我们可以得出构造赫夫曼树的赫夫曼算法描述。

根据给定的n个权值{$w_{1} ，w_{2} ，…，w_{n}$}构成n棵二叉树的集合$F=${$T_{1}，T_{2}，…，T_{n}$}，其中每棵二叉树$T_{i}$中只有一个带权为$w_{i}$根结点，其左右子树均为空。
在森林$F$中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
在$F$中删除这两棵树，同时将新得到的二叉树加入$F$中。
重复2和3步骤，直到F只含一棵树为止。这棵树便是赫夫曼树。

6.12.3 赫夫曼编码

按照不同字母出现的频率重新按照赫夫曼树来规划它们。将规划出来的树权值左分支改为0，右分支改为1后。对字母从树根到叶子所经过路径的0或1来编码，可以看出结果串变小了，编码得到了压缩，节约了存储和传输成本。

当我们接收到压缩过的新编码时，我们应该如何把它解码出来呢？

编码中非0即1，长短不等的话其实是很容易混淆的，所以若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。

可以利用哈夫曼树来设计二进制的前缀编码。

【例】如图6-12-9所示哈夫曼树，其左分支表示字符“0”，右分支表示字符“1”，则以根节点到叶结点路径上的分支字符组成的串作为该叶结点的字符编码，则可得字符a、b、c、d的二进制前缀编码分别为：0、10、110、111。

6-12-9

为了让我们去方便地解码的，在解码时，还是要用到赫夫曼树，即发送方和接收方必须要约定好同样的赫夫曼编码规则。

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

简而言之，设计电文总长最短的二进制前缀编码，就是以$n$种字符出现的频率作为权构造一棵哈夫曼树，由哈夫曼树求得的编码就是哈夫曼编码。

6.13 总结回顾

终于到了总结的时间，这一章与前面章节相比，显得过于庞大了些，原因也就在于树的复杂性和变化丰富度是前面的线性表所不可比拟的。即使在本章之后，我们还要讲解关于树这一数据结构的相关知识，可见它的重要性。
开头我们提到了树的定义，讲到了递归在树定义中的应用。提到了如子树、结点、度、叶子、分支结点、双亲、孩子、层次、深度、森林等诸多概念，这些都是需要在理解的基础上去记忆的。
我们谈到了树的存储结构时，讲了双亲表示法、孩子表示法、孩子兄弟表示法等不同的存储结构。
并由孩子兄弟表示法引出了我们这章中最重要一种树，二叉树。
二叉树每个结点最多两棵子树，有左右之分。提到了斜树，满二叉树、完全二叉树等特殊二叉树的概念。
我们接着谈到它的各种性质，这些性质给我们研究二叉树带来了方便。
二叉树的存储结构由于其特殊性使得既可以用顺序存储结构又可以用链式存储结构表示。
遍历是二叉树最重要的一门学问，前序、中序、后序以及层序遍历都是需要熟练掌握的知识。要让自己要学会用计算机的运行思维去模拟递归的实现，可以加深我们对递归的理解。不过，并非二叉树遍历就一定要用到递归，只不过递归的实现比较优雅而已。这点需要明确。
二叉树的建立自然也是可以通过递归来实现。
研究中也发现，二叉链表有很多浪费的空指针可以利用，查找某个结点的前驱和后继为什么非要每次遍历才可以得到，这就引出了如何构造一棵线索二叉树的问题。
线索二叉树给二叉树的结点查找和遍历带来了高效率。
树、森林看似复杂，其实它们都可以转化为简单的二叉树来处理，我们提供了树、森林与二叉树的互相转换的办法，这样就使得面对树和森林的数据结构时，编码实现成为了可能。
最后，我们提到了关于二叉树的一个应用，赫夫曼树和赫夫曼编码，对于带权路径的二叉树做了详尽地讲述，让你初步理解数据压缩的原理，并明白其是如何做到无损编码和无错解码的。

读书笔记大话数据结构

读书笔记数据结构

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

大话数据结构第七章图上一篇

大话数据结构第五章串下一篇

大话数据结构第六章 树