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

---

回顾

• 二叉树的遍历方式：
  • 前序遍历（根 -> 左子树 -> 右子树）
  • 中序遍历（左子树 -> 根 -> 右子树）
  • 后序遍历（左子树 -> 右子树 -> 根）

提要

1. 线索二叉树的定义；
2. 线索二叉树的建立与相关操作；
3. 哈夫曼树；
4. 哈夫曼编码及应用。

问题的引出

问题：n个结点的二叉树，有多少个空指针？
分析：每个结点均有2个指针域，则n个结点的二叉树共有 2n 个指针域。
除根结点外，二叉树中每一个结点均由一个指针域指向，则n个结点的二叉树使用了n - 1个指针域。
空指针数目 = 2n - (n - 1) = n+1
由此可见，二叉链表空间利用率较低。

中序遍历序列为：B D C E A F H G
则中序遍历时A结点的前驱为E，后继为F。
普通二叉树只能找到结点的左、右孩子信息，而结点的前驱和后继只能在遍历过程中获得。
可以利用 n+1 个空指针域保存遍历序列中的前驱和后继的信息，从而提高遍历过程的效率。

结点的改造

为了避免混淆，给结点增加两个标志域（ltag和rtag），用于区分指针域是指向真实结点还是线索。

线索二叉树

线索二叉树是利用空指针域保存遍历序列中的前驱和后继信息的二叉树，线索化后的二叉树可以提高遍历过程的效率。
指示遍历序列中前驱和后继的指针域称为线索；
对二叉树以某种次序遍历，创建线索的过程称为线索化。
线索化之后的二叉树称为线索二叉树；
如果分别按中序、前序、后序遍历，则可得到：
中序线索二叉树
前序线索二叉树
后序线索二叉树

示例

画出以下二叉树对应的中序线索二叉树。
该二叉树中序遍历结果为: D, G, B, A, E, C, F

中序遍历结果为: D, G, B, A, E, C, F

线索二叉树的创建和遍历

1.定义线索二叉树结点

enum Tag {Link, Thread};  // 标记枚举类型，Link表示指向孩子，Thread表示线索

struct ThreadNode {
    char data;              // 结点数据域
    Tag ltag, rtag;          // 左右标记域
    struct ThreadNode *lchild, *rchild;  // 左右孩子或线索
};

typedef struct ThreadNode BiTNode;  // 定义线索二叉树结点类型
1
2
3
4
5
6
7
8
9

2.初始化头结点

BiTNode* InitThreading() {
    BiTNode* head = new BiTNode;
    head->ltag = Thread;
    head->rtag = Link;
    head->lchild = NULL;
    head->rchild = NULL;
    return head;
}
1
2
3
4
5
6
7
8

3.中序线索化函数

void InOrderThreading(BiTNode* &head, BiTNode* p) {
    if (p != NULL) {
        InOrderThreading(head, p->lchild);  // 递归线索化左子树

        if (p->lchild == NULL) {  // 无左孩子，指向前驱
            p->ltag = Thread;
            p->lchild = head->rchild;
        }
        if (head->rchild != NULL && head->rchild->rtag == Thread) {  // 前驱无右孩子，指向当前结点
            head->rchild->rtag = Link;
        }

        InOrderThreading(head, p->rchild);  // 递归线索化右子树

        if (p->rchild == NULL) {  // 无右孩子，指向后继
            p->rtag = Thread;
            p->rchild = head->rchild;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.创建二叉树并线索化

void CreateBiTree(BiTNode* &p, char data[]) {
    p = new BiTNode;
    p->data = data[0];
    p->ltag = p->rtag = Link;
    p->lchild = p->rchild = NULL;
    int k = 2;  // 从索引2开始为左孩子
    if (data[k] != '#') {
        CreateBiTree(p->lchild, data);  // 递归创建左子树
        k++;
    }
    if (data[k] != '#') {
        CreateBiTree(p->rchild, data);  // 递归创建右子树
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5.中序遍历线索二叉树

void InOrderTraverse(BiTNode* head) {
    BiTNode* p = head->rchild;  // 从头结点的最右结点开始
    while (p != NULL) {
        if (p->rtag == Link) {
            cout << p->data << " ";  // 访问结点
            p = p->rchild;  // 继续访问右子树
        } else {
            p = p->rchild;  // 否则继续访问后继结点
        }
    }
    cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12

6.主函数示例

int main() {
    char data[] = {'A', 'B', '#', '#', 'D', 'G', '#', '#', 'E', 'C', '#', '#', 'F', NULL};
    BiTNode* head = InitThreading();  // 初始化头结点
    CreateBiTree(head->rchild, data);  // 创建二叉树
    InOrderThreading(head, head->rchild);  // 中序线索化
    InOrderTraverse(head);  // 中序遍历线索二叉树
    return 0;
}
1
2
3
4
5
6
7
8

中序线索二叉树存储结构

在中序遍历结果的基础上增设一个头结点，使得遍历更加方便。

线索化的过程

1. 以某种遍历次序遍历二叉树。
2. 检查结点的左右指针域是否为空。
3. 将空的左指针域改为指向前驱的线索，空的右指针域改为指向后继的线索。
4. 如果右指针域为空，将这个右指针域改为指向该结点后继的线索。

线索二叉树节点类型描述

线索二叉树的节点除了包含数据域外，还需要两个指针域（分别指向左右孩子或线索），以及两个标记域（区分指针是孩子还是线索）。

struct ThreadNode {
    char data;               // 数据域
    ThreadNode *left;        // 左孩子或左线索
    ThreadNode *right;       // 右孩子或右线索
    bool ltag, rtag;         // 左右标记，true 表示线索，false 表示孩子
};
1
2
3
4
5
6

中序线索化的实现

中序线索化的过程需要递归地遍历二叉树，并在适当的时候添加线索。

void InOrderThreading(ThreadNode *&head, ThreadNode *node) {
    if (node != nullptr) {
        InOrderThreading(head, node->left);  // 线索化左子树

        if (node->left == nullptr) {  // 无左孩子，添加前驱线索
            node->left = (head != nullptr && head->right != node) ? head->right : nullptr;
            node->ltag = true;
        }

        if (head != nullptr && head->right == node && head->left == nullptr) {
            head->left = node->right;  // 头结点的左线索指向node的右孩子
            head->ltag = true;
        }

        InOrderThreading(head, node->right);  // 线索化右子树

        if (node->right == nullptr) {  // 无右孩子，添加后继线索
            node->right = head;
            node->rtag = true;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

查找任意节点p的中序前驱

中序遍历中，一个节点的前驱是其在中序序列中的前一个节点，可以通过线索快速找到。

ThreadNode* FindInOrderPredecessor(ThreadNode* p) {
    if (p->ltag) {  // 如果左线索存在，直接通过线索找到前驱
        return p->left;
    } else {
        ThreadNode* temp = p->left;  // 否则，前驱是最右边的左子树节点
        while (temp->rtag == false) {
            temp = temp->right;
        }
        return temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11

查找任意节点p的中序后继

中序遍历中，一个节点的后继是其在中序序列中的下一个节点，同样可以通过线索快速找到。

ThreadNode* FindInOrderSuccessor(ThreadNode* p) {
    if (p->rtag) {  // 如果右线索存在，直接通过线索找到后继
        return p->right;
    } else {
        ThreadNode* temp = p->right;  // 否则，后继是最左边的右子树节点
        while (temp->ltag == false) {
            temp = temp->left;
        }
        return temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11

建立中序线索二叉树

使用全局变量pre指向刚刚访问过的结点，p指向当前线索化的结点，通过递归实现中序线索化。
以中序遍历为例，建立中序线索二叉树。

• 在遍历过程中，设定p和pre用于保存相应位置:
  • p：总是指向当前线索化的结点。
  • pre：作为全局变量，指向刚刚访问过的结点。
  • pre是p的中序前驱结点；
  • p是pre的中序后继结点。
  • 

线索二叉树的结点类型描述

定义线索二叉树结点类型，包含数据域、左右标记和左右线索指针。

typedef struct node {
    ElemType data;
    int ltag; // 左标记
    int rtag; // 右标记
    struct node *left;  // 左孩子或线索指针
    struct node *right; // 右孩子或线索指针
} TBTNode; // 线索树结点类型定义
1
2
3
4
5
6
7

中序线索化的实现

实现中序线索化函数，包括建立头结点、递归中序线索化和处理边界情况。

查找任意结点的中序前驱和后继

提供查找中序前驱和后继的函数，利用线索快速定位。

• 若p的ltag为1，则p的left为线索，指向p的前驱；
• 若p的ltag为0，则p的前驱为p的左子树的“最右结点”。
• 
• 若p的rtag为1，则p的right为线索，指向p的后继；
• 若p的rtag为0，则p的后继为p的右子树的“最左结点”。
• 

哈夫曼树

定义

哈夫曼树（最优二叉树）是带权路径长度WPL最小的二叉树。

• 结点的权：将树中结点赋予一个有某种意义的数值。

• 设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度 li 与相应结点权值 wi 的乘积之和，称为二叉树的带权路径长度：
  

• 带权路径长度WPL最小的二叉树称为哈夫曼树（最优二叉树）(WPL: Weighted Path Length)。

• 

构造哈夫曼树

根据哈夫曼树的定义，二叉树要使WPL值最小，则：

• 权值越大的叶子结点越靠近根结点；
• 而权值越小的叶子结点越远离根结点。
  构造哈夫曼树的步骤：

1. 构造n棵只有一个叶子结点的二叉树，形成集合。
2. 选取权值最小的两棵树作为新树的左右子树，权值相加为根结点权值。
3. 重复以上步骤，直到集合中只剩下一棵树。
4. 给定权值w=(7,2,8,4)，构造哈夫曼树的方法如下:
5. 
6. 由给定的n个权值{W1,W2,…,Wn}构造n棵只有一个叶子结点的二叉树，从而得到一个二叉树的集合F={T1,T2,…,Tn}；
7. 在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，新的二叉树根结点的权值为其左、右子树根结点权值之和；
8. 在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；
   重复7、8两步，当F中只剩下一棵二叉树时，这棵二叉树即为要建立的哈夫曼树。
   
   
   

哈夫曼编码

哈夫曼编码是一种不等长编码方式，根据字符出现频率设计编码，使得总的电文长度最短。

若需电文总长尽可能短，可对每个字符设计长度不等的编码，且让出现次数较多的字符采用尽可能短的编码。

因此，若要设计不等长编码，则必须是任一个字符的编码都不能是另一个字符的编码的前缀。
以电文中出现的字符作为叶子结点，以该字符在电文中出现的频率作为该叶子的权值，构造哈夫曼树。
规定哈夫曼树中的左分支为0，右分支为1。
从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的哈夫曼编码。
哈夫曼编码的特点：权值越大的字符编码越短，反之越长。

总结

• 二叉树的线索化过程；
• 哈夫曼树的构造与哈夫曼编码。

---