Study-Journal

树和二叉树

---

5.3 遍历二叉树和线索二叉树

5.3.1 遍历二叉树

二叉树的存储结构：二叉链表

• 先序遍历 – 父、左、右

• 中序遍历 – 左、父、右

• 后序遍历 – 左、右、父

根据先序遍历、中序遍历，可以快速判断后序遍历的开头和结果辅助推导

5.3.2 遍历算法应用

本质都是递归遍历的应用

1. 建立二叉树

• 自根 root 进入，先序遍历递归，建立二叉链表

  • 取得新结点

  • 递归新结点的左结点

  • 递归新结点的右结点

• 约定空结点标记，如 # 为递归出口

2. 计算二叉树中的结点总数

int NodeCount(BiTNode T) {
    if (T == null) return 0;
    else return NodeCount(T->rChild) + NodeCount(T->lChild) + 1;
}

• 左子树结点数 + 右子树结点数

• +1 – 加总自己

• 递归边界为扫描到子结点是空值

3. 叶子结点总数

仅改为当且仅当双子结点为空时返回 1

if (T->rChild == null && T->lChild == null) return 1;

4. 计算二叉树的深度

返回子树的深度 +1

5. 复制二叉树 – 略

5.3.3 线索二叉树

普通二叉树只能找到左右孩子信息，该结点的直接前驱和直接后继只能在遍历过程中获得

n 个结点的二叉链表中有 n+1 个空指针域，利用其存储前驱后继关系

添加标志域

LTag 和 RTag

• 有对应方向孩子时指向对应孩子

• 否则（空指针域）分别指向前驱或后继线索

利用空指针域额外存储前项后项，使遍历过程携带的数据更为丰富

分类

根据所加线索信息类型的不同，分为

• 前序线索二叉树

• 中序线索二叉树

• 后序线索二叉树

线索：指向前驱后继的指针

线索二叉树：加上线索信息的二叉树

例：遍历中序线索二叉树

• 查找 p 指针对应结点前驱

  • p->LTag==1：左指针指向前驱

  • p->LTag==0：p 有左子树，结点的前驱是遍历左子树最后访问的结点（左子树最右下的结点）

• 查找 p 指针对应结点后继

  • p->RTag==1：右指针指向后继

  • p->RTag==0：p 有右子树，结点的前驱是遍历右子树最后访问的结点（右子树最左下的结点）

// 中序遍历二叉线索树的非递归且直接输出写法
p = T->lChild;
while (p != T) {
    while (p->LTag == 0) p = p->lChild;
    cout << p->data;
    while (p->RTag == 1 && p->RTag != T) {
        p = p->rChild;
        cout << p->data;
    }
    p = p->rChild;
}

---

5.4 树和森林

5.4.1 树的存储结构

• 双亲表示法 – 每结点后存储双亲的下标

• 孩子表示法 – 邻接链表，存储结点的每个孩子

• 孩子兄弟表示法

  又名二叉树表示法、二叉链表表示法

  • 结点的两个链域分别存储第一个孩子和下一个兄弟的指针

  • 其存储形成唯一二叉树，即完成了树到二叉树的转换

  特点：从树转化来的二叉树的根结点没有右子树

5.4.2 森林和二叉树的转换

把第二棵树的根结点作为第一棵树形成的二叉树的右结点

因此森林转换来的二叉树就拥有了左右子树

根据右子树数量可以判断由多少棵树转化而来

5.4.3 树和森林的遍历

1. 树的遍历

• 先根遍历 – 先根，后子树

  • 树的先根遍历的结果和二叉化树的先序遍历结果一致

• 后根遍历 – 先子树，后根

  • 树的后根遍历的结果和二叉化树的中序遍历结果一致

• 按层次遍历 – 自上而下自左至右

每层孩子数量不固定，也因此树不存在中根遍历

2. 森林的遍历

• 先根遍历 – 同样和二叉化森林的先序遍历一致

• 后根遍历 – 同样和二叉化森林的中序遍历一致

• 按层次遍历

---

5.5 Huffman 树及其应用

5.5.1 Huffman 树的基本概念

又称最优树，属于一种带权路径长度最短树

判定树：描述 Y/N 分类过程的二叉树

Huffman 树就是效率最高的判定树

路径：结点到另一结点间的分支所构成

路径长度：路径上的分支数目

带权路径长度：结点到根的路径长度与权的乘积

树的带权路径长度：所有叶子节点的带权路径长度之和 $WPL=\sum w_kl_k$

Huffman 树：构造出的 $WPL$ 最小的二叉树，又称最优二叉树

1. 构造

构造出的 Huffman 树可能不唯一

• $n$ 个权值构造 $n$ 棵只有跟节点的二叉树，形成森林 $F$

• 选取两个跟结点权值最小的树作为左右子树构造新的二叉树，置新的二叉树的根结点的权值为左右子树上根结点的权值之和

  • 注意实时更新节点和双亲

• 在 $F$ 删除两颗老树，把新树加入 $F$ 中

• 重复选取，直到 $F$ 只剩一棵树，这棵树就是 Huffman 树

Huffman 树的结点维度只会是 $0$ 或 $2$

因此 $n$ 个叶子结点的 Huffman 树中有 $2n-1$ 个结点

2. 实现

#define N 叶子结点数
void CreateHuffmanTree(HuffmanTree &HT, int n) {
    if (n <= 1) return;
    m = n << 1 + 1;
    HT = new HTNode[m + 1];
    for (int i = 1; i <= m; i ++) {
        HT[i].lchild = 0;
        HT[i].rchild = 0;
        HT[i].parent = 0;
    }

    for (int i = 1; i <= n; i ++) {
        cin >> HT[i].weight; 
    }

    for (int i = 1; i <= m; i ++) {
        Select();
        HT[s1].parent = i;
        ht[s2].parent = i;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}

5.5.2 Huffman 编码

1. 电文编码问题

原文 -> 电文（二进制） -> 原文

如 ABACCDA

• 为每一个字符定义等长编码替换？——有没有办法用更短的编码长度解决？

• 不等长编码？——接受方无法逆向（译码不唯一）

2. 编码唯一性问题

• 最小冗余编码

• 唯一性编码

  • 前缀编码：每一字符的编码都不是另一字符编码的前缀

Huffman 编码：最优前缀编码

3. 编码过程

• 根据每种编码出现概率作为叶子结点构造 Huffman 树

• 左孩子分支赋权 $0$，右孩子分支赋权 $1$

• 最终，每种概率到根结点练成的路径就是其 Huffman 编码

void CreateHuffmanNode(HuffmanTree HE, HuffmanCode &HC, int n) {
    HC = new char* [n + 1];
    cd = new char[n];  // 临时编码申请空间
    cd[n - 1] = '0';
    for (int i = 1; i <= n; i ++) {
        start = n - 1;
        c = i; f = HT[i].parent;
        while (f != 0) {
            start --;  // 前移
            if (HT[f].lchild = c) cd[start] = '0';
            else cd[start] = '1';
            c = f; f = HT[i].parent;  // 重复
        }
        HC[i] = new char[n - start];
        strcpy(HC[i], &cd[start]);
    }
    delete cd;  // 释放空间
}

4. 译码过程

从根开始

• 0：向左

• 1：向右

直到走到叶子结点，译出一个字符

重复直到电文结束

5. 关于 Huffman 编码的几个结论

• 是不等长编码

• 属于前缀编码

• 没有度为 1 的结点，结点个数是叶子结点个数的二倍减一

以下并查集内容略