线索二叉树

定义

给没有左孩子的结点的左指针域赋值指向该结点前驱的指针，给没有右孩子的结点的右指针域赋值指向该结点后继的指针，这种指向前驱和后继的指针称为线索，相应的二叉树称为线索二叉树。

产生原因：想要知道某结点的前驱后继是谁时不用再次遍历，节约了时间；空指针域得以利用，节省了空间。

以下均为中序遍历

mark

线索二叉树相当于把一棵二叉树变成了一个双向链表。

把对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化

为了区分孩子指针和前驱后继指针，每个结点再增设两个标志域，只存放布尔型变量：

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

结构代码

typedef enum {Link,Thread} PointerTag;
//Link==0表示指向左右孩子的指针，Thread==1表示指向前驱或后继的指针
typedef struct BitThrNode
{
    TElemType data;
    struct BitThrNode *lchild,*rchild;
    PointerTag LTag;
    PointerTag RTag;//左右标志
}BiThrNode,*BiThrTree;

线索化的过程就是在遍历过程中修改空指针的过程。

中序遍历线索化代码

BiThrTree pre;//全局变量，始终指向刚刚访问过的结点
void InThreading (BiTheTree 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);//递归右子树线索化
    }
}

可以加一个头结点，lchild指针域的指针指向二叉树的根结点；rchild指针域的指针指向中序遍历时访问的最后一个结点；二叉树中序遍历第一个结点的lchild指针域的指针和最后一个结点的rchild指针域的指针均指向头结点。这样定义的好处是既可以从第一个结点开始向后遍历，又可以从最后一个结点开始向前遍历(相当于循环链表)

mark

疑问：前驱和后继指针在度为2的结点处不连续，走不通

回答：假设某个结点度为2，它的左子树通过后继指针走到尽头后即访问该结点，疑问在于此时此刻没有后继指针了无法继续向后，实际上无论如何下一步都会进入该结点的右子树，故下一步找到其右子树进行中序遍历的第一个结点即可，具体见下代码：

遍历带有头结点的线索二叉树代码

//T指向头结点，中序遍历二叉线索链表表示二叉树T
Status InOrderTraverse_Thr (BiThrTree T)
{
    BiThrTree p;
    p = T->lchild;//p指向根结点
    while (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;//当结点存在右子树时进入右子树根
    }
    return OK;
}

如果所用的二叉树需要经常遍历或查找结点时需要某种遍历序列中的前驱或后继，则采用线索二叉链表的存储结构是一种不错的选择。

树、二叉树、森林的转换

树转化为二叉树

加线。在所有兄弟结点间加一条连线。
去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
层次调整。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来是结点的右孩子

mark

森林转换为二叉树

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

mark

二叉树转换为树

加线。若某结点的左孩子结点存在，则将左孩子的n个右孩子都作为此结点的孩子，用线连接起来。
去线。删除原二叉树中所有结点与其右孩子结点的连线。
层次调整。

mark

二叉树转换为森林

判断一棵二叉树能转换成一棵树还是森林，只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。

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

mark

树与森林的遍历

树的遍历：

方法一：先根遍历树，即先访问树的根结点，再依次先根遍历根的每棵子树。

方法二：后根遍历，即先依次后根遍历每棵子树，再访问根结点。

森林的遍历：

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

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

树和森林的前序遍历和二叉树的前序遍历结果相同，树和森林的后序遍历和二叉树的中序遍历结果相同。

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

赫夫曼树及其应用

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

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

如果考虑带权的结点，结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。

树的带权的路径长度为树中所有叶子结点的带权路径长度之和。

赫夫曼树：带权路径长度WPL最小的二叉树。

求法： mark

mark

归纳：

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

赫夫曼树创建目的是解决当年远距离通信(主要是电报)的数据传输的最优化问题。

详见大话数据结构P205

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