数据结构之树

数据结构与算法

一、树的基本概念

1.1 树的定义

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

需要强调的是，n>0时根结点是唯一的，不可能存在多个根结点，m>0时，子树的个数没有限制，但它们一定是互不相交的。以下两个结构不符合树的定义：

树的相关概念：

• 结点的度（De-gree）：结点拥有的子树数。
• 结点的层次（Level）：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树就在第l+1层。其双亲在同一层的结点互为堂兄弟。
• 树的深度（Depth）：树中结点的最大层次称为树的深度（Depth）或高度。
• 森林（Forest）：m（m≥0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。

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

线性表与树的结构对比

1.2 树的抽象数据类型

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的某个结点，i为所指结点p的度加上1，
                                非空树c与T不相交，操作结果为插入c为树T中p指结点的第i棵子树。
    DeleteChild(*T, *p, i):     其中p指向树T的某个结点，i为所指结点p的度，
                                操作结果为删除T中p所指结点的第i棵子树。
endADT

二、树的存储结构

2.1 双亲表示法

结点结构定义代码:

/* 树的双亲表示法结点结构定义 */
#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，这也就意味着，我们所有的结点都存有它双亲的位置。如下图：

这样的存储结构，根据结点的parent指针很容易找到它的双亲结点，所用的时间复杂度为O(1),然而如果要知道节点的孩子则需要遍历整个结构。

改进方法：增加一个结点最左边孩子的域（不妨叫它长子域），这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为-1，如下表：

类似的，如果需要表示兄弟节点，可以设计以下存储结构：

如果结点的孩子很多，超过了2个。我们又关注结点的双亲、又关注结点的孩子、还关注结点的兄弟，而且对时间遍历要求还比较高，那么我们还可以把此结构扩展为有双亲域、长子域、再有右兄弟域。存储结构的设计是一个非常灵活的过程。

$\color{red}{一个存储结构设计得是否合理，取决于基于该存储结构的运算是否适合、是否方便，\\时间复杂度好不好等。注意也不是越多越好，有需要时再设计相应的结构。}$

2.2 孩子表示法

多重链表表示法: 每个结点有多个指针域，其中每个指针指向一棵子树的根结点。
根据每个节点的度不一样，设计两种方案：

① 指针域的个数等于树的度
结构如下表：

其中data是数据域。child1到childd是指针域，用来指向该结点的孩子结点。
对于度为3的树，可用如下结构表示：

这种表示方法的缺点很明显，存在 大量存储空间浪费的情况。

② 每个结点指针域的个数等于该结点的度

其中data为数据域，degree为度域，也就是存储该结点的孩子结点的个数，child1到childd为指针域，指向该结点的各个孩子的结点。

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

有没有一种方法既可以减少空指针的浪费又能使结点结构相同？

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

该方法有两个节点结构：data —— firstchild; child —— next;
data是数据域，存储某结点的数据信息。firstchild是头指针域，存储该结点的孩子链表的头指针。child是数据域，用来存储某个结点在表头数组中的下标。next是指针域，用来存储指向某结点的下一个孩子结点的指针。

孩子表示法的结构定义代码

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

这样的结构如果要查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的，对头结点的数组循环即可。

但是，这也存在一个问题，如果要获取某个结点的双亲需要遍历整棵树，比较麻烦。
可以把双亲表示法与孩子表示法结合，这就是双亲孩子表示法

2.3 孩子兄弟表示法

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

结点结构为：data —— firstchild —— rightsib
其中data是数据域，firstchild为指针域，存储该结点的第一个孩子结点的存储地址，right-sib是指针域，存储该结点的右兄弟结点的存储地址。

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

结构图：

从结构图可以看出，这就成为了一棵二叉树。

三、二叉树

3.1 二叉树的定义

二叉树的特点

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

二叉树具有五种基本形态： 1.空二叉树。 2.只有一个根结点。 3.根结点只有左子树。 4.根结点只有右子树。 5.根结点既有左子树又有右子树。

特殊二叉树
斜树：所有的结点都只有左子树的二叉树叫左斜树，所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。斜树有很明显的特点，就是每一层都只有一个结点，结点的个数与二叉树的深度相同。
满二叉树:在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

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

完全二叉树的特点：

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

3.2 二叉树的性质

性质1： 在二叉树的第i层上至多有2i-1个结点（i≥1）。
性质2： 深度为k的二叉树至多有2k-1个结点（k≥1）。
性质3： 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则$n_0=n_2+1$。

终端结点数其实就是叶子结点数，一棵二叉树，除了叶子结点外，剩下的就是度为1或2的结点数了。设n1为度是1的结点数。则树T结点总数$n=n_0+n_1+n_2$。换个角度，由于根结点只有分支出去，没有分支进入，所以分支线总数为结点总数减去1。用代数表达分支线总数 ： $n-1=n_1＋2n_2$。因为刚才我们有等式$n=n_0＋n_1＋n_2$，所以可推导出$n_0＋n_1＋n_2-1=n_1＋2n_2$。结论就是$n_0=n_2＋1$。

性质4： 具有n个结点的完全二叉树的深度为$|log_2n+1|$（|x|表示不大于x的最大整数）。
性质5： 如果对一棵有n个结点的完全二叉树（其深度为）的结点按层序编号（从第1层到第层，每层从左到右），对任一结点i（1≤i≤n）有：

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

3.3 二叉树的存储结构

3.3.1 顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。
一棵完全二叉树可以用数组表示：

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

如果对于一棵深度为k的右斜树，它只有k个结点，却需要分配2k-1个存储单元空间，这显然是对存储空间的浪费，例如图6-7-4所示。所以，顺序存储结构一般只用于完全二叉树。

3.3.2 二叉链表

二叉树每个结点最多有两个孩子，设计一个数据域和两个指针域来储存，这样的链表叫做二叉链表。
二叉链表的结点结构定义代码：

/* 二叉树的二叉链表结点结构定义 */
/* 结点结构 */
typedef struct BiTNode                  
{
    /* 结点数据 */
    TElemType data;                     
    /* 左右孩子指针 */
    struct BiTNode *lchild, *rchild;    
} BiTNode, *BiTree;

结构示意图:

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

3.4 遍历二叉树

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
二叉树的遍历方式可以很多，如果限制了从左到右的习惯方式，那么主要就分为四种：

3.4.2 前序遍历算法

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如图所示，遍历的顺序为：ABDGH-CEIF。

实现代码：

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

对于下图的二叉树T，已经用二叉链表结构储存在内存中：

当调用PreOrderTraverse(T)函数时，程序运行细节如下：
1．调用PreOrderTraverse(T)，T根结点不为null，所以执行printf，打印字母A；
2．调用PreOrderTraverse(T->lchild);访问了A结点的左孩子，不为null，执行printf显示字母B；
3．此时再次递归调用PreOrderTraverse(T->lchild);访问了B结点的左孩子，执行printf显示字母D；
4．再次递归调用PreOrderTraverse(T->lchild);访问了D结点的左孩子，执行printf显示字母H；
5．再次递归调用PreOrderTraverse(T->lchild);访问了H结点的左孩子，此时因为H结点无左孩子，所以T==null，返回此函数，此时递归调用PreOrderTraverse(T->rchild);访问了H结点的右孩子，printf显示字母K；
6. 再次递归调用PreOrderTraverse(T->lchild);访问了K结点的左孩子，K结点无左孩子，返回，调用PreOrderTra-verse(T->rchild);访问了K结点的右孩子，也是null，返回。于是此函数执行完毕，返回到上一级递归的函数（即打印H结点时的函数），也执行完毕，返回到打印结点D时的函数，调用PreOrderTraverse(T->rchild);访问了D结点的右孩子，不存在，返回到B结点，调用PreOrderTra-verse(T->rchild);找到了结点E，打印字母E;
7．由于结点E没有左右孩子，返回打印结点B时的递归函数，递归执行完毕，返回到最初的PreOrderTraverse，调用PreOrderTra-verse(T->rchild);访问结点A的右孩子，打印字母C;
8．之后类似前面的递归调用，依次继续打印F、I、G、J。

3.4.3 中序遍历算法

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

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

中序遍历算法较1前序遍历算法只是把左孩子的递归函数提前了。

程序运行过程：
1．调用InOrderTraverse(T)，T的根结点不为null，于是调用InOrderTraverse(T->lchild);访问结点B。当前指针不为null，继续调用InOrderTraverse(T->lchild);访问结点D。不为null，继续调用InOrderTraverse(T->lchild);访问结点H。继续调用InOrderTraverse(T->lchild);访问结点H的左孩子，发现当前指针为null，于是返回。打印当前结点H；
2．然后调用InOrderTraverse(T->rchild);访问结点H的右孩子K，因结点K无左孩子，所以打印K；
3．因为结点K没有右孩子，所以返回。打印结点H函数执行完毕，返回。打印字母D；
4．结点D无右孩子，此函数执行完毕，返回。打印字母B；
5．调用InOrderTraverse(T->rchild);访问结点B的右孩子E，因结点E无左孩子，所以打印E；
6．结点E无右孩子，返回。结点B的递归函数执行完毕，返回到了最初我们调用In-OrderTraverse的地方，打印字母A；
7．再调用InOrderTraverse(T->rchild);访问结点A的右孩子C，再递归访问结点C的左孩子F，结点F的左孩子I。因为I无左孩子，打印I，之后分别打印F、C、G、J。步骤省略。

3.4.4 后序遍历算法

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

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

后序遍历是先递归左子树，由根结点A→B→D→H，结点H无左孩子，再查看结点H的右孩子K，因为结点K无左右孩子，所以打印K，返回。

3.4.5 层序遍历算法

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

3.5 二叉树的建立

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

假设二叉树的结点均为一个字符，把刚才前序遍历序列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);    
    }
}

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

3.6 线索二叉树

在二叉链表中，当不是完全二叉树的时候，也存在着一些浪费空间的现象，另一方面，在二叉链表上，只能知道每个结点指向其左右孩子结点的地址，而不知道某个结点的前驱是谁，后继是谁。要想知道，必须遍历一次。以后每次需要知道时，都必须先遍历一次。如果在创建时就记住这些前驱和后继，会节约很大的时间。

利用那些空地址，存放指向结点在某种遍历次序下的前驱和后继结点的地址。把指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree）。

如下图，把这棵二叉树进行中序遍历后，将所有的空指针域中的rchild，改为指向它的后继结点。于是我们就可以通过指针知道H的后继是D（图中①），I的后继是B（图中②），J的后继是E（图中③），E的后继是A（图中④），F的后继是C（图中⑤），G的后继因为不存在而指向NULL（图中⑥）。此时共有6个空指针域被利用。

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

其实，线索二叉树就等于是把一棵二叉树转变成了一个双向链表，这样对于插入删除结点、查找某个结点都带来了方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。

不过这里还没有完，如何知道某一结点的lchild是指向它的左孩子还是指向前驱？rchild是指向右孩子还是指向后继？因此，需要在每个结点再增设两个标志域ltag和rtag，注意ltag和rtag只是存放0或1数字的布尔型变量，其占用的内存空间要小于像lchild和rchild的指针变量。结点结构如图所示：

其中：

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

这样的话二叉链表就改为下图所示：

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

/* 二叉树的二叉线索存储结构定义 */
/* Link==0表示指向左右孩子指针 */
/* Thread==1表示指向前驱或后继的线索 */
typedef enum {Link, Thread} PointerTag;    
/* 二叉线索存储结点结构 */
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;    
            /* 前驱右孩子指针指向后继（当前结点p） */
            pre->rchild = 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，以便于下一次使用。

线索二叉树的遍历就相当于操作一个双向链表

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

遍历的代码如下：

/* T指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的 */
/* 最后一个结点。中序遍历二叉线索链表表示的二叉树T */
Status InOrderTraverse_Thr(BiThrTree T)
{
    BiThrTree p;
    /* p指向根结点 */
    p = T->lchild;                 
    /* 空树或遍历结束时，p==T */
    while (p != T)                 
    {
        /* 当LTag==0时循环到中序序列第一个结点 */
        while (p->LTag == Link)    
            p = p->lchild;
        /* 显示结点数据，可以更改为其他对结点操作 */
        printf("%c", p->data);     
        while (p->RTag == Thread && p->rchild != T)
        {
           p = p->rchild;
           printf("%c", p->data);
        }
        /* p进至其右子树根 */
        p = p->rchild;             
   }
   return OK;
}  

1.代码中，第4行，p=T->lchild;意思就是上图中的①，让p指向根结点开始遍历。
2.第5～16行，while(p!=T)其实意思就是循环直到图中的④的出现，此时意味着p指向了头结点，于是与T相    等（T是指向头结点的指针），结束循环，否则一直循环下去进行遍历操作。
3.第7～8行，while(p->LTag==Link)这个循环，就是由A→B→D→H，此时H结点的LTag不是Link（就是不等于0    ），所以结束此循环。
4.第9行，打印H。
5.第10～14行，while(p->RTag==Thread&&p->rchild!=T)，由于结点H的RTag==Thread（就是等于1），且    不是指向头结点。因此打印H的后继D，之后因为D的RTag是Link，因此退出循环。
6.第15行，p=p->rchild;意味着p指向了结点D的右孩子I。
7.……，就这样不断循环遍历，直到打印出HDIBJEAFCG，结束遍历操作。

从这段代码也可以看出，它等于是一个链表的扫描，所以时间复杂度为O(n)。

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

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

3.7.1 树转换为二叉树

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

3.7.2 森林转换为二叉树

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

3.7.3 二叉树转换为树

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

3.7.4 二叉树转换为森林

判断一棵二叉树能够转换成一棵树还是森林，标准很简单，那就是只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。那么如果是转换成森林，步骤如下： 1.从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除……，直到所有右孩子连线都删除为止，得到分离的二叉树。
2.再将每棵分离后的二叉树转换为树即可。

3.7.5 树与森林的遍历

树的遍历分为两种方式:

• 一种是先根遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树;
• 另一种是后根遍历，即先依次后根遍历每棵子树，然后再访问根结点。

比如上上图中右下方的树，它的先根遍历序列为ABEFCDG，后根遍历序列为EFBCGDA。

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

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

森林的前序遍历和二叉树的前序遍历结果相同，森林的后序遍历和二叉树的中序遍历结果相同。当以二叉链表作树的存储结构时，树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。

3.8 赫夫曼树

我们平时所用到的压缩与解压缩技术都是基于赫夫曼的研究，为了纪念他，就把他在编码中用到的特殊的二叉树称之为赫夫曼树，他的编码方法称为赫夫曼编码。

3.8.1 赫夫曼树定义与原理

假设有n个权值{$w_1,w_2,...,w_n$}，构造一棵有n个叶子结点的二叉树，每个叶子结点带权$w_k$，每个叶子的路径长度为$l_k$，我们通常记作，则其中带权路径长度WPL最小的二叉树称做赫夫曼树。

构造赫夫曼树的赫夫曼算法:

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

3.8.2 赫夫曼编码

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