⇧
❮
❯
↻
🍀计算机基础🍀 10616字 54分钟

数据结构强化笔记（6）：树与二叉树

作者

本文介绍树与二叉树。

Hyplus目录

1 树的基本概念

树（Tree）：含有n\ (n≥0)个结点的非线性结构，当n=0时，称为空树；非空树有且仅有一个称为根（Root）的特殊结点；当n>1时，非根结点可分成m\ (m>0)个互不相交的有限集，称为子树。

相关术语：

  • 结点的度（Degree）：结点的⼦树个数（注意与图中顶点的度区分）
  • 树的度：树的所有结点中最⼤的度数

    【辨析】度为m的树与m叉树的区别？

    • 度为m的树：客观存在⾄少有⼀个度为m的结点，因此必定非空
    • m叉树：⼈为规定结点可有的最⼤度数为m，因此可以不存在度为m的结点，甚至可以为空
  • 叶结点（Leaf）：度为0的结点。与之相对的是非叶结点（分枝结点）
  • 父结点（Father，又称双亲结点，Parent）：有⼦树的结点是其⼦树根的⽗结点
    • 所有非根结点有且只有1个父结点
  • ⼦结点（Child, Son）：若A是B的⽗结点，则B是A的⼦结点
  • 兄弟结点（Sibling）：具有同⼀⽗结点的各个结点互为兄弟结点
  • 祖先结点（Ancestor）：沿树根到某⼀结点路径上的所有结点为该结点的祖先
  • ⼦孙结点（Descendant）：某⼀结点的⼦树中的所有结点为该结点的⼦孙
  • 层次：从根开始算，根为第1层，根的孩⼦为第2层，逐级递推（有时亦设定根为0层）
  • 树的⾼度/深度：树中结点的最⼤层次
  • 结点的深度：从根结点开始⾃顶⽽下逐层增加
  • 结点的⾼度：从叶结点开始⾃底⽽上逐层增加

2 树的重要理论性质

树的理论性质（适用于任何树）：

  1. 树的结点数等于分支数 + 1，即|V|=|E|+1

    m棵树的森林有k条边（分支），则这m棵树共有m+k个结点

  2. 树的结点数等于所有结点度数之和 + 1，即|V|=\sum\limits_i \text{TD}(v_i)+1

    其中\text{TD}(v)表示顶点v的度数，详见“图”

  3. m叉树的结点数=n_0+n_1+n_2+\cdots+n_m
  4. m叉树的分支数=n_1+2n_2+\cdots+mn_m

    其中n_i表示度为i的结点的个数

  5. 度为m的树的第i层上：至多有m^{i-1}个结点

    满二叉树的第i层上有2^{i-1}个结点

  6. 高度为h的m叉树：至多有\dfrac{m^h-1}{m-1}个结点

    【推导】等比数列求和S=m^{h-1}+m^{h-2}+\cdots+m+1=\dfrac{m^h-1}{m-1}

  7. 具有n个结点的m叉树的最小高度：h_{\min}=\left \lceil \log_{m} (n(m-1)+1) \right \rceil
  8. 部分最⼩⾼度问题：树越胖越矮，越矮越胖。每层顶点分布尽可能多，故满⼆叉树最矮；⾼度越⼩时，每层顶点分布数越多，就越宽
  9. 部分最⼤⾼度问题：树越瘦越⾼，越⾼越瘦。与上同理

3 二叉树

⼆叉树（Binary Tree）：⼀种特殊的有序树，要么为空树，要么每个结点最多只有两棵⼦树，即结点的度只能为0,1,2，子树严格区分左右顺序。

⼆叉树具有5种基本形态：

【辨析】⼆叉树与⼀般的每个结点⾄多有两棵⼦树的有序树的区别？

如果有序树中的⼦树只有⼀个孩⼦时，这个孩⼦结点就⽆须区分其左右次序；⽽⼆叉树中的孩⼦⽆论如何都明确区分左、右！

特殊⼆叉树：

  • 满⼆叉树（Full Binary Tree）：所有分⽀结点都有左右孩⼦，叶结点集中在最后⼀层，且含有2^h-1个结点（h为高度）

  • 完全⼆叉树（Complete Binary Tree，CBT）：由满⼆叉树从右⾄左、从下⾄上修剪⽽来，结点特征为都尽可能靠上、靠左集中，因此适合⽤顺序存储结构（⼀维数组）存储

3.1 ⼆叉树的重要性质

⼆叉树的特有性质：

  1. 二叉树中度的性质：n_0=1+n_2
    • 推广至m叉树：n_0=1+n_2+2n_3+\cdots+(m-1)n_m
    • 由定义可知，完全二叉树中n_1≤1
  2. 非空二叉树的第i层上：至多有2^{i-1}个结点
  3. 高度为h的二叉树：至多有2^h-1个结点，即为满二叉树时

    以上两条均为非空m叉树的特例；\dfrac{2^h-1}{2-1}=2^{h}-1

  4. 具有n个结点的完全⼆叉树的⾼度：h=\left \lceil \log_2 (n+1) \right \rceil = \left \lfloor \log_2 n \right \rfloor + 1
  5. 对完全⼆叉树从上到下、从左到右顺次编号1,2,\cdots,n，根结点为第1层，则对编号为i的结点：
    1. 非叶结点：i≤\left \lfloor \dfrac{n}{2} \right \rfloor
      • 编号最⼤的⾮叶结点：\left \lfloor \dfrac{n}{2} \right \rfloor，在其之后均为叶结点
      • 由此可得完全二叉树叶结点个数公式：n-\left \lfloor \dfrac{n}{2} \right \rfloor
    2. 由结点i反推其他属性：
      • 双亲结点：\left \lfloor \dfrac{i}{2} \right \rfloor(i>1)
      • 左孩子：2i(2i≤n)
      • 右孩子：2i+1(2i+1≤n)
      • 结点i所在层次：\left \lfloor \log_2 i \right \rfloor + 1

        若层次编号从\text{0}开始，则为\left \lfloor \log_2 (i+1) \right \rfloor + 1

    3. 若n为奇数，则每个分支结点都有左右孩子
    4. 若n为偶数，则编号最⼤的⾮叶结点\left \lfloor \dfrac{n}{2} \right \rfloor只有左孩子，没有右孩子，其余分⽀结点都有左右孩⼦

      变式：从0开始编号时依旧可推出左右孩⼦，在原有结论上+1即可

3.2 ⼆叉树的存储结构

孩子存储结构：二叉树的顺序存储结构，对⼆叉树按从上到下、从左到右顺序依次编号，使⽤顺序表（⼀维数组）直接存储，通常从下标1开始存储结点

  • 缺点：存储普通⼆叉树会造成⼤量空间浪费（不存在的孩⼦需补0）
  • 优点：⾮常适合存储完全⼆叉树，特别是堆（详见“排序”），可根据下标快速推算出结点在⼆叉树中的位置
#define MAXSIZE 1010
int SqBiTree[MAXSIZE];

⼆叉链表存储结构：二叉树的链式存储结构，使用二叉链表存储信息，优劣与单链表相同，也可追加双亲指针变成三叉链表

  • 性质：n个结点的二叉链表中，含有n+1个空链域（空指针，空分枝）

    计算过程：由每个叶结点有2个空指针、每个度为1的结点有1个空指针，得空指针总数为2n_0+n_1；又由n_0=1+n_2，可得空指针数=n_0+n_1+n_2+1=n+1\ (n_0+n_1+n_2=n)

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

【拓展】为了易于使用，实际应用中还常直接采用链式前向星实现二叉链表（参考2.B“链式前向星”）：

int l[N], r[N], idx;
// 二叉链表存储结构：l[k]、r[k]分别存储结点k的左右孩子
// idx初始为0，指向下一个结点可用地址

3.3 ⼆叉树的遍历

首先简要介绍递归函数的若干基础知识：

  1. 只有1个递归入口的情况
int i = 0;

void r() {
    if (i < 3) {
        i++;
        r();
    }
}
  1. 有2个递归入口的情况【重点】
int i = 0;

void r() {
    if (i < 2) {
        i++;
        r();
        r();
    }
}

递归函数原理：使用系统工作栈实现保护现场、恢复现场

3.3.1 二叉树DFS与BFS

深度优先遍历（DFS）：分为先序遍历（NLR）、中序遍历（LNR）、后序遍历（LRN）等（此处的“序”指的是根结点（N）在何时被访问，实际还可有RNL、NRL等变形次序遍历）

  • 性能：T(n)=O(n)，S(n)=O(n)（使用了递归工作栈）
/* 二叉树的递归版先序、中序、后序遍历示例，其中visit()为预定义的访问函数 */
void dfs(BiTree T) {
    if (T) {
        // visit(p);        // 先序遍历
        DFS(T->lchild);
        // visit(p);        // 中序遍历
        DFS(T->rchild);
        // visit(p);        // 后序遍历
    }
}

层序遍历（Level Order）：对⼆叉树从左⾄右、从上⾄下依次遍历，相当于对⼆叉树编号的顺序

  • 性能：T(n)=O(n)，S(n)=O(n)（使用了队列）
/* 二叉树的层序遍历 */
void levelOrder(BiTree T) {
    Queue Q;    // 辅助队列
    initQueue(Q);
    BiTNode *p = T; // 遍历指针，初始指向根结点
    push(Q, p); // 根结点⼊队
    while (!isEmpty(Q)) {   // 循环条件：队列⾮空
        pop(Q, p);  // 队⾸出队（并执行其他操作）
        visit(p);
        if (p->lchild) push(Q, p->lchild);  // 左孩⼦⾮空则⼊队
        if (p->rchild) push(Q, p->rchild);  // 右孩⼦⾮空则⼊队
    }
}

【总结与归纳】⼆叉树DFS、BFS的性质：

  • 对不同的遍历序列，相对次序发⽣变化的都是⼦树的根，即分⽀结点，叶结点的相对次序不变！
  • 通过遍历实现各种操作：
    1. ⾮递归求⾼度与宽度问题、判断完全⼆叉树：层次遍历
    2. 祖先路径问题：后序⾮递归
    3. 求叶结点数、求⾼度：先序遍历（⽆限制就⽤递归版，容易书写）
    4. 层次遍历反转、Z型遍历（PAT甲级例题）：栈 + 队列，改造层次遍历

3.3.2 DFS非递归化

⾮递归化⽅法：使⽤栈来模拟递归⼯作栈的作⽤

  1. 中序⾮递归：设置初始指向根结点的遍历指针p
    • 算法步骤：在栈⾮空或当前所指⾮空时循环——
      1. 当前所指⾮空时⼊栈、往左⾛
      2. 为空时则栈顶元素出栈并接收，访问它、往右⾛
    • 特点：中序⾮递归的辅助栈栈顶结点为当前所指结点的⽗结点
void inOrder(BiTree T) {
    Stack S;    // 辅助栈
    initStack(S);
    BiTNode *p = T; // p为遍历指针，初始指向根结点
    while (p || !isEmpty(S)) {  // 循环条件：p⾮空或栈⾮空
        if (p) {    // p⾮空时：p⼊栈，⼀路沿左⾛
            push(S, p);
            p = p->lchild;
        } else {    // p为空时：栈顶出栈，访问之，再往其右孩⼦⾛
            pop(S, p);
            visit(p);
            p = p->rchild;
        }
    }
}
  1. 先序⾮递归：与⾮递归中序⼏乎⼀致，将访问时机提前⾄p所指⾮空时第⼀步即可
void preOrder(BiTree T) {
    Stack S;
    initStack(S);
    BiTNode *p = T;
    while (p || !isEmpty(S)) {
        if (p) {
            visit(p);   // 先序变化：⼀开始就"先"访问
            push(S, p);
            p = p->lchild;
        } else {
            pop(S, p);
            p = p->rchild;
        }
    }
}
  1. 后序⾮递归：除了遍历指针p外，还增设⽤于标记上⼀次访问的结点的标记指针r。
    • 算法流程：同中序非递归，在栈⾮空或当前所指⾮空时循环
      1. 同中序非递归，当前所指⾮空时⼊栈、往左⾛
      2. 为空时读取栈顶结点先不出栈，若存在右⼦树且不是上⼀次访问过的结点r则往右走，否则此时再出栈，访问它、更新标记指针r、重置遍历指针p为空
    • 特点：后序⾮递归的栈内全部结点实为当前所指结点的全部祖先（栈顶至底恰好为由近至远顺序）
void postOrder(BiTree T) {
    Stack S;    // 辅助栈中元素恰好为p所指结点的全部祖先
    initStack(S);
    BiTNode *p = T, *r = NULL;  // r标记上⼀次访问过的结点
    while (p || !isEmpty(S)) {
        if (p) {
            push(S, p);
            p = p->lchild;
        } else {    // p为空时：检查右孩⼦
            getTop(S, p);
            if (p->rchild && p->rchild != r) {  // 若右孩⼦未被遍历，则往右⾛（若存在）
                p = p->rchild;
            } else {    // 否则正常执⾏栈顶出栈，访问之，更新指针
                pop(S, p);
                visit(p);
                r = p;  // 更新记录指针r为刚访问过的p
                p = NULL;   // p置空！
            }
        }
    }
}

注：为便于正向、反向遍历，实际应⽤时常直接使⽤数组现场定义简单栈、⾮循环队列

3.3.3 ⼆叉树的确定

设先序、中序、后序遍历子序列分别为pre[preL...preR]、in[inL...inR]、post[postL...postR]，由“先序和中序”或“后序和中序”确定⼆叉树的通用方法如下：

  1. 根：先序的首元素pre[preL] / 后序的尾元素post[postR]
  2. 左右子树：中序对应的根位k两侧的左、右子区间（不含k）分别为左右子树；同时可在先/后序中标出这两段子树区间，统一左子树在左、右子树在右
  3. 子树根：回到先/后序，站在根处看向剩余序列，两段子树区间离根最近的结点即为⼦树根

代码化要点：注意递归⼊⼝参数表区间⻓度⼀致；可事先建立“先/后序 → 中序”的结点位置映射表，将顺序查找替换为哈希

/* 由先序和中序序列确定⼆叉树 */
BiTNode *build1(ElemType pre[], int preL, int preR, ElemType in[], int inL, int inR) {
    BiTNode *root = (BiTNode*) malloc(sizeof BiTNode);  // 建⽴⼦树根结点
    root->data = pre[preL]; // 赋值为先序序列⾸元素

    int k;  // k记录根在中序序列中对应的位置
    for (k = inL; k <= inR && in[k] != root->data; k++);    // 在中序序列中顺序查找（或改为哈希映射）

    if (inL < k)    // 递归构建左⼦树
        root->lchild = build1(pre, preL + 1, preL + 1 + (k - 1 - inL), in, inL, k - 1);
    else
        root->lchild = NULL;

    if (k < inR)    // 递归构建右⼦树
        root->rchild = build1(pre, preL + 1 + (k - 1 - inL) + 1, preR, in, k + 1, inR);
    else
        root->rchild = NULL;

    return root;
}
/* 由后序和中序序列确定⼆叉树 */
BiTNode *build2(ElemType post[], int postL, int postR, ElemType in[], int inL, int inR) {
    BiTNode *root = (BiTNode*) malloc(sizeof BiTNode);
    root->data = post[postL];   // 赋值为后序序列尾元素

    int k;
    for (k = inL; k <= inR && in[k] != root->data; k++);

    if (inL < k)
        root->lchild = build2(post, postL, postL + (k - 1 - inL), in, inL, k - 1);
    else
        root->lchild = NULL;

    if (k < inR)
        root->rchild = build_2(post, postL + (k - 1 - inL) + 1, postR - 1, in, k + 1, inR);
    else
        root->rchild = NULL;

    return root;
}

仅靠“前序和后序”序列无法唯一确定⼆叉树，但可以确定部分信息：

  • 确定祖先关系：当结点v_1,v_2在前序、后序序列中顺序相反（前序中v_1在v_2之前，后序中v_2在v_1之前）时，v_1为v_2的祖先
  • 前序与后序序列正好相反的⼆叉树只有⼀个叶⼦（例如单分⽀⼆叉树）

3.4 线索⼆叉树

线索⼆叉树（Thread Binary Tree，TBT）：树的⼀种特殊的存储结构。追加两个线索标记ltag、rtag，通过某种遍历序列，利⽤空的孩⼦指针（空分支，图示中常用^表示）将⼆叉树中每⼀个结点排成⼀个线性序列，类似于双链表，除头尾外都有⼀个直接前驱和直接后继。此时该孩⼦指针被称为线索

  • ltag == 0：lchild指向结点的左孩子；ltag == 1：lchild指向结点的前驱
  • rtag == 0：rchild指向结点的右孩子；rtag == 1：lchild指向结点的后继
typedef struct TBiTNode {
    ElemType data;
    struct TBiTNode *lchild, *rchild;
    int ltag, rtag; // 左、右线索标记
} TBiTNode, *TBiTree;   // 线索链表存储结构

核⼼操作——根据深度优先遍历序列建⽴线索：需要的辅助变量包括遍历指针p与前驱指针pre（初始为空，建⽴前驱结点的后继线索前需判断非空），其中前序线索化时递归⼊⼝前需特判⾮线索

/* 中序线索化 */
void inThread(TBiTNode *p, TBiTNode *&pre) {
    if (p) {
        inThread(p->lchild, pre);

        if (!p->lchild) {   // 建⽴前驱线索
            p->lchild = pre;
            p->ltag = 1;
         }
        if (pre && !pre->rchild) {
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;

        inThread(p->rchild, pre);
    }
}
/* 先序线索化，注意特判⾮线索 */
void preThread(TBiTNode *p, TBiTNode *&pre) {
    if (p) {
        if (!p->lchild) {   // 建⽴前驱线索
            p->lchild = pre;
            p->ltag = 1;
         }
        if (pre && !pre->rchild) {  // 建⽴前驱结点的后继线索，注意pre需⾮空
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;

        if (p->ltag == 0) preThread(p->lchild, pre);    // 为避免出现死循环，
        if (p->rtag == 0) preThread(p->rchild, pre);    // 禁止走线索。
    }
}
/* 后序线索化 */
void postThread(TBiTNode *p, TBiTNode *&pre) {
    if (p) {
        postThread(p->lchild, pre);
        postThread(p->rchild, pre);

        if (!p->lchild) {   // 建⽴前驱线索
            p->lchild = pre;
            p->ltag = 1;
         }
        if (pre && !pre->rchild) {  // 建⽴前驱结点的后继线索，注意pre需⾮空
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
    }
}

三种DFS线索⼆叉树的常用操作：

  • 中序线索⼆叉树——找前驱、后继都方便
    • first(p)（求⼦树中第⼀个结点）：从根结点往左⼀直⾛直⾄左指针为左线索，即为序列第⼀个结点
    • last(p)（求子树中最后一个结点）：同上，改成往右⼀直⾛并遇⻅右线索

      联系中序⾮递归流程中"当前所指⾮空"时⼀直左⾛的操作！

    • next(p)（求结点的后继）：若右指针⾮线索，则返回其所指的右⼦树的第⼀个结点；否则直接返回右线索所指的后继
    • prior(p)（求结点的前驱）：同时，改成左指针所指的左子树的最后一个结点；否则直接返回左线索所指的前驱

      与BST查找操作极为相似，若⽆法直接根据线索返回，则"拐"⼀下⾛⾄尽头

/* 通用遍历示例 */
for (TBiTNode *p = first(tbt); p; p = next(p))
    visit(p);
  • 先序线索⼆叉树——找前驱麻烦，找后继方便
    • 找⼦树中第⼀个结点：显然为根结点
    • 找结点的后继：【从左开始看】
      1. 有左孩⼦：后继是左孩⼦
      2. ⽆左孩⼦但有右孩⼦：后继是右孩⼦
      3. 为叶结点：后继如右线索所指示
/* 遍历先序线索二叉树 */
void preOrder(TbiTree *tbt) {
    if (tbt) {
        TBiTNode *p = tbt;
        while (p) {
            while (p->ltag == 0) {
                visit(p);
                p = p->lchild;
            }
            visit(p);
            p = p->rchild;
        }
    }
}
  • 后序线索⼆叉树——找前驱、后继都麻烦
    • 仅需掌握找结点的后继：【从右开始看】
      1. 为根结点：后继为空
      2. 为父结点的右孩⼦，或为父结点的左孩⼦且父结点⽆右孩⼦：后继为父结点
      3. 为父结点的左孩⼦且父结点有右孩⼦：后继为父结点右⼦树上的第⼀个结点

4 树与森林

森林（Forest）：多棵互不相交的树的集合

4.1 树与森林的存储结构

双亲表示法：⼀种顺序存储结构，使⽤顺序表（⼀维数组）实现，下标对应结点，每个空间存储下标对应结点的父结点的下标

#define MAXSIZE 1010

typedef struct Tree {
    ElemType data;
    int parent;
} Tree;

Tree T[MAXSIZE];

孩⼦表示法：一种链式存储结构，直接⽤图的邻接表结构存储各结点的孩⼦（树可视作一类特殊的图），详⻅第七章"图"

孩⼦兄弟表示法：另一种链式存储结构，使⽤⼆叉链表存储树，将树与森林⼆叉树化（见下一节）。child、sibling分别指向结点的第⼀个孩⼦、兄弟

typedef struct CSTNode {
    ElemType data;
    struct CSTNode *child, *sibling;
} CSTNode, *CSTree;

4.2 树、森林与⼆叉树的转换

树与⼆叉树互相转换：

  • 树 → ⼆叉树：
    1. 把互为兄弟的孩⼦们连起来
    2. 每个⽗结点只保留⼀条与孩⼦的连线（通常选择最左的孩⼦），删除多余的线
  • 还原为树：
    1. 把孩⼦们与其⽗结点连起来（即与最左兄弟相连的那位）
    2. 删除所有孩⼦之间的线

森林与⼆叉树互相转换

  • 森林 → ⼆叉树：
    1. 先将森林中的每棵树分别转化成⼆叉树（根结点只允许有左分枝，右分枝需为空）
    2. 利⽤各个根的右空分枝，将所有根结点顺次连起来
  • 还原为森林：
    1. 删除各根结点右分枝的线（根结点即第⼀“斜层”的结点）
    2. 将各⼆叉树还原为树

4.3 树与森林的遍历

树、森林与⼆叉树的深度优先遍历对应关系：

树 森林 二叉树
先根遍历：根 → ⼦树 先序遍历 先序遍历
后根遍历：⼦树 → 根 后序遍历（又称中序遍历） 中序遍历

注意！对于森林，有时也称后序遍历为中序遍历，记住两者是⼀回事即可，名称只是形式！

层序遍历：同⼆叉树的层序遍历，使⽤队列

代码实现详见“图的遍历”

5 树与二叉树的应用

"堆"位于第⼋章"搜索"之"堆排序"

"⼆叉排序树"与"平衡⼆叉树"位于第九章"查找"

5.1 表达式⼆叉树

表达式⼆叉树：⽤⼆叉树表示表达式的运算规则

  • 建树：叶结点均为操作数；⾮叶结点均为运算符，左、右⼦树为参与该运算的⼦表达式（正好按中缀摆放），该⼦树即表示⼀个⼦表达式
  • 还原：遍历可得前缀（前序遍历）、中缀（中序遍历）、后缀（后序遍历）表达式

  • 求值：递归求值，遇到操作符则递归计算⼦表达式，遇到操作数则直接返回
double calSub(double A, char op, double B); // 子树求值函数，返回运算结果（即子树表达式的值，必合法）

double calExpTree(BiTree T) {
    if (!T) return 0;   // ⼦树为空则返回0

    if (T->lchild || T->rchild) {   // 当前为⾮叶结点（操作符结点）则递归计算
        double A = calExpTree(T->lchild);   // 递归计算左⼦树
        double B = calExpTree(T->rchild);   // 递归计算右⼦树
        return calSub(A, T->data, B);   // 返回计算结果
    } else {
        return T->data - '0';   // 当前为叶结点（操作数结点）则返回其数值
    }
}

【例】表达式a+b*(c-d)-e/f可表示成如下所示的表达式二叉树

5.2 哈夫曼树与哈夫曼编码

带权树的核心概念：

  • 结点的路径⻓度：从根结点到某结点途中经过的边数
  • 结点的带权路径⻓度：某结点的路径⻓度l与该结点上权值w的乘积
  • 树的带权路径⻓度：所有叶结点的带权路径⻓度之和，记为 
    \begin{aligned}
\text{WPL}=\sum\limits_{i=1}^n w_i l_i
\end{aligned}
  • 哈夫曼树（Huffman Tree）：带权路径最短的树，可以为⼆叉树，亦可为多叉树

哈夫曼树的构造（以⼆叉树为例）：

  1. 将n个结点分别作为n棵仅含1个结点的二叉树，形成一片森林
  2. 构造新结点：从森林中挑出两棵权值最⼩的树（可以事先按权值大小排序），作为新结点的左右⼦树，新结点的权值为左右⼦树的权值之和，然后将新结点加⼊森林中。
    • 若结点数不够，则在最开始时补上权值为0的结点（不影响WPL）
  3. 重复第 2 步操作，直⾄森林中只剩下⼀棵树为⽌

哈夫曼树的性质：

  1. 所有初始结点最终均成为叶结点，且权值越⼩的结点WPL越⼤，反之越⼩
  2. 所有新结点均为双分⽀结点，故哈夫曼树不存在度为1的结点（n_1=0），这种⼆叉树称为正则（严格）⼆叉树
  3. 构造过程中共新建了n-1个结点，故哈夫曼树的总结点数为2n-1

各种编码的核心概念：

  • 固定⻓度编码：每个字符⽤相等⻓度的⼆进制位表示
  • 可变⻓度编码：对不同字符⽤不等⻓的⼆进制位表示：⾼频字符赋以短编码，低频字符赋以较⻓编码，使得字符的平均编码⻓度减短，起到压缩数据的效果（例如哈夫曼编码）
  • 前缀码：没有⼀个编码是另⼀个编码的前缀的编码。【例】0,101,110是前缀码
  • 哈夫曼编码（Huffman Coding）：⽤哈夫曼树对字符（叶结点）按出现频度（权值）进⾏编号的⼀种前缀码

哈夫曼编码过程：

  1. 将每个出现的字符以其出现频度（或次数）为结点权值构造哈夫曼树
  2. 标记所有边，通常规定左分枝标记\text{0}、右分枝标记\text{1}
  3. 从根⾛到某叶结点，记录路径上的编号，即为哈夫曼编码，其WPL即为⼆进制编码⻓度

哈夫曼树、哈夫曼编码不唯⼀，但各树的WPL必定相同且为最优，且哈夫曼树的最大高度为哈夫曼编码的最大长度 + 1。

【例】字符集{a, b, c, d, e, f}所对应的权值集合为\{8, 3, 4, 6, 5, 5\}，以此构造的⼀棵哈夫曼树为

所构造的哈夫曼树的\text{WPL}=6\times 2 + 3\times 3+ 4\times 3 + 8\times 2 + 5\times 3 + 5\times 3 = 79

字符集{a, b, c, d, e, f}中各字符所对应的哈夫曼编码分别为：00,010,011,10,110,111

5.3 并查集

并查集（Union-find Disjoint Set）：双亲表示法的应⽤，通常规定元素存储范围为[1, n]，祖宗存储元素为其⾃身（或规定为其他特定标记如-1、0）

基本操作：

  1. 初始化
int p[MAXSIZE], n;  // p[1...n]

for (int i = 1; i <= n; i++)
    p[i] = i;
  1. 查找操作：并查集核心操作。查找元素x的祖宗结点，同时更新沿路祖宗信息，T(n)=O(n)
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
  1. 合并操作：合并结点a和b所在集合（将a并至b），同时更新祖宗信息
p[find(a)] = find(b);
  1. 判断两个结点是否属于同一集合的条件：p[find(a)] == find(b)

5.3.A 维护集合大小的并查集*

结点a所属集合的大小：cnt[find(a)]

  1. 初始化：
int n;
int p[N], cnt[N];   // cnt[i]存储根结点i的集合中结点数（仅根结点的cnt有意义）

void init() {
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        cnt[i] = 1;     // 初始化各结点为根，其所属集合大小为1
    }
}
  1. 查找操作
int find(int x) {
    if (p[x] != x) {
        p[x] = find(p[x]);
    }
    return p[x];
}
  1. 合并操作
void Union(int a, int b) {
    if (find(a) == find(b)) continue;   // 若已在同一集合内则跳过
    cnt[find(b)] += cnt[find(a)];   // 需将a所属集合的大小加至b
    p[find(a)] = find(b);
}

5.3.B 维护到祖宗结点距离的并查集*

结点i到其根结点p[i]的距离：d[i]

  1. 初始化：
int n;
int p[N], d[N];     // d[i]存储结点i到其根结点p[i]的距离

void init() {
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        d[i] = 0;   // 初始化全为0
    }
}
  1. 查找操作
int find(int x) {
    if (p[x] != x) {
        int u = find(p[x]); // u临时记录根结点
        d[x] += d[p[x]];    // 更新x到根p[x]的路径长度
        p[x] = u;
    }
    return p[x];
}
  1. 根据具体问题，初始化结点a所在集合的祖先find(a)的偏移量：
void set_distance(int a, int distance) {
    d[find(a)] = distance;
}
  1. 合并操作
void Union(int a, int b) {
    p[find(a)] = find(b);
}

5.A Trie树*

字典树（Retrieval Tree，Trie Tree）又称前缀树，用于高效存储和查找字符串集合。

AC自动机为追加了fail指针的Trie树，算法思想类似于KMP。此处仅介绍原版Trie树。

Trie-tree

int son[N][26], cnt[N], idx;
// son[p][u]记录结点p的第u个子结点（26表示26个字母）
// cnt[p]存储以结点p结尾的单词数量
// idx初始为0（0号点既是根结点，又是空结点，故创建结点时为++idx）

/* 插入一个字符串 */
void insert(char str[]) {
    int p = 0;  // 从根结点0开始遍历Trie的指针
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!son[p][u]) {
            son[p][u] = ++idx;  // 不存在则创建该子结点
        }
        p = son[p][u];
    }
    cnt[p]++;   // p最终指向字符串末尾字母，p计数器自增
}

/* 查询字符串出现的次数 */
int query(char str[]) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!son[p][u]) {
            return 0;   // 不存在则直接返回0
        }
        p = son[p][u];
    }
    return cnt[p];  // p最终指向字符串末尾字母，返回数量
}

A 树与⼆叉树编程练习

A.1 ⼆叉树递归DFS

【例1】在一棵以二叉链表存储的二叉树中，查找数据域值（int型）等于key的结点是否存在，若存在则将指针q指向该结点（假设树中结点值各不相同

void search(BiTree T, BiNode *&q, int key) {
    if (T) {
        if (T->data == key) {
            q = T;
        } else {
            search(T->lchild, q, key);
            search(T->rchild, q, key);
        }
    }
}

【例2】设一棵二叉树T以二叉链表存储，结点值为int型，求先序遍历序列中第k个结点的值（1 <= k <= 结点个数）

int cnt = 0;    // 定义全局变量计数器（或者作为函数参数）
void searchK(BiTree T, int k) {
    if (T) {
        cnt++;  // 更新计数器，记录当前访问的是第几个结点
        if (cnt == k) { // 若遍历到第k个结点则打印该结点数据值并结束本次递归
            printf("%d", T->data);
            return;
        }
        searchK(T->lchild, k);
        searchK(T->rchild, k);
    }
}

【例3】利用递归计算二叉树中所有结点的个数

/* 法1 */
int n = 0;  // 定义全局变量记录结点个数
void countNodes1(BiTree T) {
    if (T) {
        n++;
        countNodes1(T->lchild);
        countNodes1(T->rchild);
    }
}
/* 法2 */
int countNodes2(BiTree T) {
    if (!T) return 0;   // 递归边界
    int lcnt = countNodes2(T->lchild);
    int rcnt = countNodes2(T->rchild);
    return lcnt + rcnt + 1;
}

【例4】利用递归计算二叉树中所有叶结点的个数

/* 法1 */
int n = 0;  // 定义全局变量记录结点个数
void countLeaves1(BiTree T) {
    if (T) {
        if (!T->lchild && !T->rchild) n++;  // 为叶子结点（无孩子）则计数
        countLeaves1(T->lchild);
        countLeaves1(T->rchild);
    }
}
/* 法2 */
int countLeaves2(BiTree T) {
    if (!T) return 0;   // 当前为空则返回0
    if (!T->lchild && !T->rchild) return 1; // 为叶结点则返回1
    return countLeaves2(T->lchild) + countLeaves2(T->rchild);
}

【例5】利用递归计算二叉树中所有双分支结点的个数

int count2Deg(BiTree T) {
        if (!T)
            return 0;
        else if (T->lchild && T->rchild)    // 为双分支结点，则在计算子树中个数基础上再+1
            return count2Deg(T->lchild) + count2Deg(T->rchild) + 1;
        else
            return count2Deg(T->lchild) + count2Deg(T->rchild);
}

【例5改】利用递归计算二叉树中所有单分支结点个数

int count1Deg(BiTree T) {
        if (!T)
            return 0;
        else if ((T->lchild && !T->rchild) || (!T->lchild && T->rchild))
            return count1Deg(T->lchild) + count1Deg(T->rchild) + 1; // 递归计算子树，下同
        else
            return count1Deg(T->lchild) + count1Deg(T->rchild);
}

【例6】利用递归计算二叉树的深度

int getDepth(BiTree T) {
    if (!T) return 0;   // 当前子树为空则深度为0
    int ldepth = getDepth(T->lchild);
    int rdepth = getDepth(T->rchild);
    return (ldepth > rdepth ? ldepth : rdepth) + 1; // 返回更深的子树高度+1
}

【例7】设二叉树T用二叉链表存储，设计算法把树T中所有结点的左、右子树进行交换

void swapChilds(BiTree &T) {
    if (T) {
        BiTNode *tmp = T->lchild;   // 设置辅助指针，类似基本数据类型变量的值交换方法
        T->lchild = T->rchild;
        T->rchild = tmp;
        swapChilds(T->lchild);
        swapChilds(T->rchild);
    }
}

【例8】设二叉树T用二叉链表存储，设计算法求树T中值为x的结点的层次号，将其打印（假设结点值各不相同且必查找成功）

void searchLevel(BiTree T, int x, int level) {
    if (T) {
        if (T->data == x) printf("%d", level);  // 当前子树根值为x则打印层数
        searchLevel(T->lchild, x, level + 1);   // 递归，让层数（level）加1，下同
        searchLevel(T->rchild, x, level + 1);
    }
}

/* 封装递归函数 */
void searchAndPrintLevel(BiTree T, int x) {
    searchLevel(T, x, 1);   // 初始时根所在层次为1
}

【例9】设二叉树T用二叉链表存储，设计算法将树T的叶子结点按从左到右的顺序连成一个单链表，表头指针为head，链接时用叶子结点的右指针域来存放单链表指针

BiTNode *head = NULL, *pre = NULL;   // head：链表头指针；pre：记录指针，记录前驱叶结点

void linkLeaves(BiTree &T) {    // 改写中序遍历
    if (T) {
        linkLeaves(T->lchild);
        if (!T->lchild && !T->rchild) { // 若此结点为叶子结点，则执行操作
            if (!pre) { // 特判访问到的第一个结点情况（此时pre为空）
                head = T;   // 让头指针head指向该开始结点
                pre = T;    // 更新前驱
            } else {    // 非开始结点则正常操作
                pre->rchild = T;    // 当前叶结点链接至前驱之后
                pre = T;    // 更新前驱
            }
        }
        linkLeaves(T->rchild);
    }
}

【例10】判断两棵二叉树是否相似（T1与T2相似：两棵树都空或都只有一个根结点；或它们的左子树相似，且它们的右子树相似）

bool isSimilar(BiTree T1, BiTree T2) {
    if (!T1 && !T2) return true;    // 两棵树都空，则相似
    if (!T1 || !T2) return false;   // 两棵树其一为空、其一非空，则不相似
    bool lflag = isSimilar(T1->lchild, T2->lchild);
    bool rflag = isSimilar(T1->rchild, T2->rchild);
    return lflag && rflag;
}

【例11】计算二叉树的带权路径长度（假设结点数据类型为int型

void preOrder(BiTree T, int *WPL, int level) {
    if (T) {
        if (!T->lchild && !T->rchild) *WPL += level * T->data;
        preOrder(T->lchild, WPL, level + 1);
        preOrder(T->rchild, WPL, level + 1);
    }
}

int getWPL(BiTree T) {
    int WPL = 0;
    preOrder(T, &WPL, 0);
    return WPL;
}

A.2 ⼆叉树层次遍历

【例1】设二叉树T用二叉链表存储，判断其是否是完全二叉树

bool isComplete(BiTree T) {
    if (!T) return true;    // 完全二叉树可以为空
    Queue Q;
    initQueue(Q);
    BiTNode *p = T; // 遍历指针，初始指向根结点
    push(Q, p); // 让根结点入队
    while (!isEmpty(Q)) {
        pop(Q, p);
        if (p) {    // p不为空则让其孩子入队（孩子为空则入队NULL）
            push(Q, p->lchild);
            push(Q, p->rchild);
        } else {    // p为空则判断队列中还有无结点（非NULL）
            while (!isEmpty(Q)) {
                pop(Q, p);
                if (p) return false;    // 若后续还有结点则表明不是完全二叉树，直接返回false
            }
        }
    }
    return true;    // 若队列中剩余数据全为NULL，则表明是完全二叉树，返回true
}

【例2】设二叉树T用二叉链表存储，设计算法完成：对于树中每个元素值为x的结点，删除以它为根的子树，并释放相应空间

void deleteTree(BiTree &T) {
    if (T) {    // 先删左右子树，最后释放根结点空间
        deleteTree(T->lchild);
        deleteTree(T->rchild);
        free(T);
    }
}

void deleteNodesByValue(BiTree &T, int x) {
    if (!T) return; // 若为空树则直接结束函数
    if (T->data == x) {
        deleteTree(T);  // 若根的元素值即为x，则直接删除整棵树
        return;
    }
    Queue Q;
    initQueue(Q);
    BiTNode *p = T; // 遍历指针，初始指向根结点
    push(Q, p); // 根结点入队
    while (!isEmpty(Q)) {
        pop(Q, p);
        if (p->lchild) {
            if (p->lchild->data == x) { // 检查左子树根
                deleteTree(p->lchild);
                p->lchild = NULL;
            } else {
                push(p->lchild);
            }
        }
        if (p->rchild) {
            if (p->rchild->data == x) { // 检查右子树根
                deleteTree(p->rchild);
                p->rchild = NULL;
            } else {
                push(Q, p->rchild);
            }
        }
    }
}

【例3】设二叉树T用二叉链表存储，使用层次遍历计算二叉树的高度【使用非循环队列，假设最大容量够用】

int getDepth(BiTree T) {
    if (!T) return 0;   // 规定空树的高度为0
    int h = 0, last = 0;    // h：记录高度；last：记录每一层最右边结点的位置
    BiTNode *Q[MAXSIZE];    // 非循环队列，设置双指针初始都指向-1
    int front = -1, rear = -1;
    BiTNode *p = T; // 遍历指针，初始指向根结点
    Q[++rear] = p;
    while (front != rear) {
        p = Q[++front];
        if (p->lchild) Q[++rear] = p->lchild;
        if (p->rchild) Q[++rear] = p->rchild;
        if (front == last) {    // 当某一层最右边结点出队时:
            h++;    // 高度计数器+1
            last = rear;    // 更新last，使其指向下一层最右边结点位置
        }
    }
    return h;
}

【例4】设二叉树T用二叉链表存储，求给定二叉树的宽度（宽度：树中具有结点数最多那一层的结点个数）

int getWidth(BiTree T) {
    if (!T) return 0;   // 规定空树的宽度为0
    BiTNode *Q[MAXSIZE];    // 非循环队列，设置双指针初始都指向0
    int front = 0, rear = 0;
    int level[MAXSIZE]; // 记录队列中各位置对应结点所在层数（与Q同步更新）
    BiTNode *p = T; // 遍历指针，初始指向根结点
    int k = 1;  // 记录p所指结点所在层数，初始为1
    Q[rear] = p;
    level[rear++] = k;
    while (front != rear) {
        p = Q[front];
        k = level[front++];
        if (p->lchild) {
            Q[rear] = p->lchild;
            level[rear++] = k + 1;  // 儿子在父亲下一层，下同
        }
        if (p->rchild) {
            Q[rear] = p->rchild;
            level[rear++] = k + 1;
        }
    }
    int max = 0;    // max：记录一层中结点数的最大值
    for (int i = 0, k = 1; i < rear;) { // k：表示当前所计数的是第几层，初始为1
        int cnt = 0;    // 记录第k层的结点个数
        while (i < rear && level[i] == k) {  // 对第k层进行计数
            cnt++;
            i++;
        }
        k++;    // 本层计数结束，更新k，准备去下一层
        if (cnt > max) {
            max = cnt;
        }
    }
    return max;
}

A.3 ⼆叉树⾮递归DFS

【例1】在二叉树中查找值为x的结点，打印其所有祖先（结点值为int型，且保证值为x的结点不多于1个）

void printAncestors(BiTree T, int x) {  // 改写后序非递归
    Stack S;    // 辅助栈（栈中元素恰好为p所指结点的全部祖先）
    initStack(S);
    BiTNode *p = T, *r = NULL;
    while (p || !isEmpty(S)) {
        if (p) {
            push(S, p);
            p = p->lchild;
        } else {
            getTop(S, p);
            if (p->rchild && p->rchild != r) {
                p = p->rchild;
            } else {
                pop(S, p);
                if (p->data == x) { // 数据域等于x则打印当前栈中所有结点
                    while (!isEmpty(S)) {   // 栈顶出栈、打印
                        pop(S, p);
                        printf("%d ", p->data);
                    }
                }
                r = p;
                p = NULL;
            }
        }
    }
}

【例2】设p和q分别指向一棵二叉树中任意两个结点，设计算法找到p和q的最近公共祖先并返回

BiTNode *findLCA(BiTree T, BiTNode *p, BiTNode *q) {  // 改写后序非递归
    BiTNode *bt = T, *r = NULL; // bt：遍历指针；r：记录指针
    BiTNode *S[MAXSIZE], *S1[MAXSIZE], *S2[MAXSIZE];    // 三个栈：S为递归主栈，S1、S2分别存储p、q的祖先
    int top = -1, top1 = -1, top2 = -1;
    while (bt || top != -1) {
        if (bt) {
            S[++top] = bt;
            bt = bt->lchild;
        } else {
            bt = S[top];
            if (bt->rchild && bt->rchild != r) {
                bt = bt->rchild;
            } else {
                bt = S[top--];
                if (bt == p) {  // 遍历至p则将当前栈S中所有结点复制至栈S1中
                    for (int i = 0; i <= top; i++) {    // 当前栈S中结点即为p的所有祖先
                        S1[top1++] = S[i];
                    }
                }
                if (bt == q) {  // 遍历至q则将当前栈S中所有结点复制至栈S2中
                    for (int i = 0; i <= top; i++) {    // 当前栈S中结点即为q的所有祖先
                        S2[top2++] = S[i];
                    }
                }
                r = bt;
                bt = NULL;
            }
        }
    }
    for (int i = top1; i >= 0; i--) {       // 自顶至底寻找栈S1和S2中的最近公共结点，找到则返回该指针
        for (int j = top2; j >= 0; j--) {
            if (S1[i] == S2[j]) return S1[i];
        }
    }
    return NULL;                           // 若未找到则返回NULL
}

【例3】设一棵二叉树以二叉链表存储，结点值为int型，设计算法输出根结点到每个叶子结点的路径

void printPaths(BiTree T) { // 改写后序非递归
    BiTNode *p = T, *r = NULL;
    BiTNode *S[MAXSIZE];
    int top = -1;
    while (p || top != -1) {
        if (p) {
            S[++top] = p;
            p = p->lchild;
        } else {
            p = S[top];
            if (p->rchild && p->rchild != r) {
                p = p->rchild;
            } else {
                p = S[top--];
                if (!p->lchild && !p->rchild) { // 若当前结点p为叶子结点
                    for (int i = 0; i <= top; i++) {    // 顺序打印栈中所有结点数据
                        printf("%d ", S[i]->data);
                    }
                    printf("%d\n", p->data);    // 最后打印该叶子结点数据
                }
                r = p;
                p = NULL;
            }
        }
    }
}

A.4 其他⼆叉树存储形式

【例1】有一棵二叉树以顺序存储的方式存在一维数组A中，结点数据为字符型，空指针域用字符'#'表示。设计算法将其改为二叉链表存储结构（假设数组A从下标1开始存储元素，存储元素个数为n）

BiTNode *createSubTree(char A[], int i, int n) {    // i：遍历索引
    if (i > n || A[i] == '#') return NULL;  // i超出长度范围或遇到空结点则返回空
    BiTNode *p = (BiTNode*) malloc(sizeof BiTNode); // 创建新结点
    p->data = A[i];
    p->lchild = createSubTree(A, 2 * i, n); // 递归处理左子树
    p->rchild = createSubTree(A, 2 * i + 1, n); // 递归处理右子树
    return p;
}

BiTree createTree(char A[], int n) {
    return createSubTree(A, 1, n);
}

【例2】设有一棵满二叉树，已知其先序序列为pre，设计算法求其后序序列post（假设结点值为字符型且各不相同）

void preToPost(char pre[], int preL, int preR, char post[], int postL, int postR) {
    if (preL <= preR) { // 递归边界：先序子序列长度非负（≤ preR）才有意义
        post[postR] = pre[preL];    // 后序尾元素 = 根 = 先序首元素
        int half = (preR - preL) / 2;   // 计算子树结点个数：满二叉树左右子树结点个数相等
        preToPost(pre, preL + 1, preL + half, post, postL, postL + half - 1);
        preToPost(pre, preL + half + 1, preR, post, postL + half, postR - 1);
    }
}

【例3】在二叉树的二叉链表存储结构中，增加一个指向双亲结点的parent指针。设计算法给这个指针赋值（假设结点值为字符型），并输出所有结点到根结点的路径

typedef struct PBiTNode {
    char data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
    struct BiTNode *parent; // 结构体新增双亲指针
} PBiTNode, *PBiTree;

/* 设置二叉树的双亲指针 */
void setParent(PBiTree &T, PBiTNode *p) {   // p：记录双亲结点，初始应为NULL
    if (T) {
        T->parent = p;  // 设置当前遍历结点的双亲指针为p
        p = T;  // 更新p
        setParent(T->lchild, p);    // 递归设置左子树
        setParent(T->rchild, p);    // 递归设置右子树
    }
}

/* 打印单个结点到根结点的路径 */
void printPath(PBiTNode *p) {
    while (p) {
        printf("%c ", p->data);
        p = p->parent;
    }
    printf("\n");
}

/* 打印所有结点到根结点的路径 */
void printPaths(PBiTree T) {
    if (T) {
        printPath(T);   // 打印当前子树根结点到整棵树根的路径
        printPaths(T->lchild);  // 递归打印左子树
        printPaths(T->rchild);  // 递归打印右子树
    }
}

A.5 树的孩⼦兄弟表示法

【例1】设计算法计算以孩子兄弟表示法存储森林的叶结点数

int countLeaves(CSTree T) {
    if (!T) // 若为空树则叶结点数为0
        return 0;
    else if (!T->child) // 若无child则表示其为叶结点，返回1+其兄弟子树上的叶结点数
        return 1 + countLeaves(T->sibling);
    else    // 否则返回其孩子及其兄弟子树上的叶结点数
        return countLeaves(T->child) + countLeaves(T->sibling);
}

【例2】设计算法计算以孩子兄弟表示法存储树的高度

int getHeight(CSTree T) {
    if (!T) return 0;   // 空树的高度为0
    int lheight = getHeight(T->child);
    int rheight = getHeight(T->sibling);
    if (lheight + 1 > rheight) return lheight + 1;  // 左边+1是因为T为其双亲，加上了双亲的这一层
    return rheight; // 右边不加是因为T为其兄弟，处于同一层
}

发表评论