一、线索化二叉树

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

注意：线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题。

优势

(1)利用线索二叉树进行中序遍历时，不必采用堆栈处理，速度较一般二叉树的遍历速度快，且节约存储空间。
(2)任意一个结点都能直接找到它的前驱和后继结点。

不足

(1)结点的插入和删除麻烦，且速度也较慢。
(2)线索子树不能共用。

规则
1\. 结点左子树为空，利用左孩子指针指向它的前驱结点；
2\. 结点右子树为空，利用右孩子指针指向它的后继结点；
3\. 注意：所有前驱和后继必须按照某一种遍历逻辑（中序）

为了区分一个结点的左孩⼦指针指向的是左孩子还是前驱结点，引入了标志位（tag, 0表示左/右孩子，1表示前驱或后继），

完整代码

#include "string.h"
#include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */

/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int Status;
typedef char CElemType;
/* 字符型以空格符为空 */
CElemType Nil='#';

#pragma mark--二叉树构造
int indexs = 1;
typedef char String[24]; /*  0号单元存放串的长度 */
String str;
Status StrAssign(String T,char *chars)
{
    int i;
    if(strlen(chars)>MAXSIZE)
        return ERROR;
    else
    {
        T[0]=strlen(chars);
        for(i=1;i<=T[0];i++)
            T[i]=*(chars+i-1);
        return OK;
    }
}

/* Link==0表示指向左右孩子指针, */
/* Thread==1表示指向前驱或后继的线索 */
typedef enum {Link,Thread} PointerTag;

/* 线索二叉树存储结点结构*/
typedef struct BiThrNode{

    //数据
    CElemType data;

    //左右孩子指针
    struct BiThrNode *lchild,*rchild;

    //左右标记
    PointerTag LTag;
    PointerTag RTag;

}BiThrNode,*BiThrTree;

/*
 8.1 打印
 */
Status visit(CElemType e)
{
    printf("%c ",e);
    return OK;
}

/*
 8.3 构造二叉树
 按照前序输入线索二叉树结点的值,构造二叉树T
 */

Status CreateBiThrTree(BiThrTree *T){

    CElemType h;
    //scanf("%c",&h);
    //获取字符
    h = str[indexs++];

    if (h == Nil) {
        *T = NULL;
    }else{
        *T = (BiThrTree)malloc(sizeof(BiThrNode));
        if (!*T) {
            exit(OVERFLOW);
        }
        //生成根结点(前序)
        (*T)->data = h;

        //递归构造左子树
        CreateBiThrTree(&(*T)->lchild);
        //存在左孩子->将标记LTag设置为Link
        if ((*T)->lchild) (*T)->LTag = Link;

        //递归构造右子树
        CreateBiThrTree(&(*T)->rchild);
        //存在右孩子->将标记RTag设置为Link
        if ((*T)->rchild) (*T)->RTag = Link;
    }

    return OK;
}

/*
 8.3 中序遍历二叉树T, 将其中序线索化
 */

BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化*/
void InThreading(BiThrTree p){

    /*
     InThreading(p->lchild);
     .....
     InThreading(p->rchild);
     */
    if (p) {
        //递归左子树线索化
        InThreading(p->lchild);
        //无左孩子
        if (!p->lchild) {
            //前驱线索
            p->LTag = Thread;
            //左孩子指针指向前驱
            p->lchild  = pre;
        }else
        {
            p->LTag = Link;
        }

        //前驱没有右孩子
        if (!pre->rchild) {
            //后继线索
            pre->RTag = Thread;
            //前驱右孩子指针指向后继(当前结点p)
            pre->rchild = p;
        }else
        {
            pre->RTag = Link;
        }

        //保持pre指向p的前驱
        pre = p;
        //递归右子树线索化
        InThreading(p->rchild);
    }
}

/* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点 */
Status InOrderThreading(BiThrTree *Thrt , BiThrTree T){

    *Thrt=(BiThrTree)malloc(sizeof(BiThrNode));

    if (! *Thrt) {
        exit(OVERFLOW);
    }

    //建立头结点;
    (*Thrt)->LTag = Link;
    (*Thrt)->RTag = Thread;
    //右指针回指向
    (*Thrt)->rchild = (*Thrt);

    /* 若二叉树空,则左指针回指 */
    if (!T) {
        (*Thrt)->lchild=*Thrt;
    }else{

        (*Thrt)->lchild=T;
        pre=(*Thrt);

        //中序遍历进行中序线索化
        InThreading(T);

        //最后一个结点rchil 孩子
        pre->rchild = *Thrt;
        //最后一个结点线索化
        pre->RTag = Thread;
        (*Thrt)->rchild = pre;

    }
    return OK;
}

/*中序遍历二叉线索树T*/
Status InOrderTraverse_Thr(BiThrTree T){
    BiThrTree p;
    p=T->lchild; /* p指向根结点 T指向头结点 */
    while(p!=T)
    { /* 空树或遍历结束时,p==T */
        while(p->LTag==Link)//A->B->D->H, 此时H结点的LTag不是Link ,则循环结束
            p=p->lchild;
        if(!visit(p->data)) /* 访问其左子树为空的结点 */
            return ERROR;
        while(p->RTag == Thread && p->rchild != T)
            //由于结点H的RTag == Tread,且不不是指向头结点, 因此打印H的后继D,之后因为D的RTag 是Link 则退出循环.
        {
            p=p->rchild;
            visit(p->data); /* 访问后继结点 */
        }
        p=p->rchild;
    }

    return OK;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, 线索化二叉树!\n");
    BiThrTree H,T;

    //StrAssign(str,"ABDH#K###E##CFI###G#J##");
    StrAssign(str,"ABDH##I##EJ###CF##G##");

    CreateBiThrTree(&T); /* 按前序产生二叉树 */
    InOrderThreading(&H,T); /* 中序遍历,并中序线索化二叉树 */
    InOrderTraverse_Thr(H);
    printf("\n\n");
    return 0;
}

二、哈夫曼树

最优二叉树也称为哈夫曼树（Huffman）,是指对于一组带有确定权值的叶子结点，构造的具有最小带权路径长度的二叉树。权值是指一个与特定结点相关的数值。前面介绍过路径和结点的路径长度的概念，而二叉树的路径长度则是指由根节点到所有叶子结点的路径长度之和。如果二叉树中的所有叶子结点都具有一个特定权值，则可将这一概念加以推广。

设二叉树具有n个带权值的叶子结点，那么从根结点到各个叶子结点的路径长度与该叶子结点相应的权值的乘积之和叫做二叉树的带权路径长度(Weighted Path Length，简称WPL = 路径长度X权值)。

image

a:WPL = 1X2 + 3X2 + 5X2 +5X2 = 28;

b:WPL = 1X3 + 3X3 +5X2 +5X1 = 27;

c: WPL =1X2+3X3 +5X3 + 5X1 =31;

由此可见，由相同权值的一组叶子结点所构成的二叉树由不同形态和不同的带权路径长度。根据哈夫曼树定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶子结点越靠近根节点，而权值越小的叶子结点越远离根结点。哈夫曼根据这一特点提出了一种构造最优二叉树的方法，这种方法的基本思想是：

由给定的n个权值{W1,W2,...,Wn}构造n棵只有一个叶子结点的二叉树，从而得到一个二叉树的集合F={T1,T2,...,Tn};
在F中选取根结点的权值最小和次小的两棵二叉树作为左右子树构造一棵新树的二叉树，这棵新的二叉树根节点的权值为其左右子树的根节点权值之和；
在集合F中删除作为左右子树的两棵二叉树，并将新建立的二叉树加入到集合F中;
重复上面两部后，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。
下图给出了前面提到的叶子结点权值集合为W = {1,3,5,5}的哈夫曼树的构造过程。WPL=3X3+1X3+5X2+5X1 =27

image

三、哈夫曼树的构造算法

在构造哈夫曼树时，可以设置一个结构数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，数组元素的结构形式如下：

weight、lchild、rchild、parent。

其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左右孩子结点在数组HuffNode中序号，从而建立起结点之间的关系。为了判定一个结点算法已加入到要建立的哈夫曼树中，可通过parent域的值来确定。初始时parent的值为-1，当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffNode中的序号，就不会是-1了。

构造哈夫曼树时，首先将由n个字符形成的n个叶子结点存放到数组HuffNode的前n个分量重，然后根据起那么介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffNode数组中前n个分量的后面。算法如下：

const int MaxValue = 10000;//初始设定的权值最大值
const int MaxBit = 4;//初始设定的最大编码位数
const int MaxN = 10;//初始设定的最大结点个数

typedef struct HaffNode{
    int weight;
    int flag;
    int parent;
    int leftChild;
    int rightChild;
}HaffNode;
//1.
//根据权重值,构建哈夫曼树;
//{2,4,5,7}
//n = 4;
void Haffman(int weight[],int n,HaffNode *haffTree){

    int j,m1,m2,x1,x2;

    //1.哈夫曼树初始化
    //n个叶子结点. 2n-1
    for(int i = 0; i < 2*n-1;i++){

        if(I<n)
            haffTree[i].weight = weight[I];
        else
            haffTree[i].weight = 0;

        haffTree[i].parent = 0;
        haffTree[i].flag = 0;
        haffTree[i].leftChild = -1;
        haffTree[i].rightChild = -1;
    }

    //2.构造哈夫曼树haffTree的n-1个非叶结点
    for (int i = 0; i< n - 1; i++){
         m1 = m2 = MaxValue;
         x1 = x2 = 0;
        //2,4,5,7
        for (j = 0; j< n + i; j++)//循环找出所有权重中，最小的二个值--morgan
        {
            if (haffTree[j].weight < m1 && haffTree[j].flag == 0)
            {
                m2 = m1;
                x2 = x1;
                m1 = haffTree[j].weight;
                x1 = j;
            } else if(haffTree[j].weight<m2 && haffTree[j].flag == 0)
            {
                m2 = haffTree[j].weight;
                x2 = j;
            }
        }

        //3.将找出的两棵权值最小的子树合并为一棵子树
        haffTree[x1].parent = n + I;
        haffTree[x2].parent = n + I;
        //将2个结点的flag 标记为1,表示已经加入到哈夫曼树中
        haffTree[x1].flag = 1;
        haffTree[x2].flag = 1;
        //修改n+i结点的权值
        haffTree[n + i].weight = haffTree[x1].weight + haffTree[x2].weight;
        //修改n+i的左右孩子的值
        haffTree[n + i].leftChild = x1;
        haffTree[n + i].rightChild = x2;
    }

}

四、哈夫曼编码

在数据通信中，经常需要将传递的文字转换成由二进制字符0、1组成二进制串，即进行符号的二进制编码。常见的如ASCII码就是8位的二进制编码，此外，还有汉字国际码、电报明码等。

ASCII码是一种定长编码，即每个字符用相同数目的二进制位表示。为了缩短数据文件报文长度，可采用不定长编码。例如，假设要传递的报文为ABACCDA，报文中只含A、B、C、D四种字符。如下图所示：

image

a编码，报文的代码为0000 1000 0100 1001 11000，长度为21；

b编码，报文的代码为0001 0010 101100，长度为14；这两种编码均是定长编码，码长分别为3和2。

c编码，报文的代码为0110 0101 01110，长度为13；

d编码，报文的代码为0101 0010 0100 11001,长度为17；

显然，不同的编码方案，其最终形成的报文代码总长度是不同的。如何使最终的报文最短，可以借鉴哈夫曼思想，在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造的不定长编码，则报文的代码就可能达到更短。

因此，利用哈夫曼树来构造编码方案，就是哈夫曼树的典型应用。具体做法如下：设需要编码的字符集合为{d1，d2，···，dn}，它们在报文中出现的次数或频率集合为{w1，w2,···，wn}，以d1，d2，···dn为叶子结点，w1，w2,···，wn为它们的权值，构造一棵哈夫曼树，规定对哈夫曼树中的左分支赋予0，右分支赋予1，则从根结点到每个叶子结点所经过的路径分支组成的0和1序列便为该叶子结点对应字符的编码，称为哈夫曼编码，这样的哈夫曼树也称为哈夫曼编码树。

在哈夫曼编码树中，树的带全路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是报文的代码总长，所以采用哈夫曼树构造的编码是一种能使报文代码总长最短的不定长编码。

在建立不定长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，这样才能保证译码的唯一性。例如d编码方案，字符A的编码01是字符B的编码010的前缀部分，这样对于代码串0101001，既是AAC的代码，又是ABA和BDA的代码，因此，这样的编码不能保证译码的唯一性，称为具有二义性的译码。同时把满足“任意一个符号的编码都不是其他的编码的前缀”这一条件的编码称为前缀编码。

采用哈夫曼树进行编码，则不会产生上述二义性问题。因为，在哈夫曼树中，每个字符结点都是叶子结点，它们不可能在根结点到其他字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。

设ABCD出现的频率分别为0.4，0.3，0.2，0.1，则得到的哈夫曼树和二进制前缀编码如下图所示：

image

按此编码，前面的报文可转换成总长为14bit的二进制位串“01001101101110”，可以看出，这一种不定长的前缀编码能将报文唯一地无二义性地翻译成原文。当原文较长、频率很不均匀时，这种编码可使传送的报文缩短很多。当然，也可以在哈夫曼树中规定左分支表示“1”，右分支表示“0”，得到的二进制前缀编码虽然不一样，但使用效果一样。

五、哈夫曼编码算法实现

编码表存储结构：

typedef struct Code//存放哈夫曼编码的数据元素结构
{
    int bit[MaxBit];//数组
    int start;  //编码的起始下标
    int weight;//字符的权值
}Code;

哈夫曼编码的算法思路：在哈夫曼树中，从每个叶子结点开始，一直往上搜索，判断该结点是其双亲结点的做孩子还是右孩子。若是左孩子，则相应位置上的代码为0，反之为1。直到搜索到根据点为止，具体算法如下：

*
  哈夫曼编码
 由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode
 //{2,4,5,7}
 */
void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[])
{
    //1.创建一个结点cd
    Code *cd = (Code * )malloc(sizeof(Code));
    int child, parent;
    //2.求n个叶结点的哈夫曼编码
    for (int i = 0; i<n; i++)
    {
        //从0开始计数
        cd->start = 0;
        //取得编码对应权值的字符
        cd->weight = haffTree[i].weight;
        //当叶子结点i 为孩子结点.
        child = i;
        //找到child 的双亲结点;
        parent = haffTree[child].parent;
        //由叶结点向上直到根结点
        while (parent != 0)
        {
            if (haffTree[parent].leftChild == child)
                cd->bit[cd->start] = 0;//左孩子结点编码0
            else
                cd->bit[cd->start] = 1;//右孩子结点编码1
            //编码自增
            cd->start++;
            //当前双亲结点成为孩子结点
            child = parent;
            //找到双亲结点
            parent = haffTree[child].parent;
        }

         int temp = 0;

        for (int j = cd->start - 1; j >= 0; j--){
            temp = cd->start-j-1;
            haffCode[i].bit[temp] = cd->bit[j];
        }

        //把cd中的数据赋值到haffCode[i]中.
        //保存好haffCode 的起始位以及权值;
        haffCode[i].start = cd->start;
        //保存编码对应的权值
        haffCode[i].weight = cd->weight;
    }
}

数据结构与算法-线索二叉树与哈夫曼编码

数据结构与算法-线索二叉树与哈夫曼编码

一、线索化二叉树

二、哈夫曼树

三、哈夫曼树的构造算法

四、哈夫曼编码

五、哈夫曼编码算法实现

数据结构与算法-线索二叉树与哈夫曼编码

一、线索化二叉树

二、哈夫曼树

三 、哈夫曼树的构造算法

四、哈夫曼编码

五、哈夫曼编码算法实现

三、哈夫曼树的构造算法