树的存储

双亲表示法

树的存储

双亲表示法

定义结构数组
存放树的结点
每个结点含两个域

①数据域：存放结点本身信息； ②双亲域：本结点的双亲结点在数组中的位置

同时定义一个r：记录树的根的下标；n:记录树中结点的个数 n=10

结点结构C语言类型描述

typedef struct PTNode{
    TElemType data;
    int parent;        //双亲位置域
}PTNode;

树结构

#define MAX_TREE_SIZE 100
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int r,n;    //根结点的位置和结点个数
}PTree;

孩子链表表示法

特点：链表结构简单，但指针域的浪费浪费明显。在一棵有n个结点，度为k的树中必有n(k-1)+1个指针域

//孩子结点结构
typedef struct CTNode{
    int child;
    struct CTNode *next;
}*ChildPtr;

//双亲结点结构
typedef struct{
    TElemType data;
    ChildPtr firstchild;    //孩子链表头指针
}CTBox;

//树结构
typedef struct{
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;    //结点数和根结点的位置
}CTree;

孩子兄弟表示法

用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向第一个孩子结点和下一个兄弟结点

typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

树和二叉树的转换

将树转为二叉树 “孩子兄弟表示法”

二叉树的根结点没有右子树，只有左子树

①加线：在兄弟之间加一连线

②抹线：对每个结点，除了最左边的孩子之外，去除其与其余孩子之间的关系

③旋转：以树的根结点为轴心，将整树顺时针旋转45°

将二叉树转为树

森林转换为二叉树

二叉树转换为森林

树和森林的遍历

先根遍历：ABCDEFGIJHK
后根遍历：CDBFIJGHEKA

层次遍历：ABEKCDFGHIJ

二叉树的中序遍历序列结果就是树的后根遍历 / 森林的中序遍历

哈夫曼树

基本概念

结点路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径
路径长度：结点路径上的分支数目称为路径长度
树的路径长度：从树根到每一个结点的路径长度之和

结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树

权：树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权
结点的带权路径长度：从该结点的到树的根结点之间的路径长度与结点的权(值)的乘积
树的带权路径长度（WPL）：树中所有叶子结点的带权路径长度之和
Huffman树：具有n个叶子结点(每个结点的权值为wi) 的二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵WPL值最小的树，称这棵树为Huffman树(或称最优树)
最优二叉树的特点：①权值越大的结点离根结点越近； ②只有度为0和度为2的结点，不存在度为1的结点

哈夫曼树的构造

哈夫曼树的存储表示

包含n棵树的森林要经过n-1次合并才能形成哈夫曼树，共产生n-1个新结点
包含n个叶子结点的哈夫曼树中共有2n-1个结点
动态分配的一维数组；数组的0号单元不使用，从1号单元开始使用；将叶子结点集中存储在前面1-n个位置，后面的n-1个位置存储其余非叶子结点

typedef struct{
    int weight;        //结点的权值
    int parent,lchild,rchild;    //结点的双亲、左孩子、右孩子的下标
}HTNode,*HuffmanTree;

哈夫曼树的构造思想

选取森林中结点权值最小的两个根结点作为左右子树，同时权值相加作为两棵树的根结点的权值。之后比较的都是根结点的权值

哈夫曼树的构造算法

void CreateHuffmanTree(HuffmanTree HT.int n){    //构造哈夫曼树--哈夫曼算法
    if(n <= 1)    return;
    m = 2*n - 1; //数组共2n-1个元素
    HT = new HTNode[m+1];    //0号单位未用，HT[m]表示根结点
    for(i=1;i <= m;++i){    //将2n-1个元素的lch、rch、parent置为0
        HT[i].lch = 0;    HT[i].rch = 0;    HT[i].parent = 0;
    }
    for(i=1;i <= n;++i)    cin >> HT[i].weight;    //输入前n个元素的weight值
    //初始化结束，下面开始建立哈夫曼树
    for(i=n+1;i <= m;i++){    //合并产生n-1个结点---构造哈夫曼树
        Select(HT,i-1,s1,s2);    //在HT[k](1<=k<=i-1)中选择两个其双亲域为0.且其权值最小的结点，并返回它们在HT中的序号s1和s2
        HT[s1].parent=i;    HT[s2].parent=i;    //表示从F中删除s1,s2
        HT[i].lch=s1;    HT[i].rch=s2;        //s1,s2分别作为i的左右孩子
        HT[i].weight=HT[s1].weight+HT[s2].weight;    //i的权值为左右孩子权值之和
    }
}

哈夫曼编码

前缀编码：要设计长度不等的编码，必须使任一字符的编码都不是另一个字符的编码的前缀

方法：①统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）

②利用哈夫曼树的特点：权越大的叶子离根越近；将每个字符的概率值作为权值，构造哈夫曼树。概率越大的结点，路径越短

③在哈夫曼树的每个分支上标0或1：结点左分支标0，右分支标1；从根到每个叶子的路径上标号连接起来，作为该叶子代表的字符的编码

字符出现的频率也可以认为其是权值

哈夫曼编码是最优前缀码

哈夫曼树的算法实现

从叶子结点逆着开始，之后再倒序，实现哈夫曼编码

编码最多有n-1位

void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC.int n){
    //从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
    HC = new char*[n+1];    //分配n个字符编码的头指针矢量
    cd = new char[n];       //分配临时存放编码的动态数组空间
    cd[n-1] = '\0';         //编码结束符
    for(i=1; i<=n;++i){    //逐个字符求哈夫曼编码
        strat=n-1; c=i; f=HT[i].parent;
        while(f!=0){        //从叶子节点开始上溯，直到根结点
            --start;        //回溯因此start向前指一个位置
            if(HT[f].lchild == c)    cd[start] = '0';    //结点c是f的左孩子，生成代码0
            else    cd[start] = '1';        //结点c是f的右孩子，生成代码1
            c=f;f = HT[f].parent;        //继续向上回溯
        }
        HC[i] = new char[n-start];        //为第i个字符串编码分配空间
        strcpy(HC[i],&cd[start]);         //将求到的编码从临时空间cd复制到HC的当前行中
    }
    delete cd;        //释放临时空间
}