# 计算机23级数据结构上机实验（第3-4周）

A 二叉树删除子树

分数 10

作者 朱允刚

单位 吉林大学

编写程序对给定二叉树执行若干次删除子树操作，输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。

输入格式:

输入第1行为一组用空格间隔的整数，表示带空指针信息的二叉树先根序列，其中空指针信息用0表示。例如1 5 8 0 0 0 6 0 0表示如下图的二叉树。第2行为整数m，表示要进行的删除操作次数。接下来m行，每行一个不等于0的整数K，表示要删除以K为根的子树。m不超过100，二叉树结点个数不超过5000。输入数据保证各结点数据值互不相等，且删除子树后二叉树不为空。

PA567.jpg

输出格式:

输出为m行，每行为一组整数，表示执行删除操作后剩余二叉树的中根序列（中根序列中每个整数后一个空格）。若要删除的子树不在当前二叉树中，则该行输出0（0后无空格）。

输入样例:

1 5 8 0 0 0 6 0 0
3
5
8
6

输出样例:

1 6 
0
1

代码长度限制

16 KB

时间限制

100 ms

内存限制

10 MB

栈限制

8192 KB

解决思路

步骤1：构建二叉树

  • 输入格式是先根序列，其中用 0 表示空指针。我们需要从根节点开始，通过递归依次构建左右子树。
  • 递归思路(注意传入二级指针,或者可以通过返回一个结点指针构建)
    • 遇到值为 0 时，返回空节点（nullptr）。
    • 对非 0 的值，创建一个新节点，并递归构建其左子树和右子树。

步骤2：中序遍历*

  • 中序遍历规则：依次访问左子树、根节点、右子树。
  • 递归实现：遍历时逐个打印节点数据，用于验证树的结构以及删除操作后的结果。

步骤3：删除以指定节点为根的子树*

  • 目标是删除树中数据值为 K 的节点及其子树。
  • 非递归实现
    1. 利用栈模拟深度层序遍历，找到目标节点的父节点。
    2. 一旦找到目标节点，修改父节点指针断开子树。
    3. 删除成功后返回 true；如果遍历完树未找到目标节点，返回 false。

步骤4：逐次删除并输出结果*

  • 每次删除
    1. 调用删除函数，尝试删除以 K 为根的子树。
    2. 若删除成功，输出树的中序遍历结果。
    3. 若删除失败（目标节点不存在），输出 0。
  • 重复删除：所有操作都基于上一次删除操作后的树。

没有考虑空间的释放

#include<iostream>
#include<vector>

using namespace std;

// 树节点类定义
class Tree
{
public:
    int data; // 节点数据
    Tree* left; // 左子节点
    Tree* right; // 右子节点

    // 构造函数，初始化节点数据及左右子节点指针
    Tree(int data) : data(data), left(nullptr), right(nullptr) { }
};

// 创建二叉树的递归函数
void Create(Tree*& tree)
{
    int k;
    cin >> k; // 输入节点数据

    if (k != 0) // 如果输入不为0，创建当前节点
    {
        tree = new Tree(k); // 动态分配内存创建节点
    }
    else // 如果输入为0，表示该节点为空
    {
        return;
    }

    Create(tree->left); // 递归创建左子树
    Create(tree->right); // 递归创建右子树
}

// 创建二叉树的根节点，并通过递归构建整棵树
Tree* CreateRoot()
{
    int k;
    cin >> k; // 输入根节点数据

    Tree* root;

    if (k != 0) // 如果输入不为0，创建根节点
    {
        root = new Tree(k);
    }
    else // 如果输入为0，根节点为空，返回nullptr
    {
        return nullptr;
    }

    Create(root->left); // 创建左子树
    Create(root->right); // 创建右子树

    return root; // 返回根节点
}

// 前序遍历：根 -> 左 -> 右
void PreOrder(Tree* root)
{
    if (root == nullptr) // 如果当前节点为空，返回
    {
        return;
    }

    cout << root->data << " "; // 输出当前节点数据
    PreOrder(root->left); // 遍历左子树
    PreOrder(root->right); // 遍历右子树
}

// 中序遍历：左 -> 根 -> 右
void InOrder(Tree* root)
{
    if (root == nullptr) // 如果当前节点为空，返回
    {
        return;
    }

    InOrder(root->left); // 遍历左子树
    cout << root->data << " "; // 输出当前节点数据
    InOrder(root->right); // 遍历右子树
}

// 后序遍历：左 -> 右 -> 根
void PostOrder(Tree* root)
{
    if (root == nullptr) // 如果当前节点为空，返回
    {
        return;
    }

    PostOrder(root->left); // 遍历左子树
    PostOrder(root->right); // 遍历右子树
    cout << root->data << " "; // 输出当前节点数据
}

// 删除树中数据为k的节点，返回删除是否成功
bool Delete(Tree* root, int k)
{
    if (root == nullptr) // 如果树为空，返回false
    {
        return false;
    }

    std::vector<Tree*> stack; // 栈用于存储待访问的节点
    stack.push_back(root); // 将根节点压入栈中

    while (!stack.empty()) // 当栈不为空时，循环
    {
        Tree* p = stack.back(); // 获取栈顶节点
        stack.pop_back(); // 弹出栈顶节点

        if (p->left) // 如果存在左子节点
        {
            if (p->left->data == k) // 检查左子节点是否是目标节点
            {
                p->left = nullptr; // 删除左子节点
                return true; // 返回删除成功
            }
            stack.push_back(p->left); // 将左子节点压入栈中
        }

        if (p->right) // 如果存在右子节点
        {
            if (p->right->data == k) // 检查右子节点是否是目标节点
            {
                p->right = nullptr; // 删除右子节点
                return true; // 返回删除成功
            }
            stack.push_back(p->right); // 将右子节点压入栈中
        }
    }

    return false; // 如果遍历完未找到目标节点，返回false
}

int main()
{
    // 创建树的根节点
    Tree* root = CreateRoot();

    int m;
    cin >> m; // 输入需要删除节点的次数

    for (int i = 0; i < m; i++) // 循环m次，每次删除一个节点
    {
        int k;
        cin >> k; // 输入需要删除的节点值
        bool is_delete = Delete(root, k); // 调用Delete函数删除节点
        if (is_delete) // 如果删除成功
        {
            InOrder(root); // 输出删除后的树的中序遍历结果
        }
        else // 如果删除失败（节点不存在）
        {
            cout << "0"; // 输出0
        }
        cout << endl;
    }
}

B 重建二叉树

分数 10

作者 朱允刚

单位 吉林大学

给定非空二叉树的中根序列和后根序列，请编写程序创建该二叉树，计算其高度和先根序列；如给定的中根和后根序列不合法，则亦能识别。

输入格式:

输入包含多组数据（不超过10组），每组为两行字符串，第一行表示某二叉树的后根序列，第二行表示其中根序列。结点的值均为A-Z的大写字母，故二叉树结点个数不超过26，且保证输入的两个序列都是结点的全排列，但不一定是合法的中根和后根序列。输入保证不是空二叉树。

输出格式:

对于每组数据，如果输入的序列不合法（不是同一棵树的中根序列和后根序列），则输出INVALID；若输入序列合法，输出为两行，第一行为一个整数，表示该二叉树的高度，第二行为一个字符串，表示该二叉树的先根序列。

输入样例1:

CEFDBHGA
CBEDFAGH
CBEDFAGH
CEFDBHGA
BCA 
CAB

输出样例1:

3
ABCDEFGH
INVALID
INVALID

代码长度限制

16 KB

时间限制

50 ms

内存限制

64 MB

栈限制

8192 KB

解题思路

  1. 重建二叉树：（核心）

  2. 根节点确定：后序遍历的最后一个元素是根节点。

  3. 分割中序遍历：在中序遍历中找到根节点的位置，将中序遍历分成左子树和右子树。
  4. 递归构建左右子树：利用递归的方法，继续为左右子树构建树。
  5. 核心：
 // 计算右子树的长度，并确定左右子树的后序根节点位置
    int right_length = b - root_index - 1;
    int left_root = post_root - right_length - 1;

假设我们已经知道：

  • root_index：根节点在中序遍历中的位置。
  • post_root：当前后序遍历的根节点的位置。

我们需要确定左右子树的后序遍历区间。为了理解这两个变量的含义，我们需要分解这段代码的逻辑：

  1. 计算右子树的长度：
int right_length = b - root_index - 1;
  • b 是当前子树的中序遍历的结束索引（即，当前子树的右边界）。
  • root_index 是当前根节点在中序遍历中的位置。

  • right_length 就是右子树的节点数，即当前根节点右侧的所有节点的数量。它是 从root_index的下一个位置到b之间的所有节点的个数，因此我们计算公式是 b - root_index - 1。

  • 计算左子树根节点的后序位置：

int left_root = post_root - right_length - 1;
  • post_root 是当前树的后序根节点的位置。对于当前子树，根节点在后序遍历的最后一个位置。
  • right_length 是我们刚才计算出来的右子树的节点数，右子树的所有节点都在后序遍历中位于根节点的前面。
  • left_root 就是左子树根节点在后序遍历中的位置。由于后序遍历中，左子树的根节点位于右子树根节点之前，因此，左子树的根节点的位置就是当前根节点的位置（post_root）减去右子树的长度（right_length）再减去1（因为根节点占了最后一个位置）。

如何用这两个变量来分割树：

  • 通过right_length 我们知道右子树有多少个节点，因此可以根据它来确定右子树的后序区间。

  • 然后通过left_root 我们知道左子树的根节点在后序遍历中的位置，根据它可以递归地继续构建左子树。

  • 计算树的高度：

  • 树的高度是从根节点到叶子节点的最长路径长度。递归计算左子树和右子树的高度，返回较大的高度值加一。

  • 输出先序遍历：

  • 在重建出二叉树后，可以通过先序遍历（根 -> 左 -> 右）来输出结果。

  • 合法性检查：

// 如果任何一侧的创建失败，返回false
    if (!left || !right) {
        return false;
    }

  • 利用Creat的返回值判断是否合法，即在中序序列里可以找到对应在后序序列的根节点

  • // 如果根节点未找到，则返回false
   if (root_index == b) {
       return false;
   }

  • 如果创建到区间里没有节点返回合法并计算深度

  • if (a >= b) return true; // 如果子树为空，返回true

具体步骤：

#include <iostream>
#include <vector>
using namespace std;

// 树节点类定义
class Tree {
public:
    char data;         // 节点数据
    Tree* left;        // 左子树指针
    Tree* right;       // 右子树指针

    // 构造函数
    Tree(char data) : data(data), left(nullptr), right(nullptr) {}
};

// 使用中序遍历和后序遍历序列递归创建二叉树，[a,b)
bool Create(Tree*& tree, string& In, string& Post, int a, int b, int post_root) {
    if (a >= b) return true; // 如果子树为空，返回true

    // 找到后序遍历的根节点在中序遍历中的位置
    int root_index;
    for (root_index = a; root_index < b; root_index++) {
        if (In[root_index] == Post[post_root])
            break;
    }

    // 如果根节点未找到，则返回false
    if (root_index == b) {
        return false;
    }

    // 创建根节点
    tree = new Tree(In[root_index]);

    // 计算右子树的长度，并确定左右子树的后序根节点位置
    int right_length = b - root_index - 1;
    int left_root = post_root - right_length - 1;

    // 递归创建左子树
    bool left = Create(tree->left, In, Post, a, root_index, left_root);

    // 递归创建右子树
    bool right = Create(tree->right, In, Post, root_index + 1, b, post_root - 1);

    // 如果任何一侧的创建失败，返回false
    if (!left || !right) {
        return false;
    }

    return true;
}

// 创建二叉树的根节点，并根据中序遍历序列和后序遍历序列通过递归构建整棵树
Tree* Createroot(string& In, string& Post) {
    // 如果中序和后序遍历长度不一致，返回nullptr
    if (In.size() != Post.size()) {
        return nullptr;
    }

    int l = In.size();
    int root_index;

    // 找到后序遍历根节点在中序遍历中的位置
    for (root_index = 0; root_index < l; root_index++) {
        if (In[root_index] == Post.back())
            break;
    }

    // 如果根节点未找到，则返回nullptr
    if (root_index == l) {
        return nullptr;
    }

    // 创建根节点
    Tree* root = new Tree(In[root_index]);

    //核心，必须在上一层递归为下一层递归提供更多信息，即根节点的创建时同时为左右子树找到其位置，因为上一层的信息总比下一层多，所以能尽早求出根的位置就先求出来
    // 计算右子树的长度，并确定左右子树的后序根节点位置
    int right_length = l - root_index - 1;
    int left_root = l - 1 - right_length - 1;

    // 递归创建左子树和右子树
    bool left = Create(root->left, In, Post, 0, root_index, left_root);
    bool right = Create(root->right, In, Post, root_index + 1, l, l - 2);

    // 如果任何一侧创建失败，返回nullptr
    if (!right || !left) {
        return nullptr;
    }

    return root;
}

// 前序遍历
void PreOrder(Tree* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->data;       // 输出根节点
    PreOrder(root->left);     // 遍历左子树
    PreOrder(root->right);    // 遍历右子树
}

// 中序遍历
void InOrder(Tree* root) {
    if (root == nullptr) {
        return;
    }
    InOrder(root->left);      // 遍历左子树
    cout << root->data << " "; // 输出根节点
    InOrder(root->right);     // 遍历右子树
}

// 后序遍历
void PostOrder(Tree* root) {
    if (root == nullptr) {
        return;
    }
    PostOrder(root->left);    // 遍历左子树
    PostOrder(root->right);   // 遍历右子树
    cout << root->data << " "; // 输出根节点
}

// 计算树的深度
int Deepth(Tree* root) {
    if (!root) {
        return 0; // 空树深度为0
    }
    int left = Deepth(root->left);  // 左子树深度
    int right = Deepth(root->right); // 右子树深度
    return left > right ? left + 1 : right + 1; // 返回较大子树深度+1
}

int main() {
    Tree* root;
    string In, Post;

    // 不断输入中序和后序序列
    while (cin >> Post >> In) {
        root = Createroot(In, Post); // 构建二叉树
        if (root) { // 如果树有效
            cout << Deepth(root) - 1 << endl; // 输出深度（从0开始计数）
            PreOrder(root); // 输出前序遍历结果
        } else { // 如果无效，输出INVALID
            cout << "INVALID";
        }
        cout << endl;
    }
}

C 最右子表达式

表达式可以对应一个树结构，称为表达式树。其中的叶结点对应表达式中的操作数，非叶结点对应运算符，假定所有运算均为二元运算。根据后缀表达式可以构造出表达式二叉树，方法是：从左向右扫描后缀表达式，每扫描到一个符号就生成一个二叉树结点，该符号作为结点的数据域值；若扫描到的符号是操作数，则将此操作数结点压栈；若扫描到的符号是运算符，则从栈中弹出两个结点，分别作为当前运算符结点的右、左孩子，再将当前运算符结点压栈。表达式扫描完成后，栈顶即为表达式树的根结点。表达式树的后根序列即为后缀表达式。

现给定一个后缀表达式exp，请编写程序求出exp的“最右子表达式”。exp的“最右子表达式”是指从exp对应的表达式树右边看向树，从第0层到最底层所能看到的各结点。例如后缀表达式abcdef+−g+∗−h∗+对应的表达式树如图1所示，其最右子表达式为 +∗h∗+g+f 。

22233.jpg

输入格式:

第一行是正整数n，表示后缀表达式的数目，1<n≤100。接下来n行，每行是一个由字母构成的字符串，长度不超过500，表示一个后缀表达式，其中小写字母表示操作数，大写字母表示运算符。所有运算符均为二元运算符。

输出格式:

对每个后缀表达式，输出其“最右子表达式”。

输入样例1:

6
abcdefXYgXZYhZX
xyPzwIM
abcABdefgCDEF
abcMN
bcMaN
fgCeDdEbcAaBF

输出样例1:

XZhZXgXf
MIw
FEDCg
NMc
Nac
FBacg

输入样例2:

6
vesBdtIBU
crpNWgaQmGG
jhAhRnlCJzU
laaKuqBHfzVEJ
rngAlKCpwgFIM
kcqoDYoDeqiYFDL

输出样例1:

UBIt
GGma
UzClh
JEVzq
MIFgg
LDFYio

代码长度限制

16 KB

时间限制

50 ms

内存限制

30 MB

栈限制

8192 KB

解题思路

  1. 构建表达式树

    ：通过后缀表达式构建二叉树，使用栈存储节点。

    • 遇到操作数时，创建叶子节点并压栈。
    • 遇到运算符时，弹出两个节点，创建运算符节点并压栈。

  2. 获取最右子表达式：从根节点开始，沿着右子树输出每一层的最右节点。

    • 思路一：利用递归将树的层次遍历拆成一层层，每次输出每层的最后的节点即最右节点

    •  std::vector<Tree*> next_level;
    // 获取当前层的最右节点
    Tree* rightest = level.back();
    cout << rightest->data;
    // 将当前层的子节点（左子树和右子树）加入下一层队列
    for (int i = 0; i < level.size(); i++) {
        Tree* p = level[i];   
        if (p->left) {
            next_level.push_back(p->left);
        }

        if (p->right) {
            next_level.push_back(p->right);
        }
    }
    // 如果下一层还有节点，递归调用
    if (!next_level.empty()) {
        rightexp(next_level);
     }

    • 思路二：创建一个与树的深度相等的数组，通过前序遍历并加入深度作为参数每次更新相应下标的数组的值，即更新最右表达式，因为如果同一层的节点存在更右的节点，将会在其后遍历同时更新数组获取最右表达式

    • //n为树的深度
vector<int> exp(n);
getexp(Tree* root, int depth)
{
    if (root = nullptr)return;

    exp[depth] = root->data;

    getexp(root->left, depth + 1);
    getexp(root->right, depth + 1);
}

#include<iostream>
#include<vector>

using namespace std;

// 树节点类定义
class Tree
{
public:
    char data; // 节点的数据（字符）
    Tree* left; // 左子树指针
    Tree* right; // 右子树指针

    // 构造函数，初始化节点数据并设置左右子树为 nullptr
    Tree(char data) : data(data), left(nullptr), right(nullptr) { }
};

// 创建表达式树，输入为后缀表达式
Tree* Create(string exp)
{
    // 使用栈来存储树节点
    std::vector<Tree*> T;

    // 遍历后缀表达式
    for (int i = 0; i < exp.size(); i++)
    {
        // 如果是操作数（小写字母），创建一个新的叶子节点并压栈
        if (exp[i] >= 'a' && exp[i] <= 'z')
        {
            Tree* p = new Tree(exp[i]);
            T.push_back(p);
        }
        else // 如果是运算符（大写字母），则构建一个新节点
        {
            Tree* q = new Tree(exp[i]);

            // 弹出栈顶两个元素，作为当前运算符的左右子树
            Tree* right = T.back();
            T.pop_back();

            Tree* left = T.back();
            T.pop_back();

            // 设置左右子树
            q->left = left;
            q->right = right;

            // 将当前运算符节点压栈
            T.push_back(q);
        }
    }

    // 如果栈为空，返回 nullptr（说明表达式有问题）
    if (T.empty())
    {
        return nullptr;
    }

    // 栈顶元素即为表达式树的根节点
    return T.back();
}

// 递归遍历每一层，输出最右边的节点
void rightexp(std::vector<Tree*> level)
{
    if (level.empty())
    {
        return;
    }

    std::vector<Tree*> next_level;

    // 获取当前层的最右节点
    Tree* rightest = level.back();
    cout << rightest->data;

    // 将当前层的子节点（左子树和右子树）加入下一层队列
    for (int i = 0; i < level.size(); i++)
    {
        Tree* p = level[i];

        if (p->left)
        {
            next_level.push_back(p->left);
        }

        if (p->right)
        {
            next_level.push_back(p->right);
        }
    }

    // 如果下一层还有节点，递归调用
    if (!next_level.empty())
    {
        rightexp(next_level);
    }

    return;
}

// 从根节点开始，递归输出最右子表达式
void Address(Tree* root)
{
    if (!root)
    {
        return;
    }

    cout << root->data;

    std::vector<Tree*> next_level;

    // 如果没有子节点，直接返回
    if (!root->left && !root->right)
    {
        return;
    }

    // 将左子树和右子树加入下一层队列
    if (root->left)
    {
        next_level.push_back(root->left);
    }

    if (root->right)
    {
        next_level.push_back(root->right);
    }

    // 递归调用 rightexp 来输出最右子表达式
    rightexp(next_level);
}

// 主函数
int main()
{
    int m;
    cin >> m; // 输入表达式的数量

    string exp;

    // 对于每个表达式
    for (int i = 0; i < m; i++)
    {
        cin >> exp; // 输入后缀表达式
        Tree* root = Create(exp); // 创建表达式树
        Address(root); // 输出最右子表达式
        cout << endl; // 换行
    }

    return 0;
}

D 哈夫曼树

分数 10

作者 朱允刚

单位 吉林大学

编写一个哈夫曼编码译码程序。针对一段文本，根据文本中字符出现频率构造哈夫曼树，给出每个字符的哈夫曼编码，并进行译码，计算编码前后文本大小。 为确保构建的哈夫曼树唯一，本题做如下限定：

  1. 选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。
  2. 若多棵二叉树根结点权值相等，则先生成的作为左子树，后生成的作为右子树，具体来说：i) 对于单结点二叉树，优先选择根结点对应字母在文本中最先出现者，如文本为cba，三个字母均出现1次，但c在文本中最先出现，b第二出现，故则选择c作为左子树，b作为右子树。ii) 对于非单结点二叉树，先生成的二叉树作为左子树，后生成的二叉树作为右子树。iii. 若单结点和非单结点二叉树根结点权值相等，优先选择单结点二叉树。
  3. 生成哈夫曼编码时，哈夫曼树左分支标记为0，右分支标记为1。

输入格式:

输入为3行。第1行为一个字符串，包含不超过5000个字符，至少包含两个不同的字符，每个字符为a-z的小写字母。第2、3行为两个由0、1组成的字符串，表示待译码的哈夫曼编码。

输出格式:

输出第一行为用空格间隔的2个整数，分别为压缩前后文本大小，以字节为单位，一个字符占1字节，8个二进制位占1字节，若压缩后文本不足8位，则按1字节算。输出从第二行开始，每行为1个字符的哈夫曼编码，按各字符在文本中出现次数递增顺序输出，若多个字符出现次数相同，则按其在文本出现先后排列。每行格式为“字母:编码”。最后两行为两行字符串，表示译码结果，若译码失败，则输出INVALID。

输入样例:

cbaxyyzz
0100
011

输出样例:

8 3
c:100
b:101
a:110
x:111
y:00
z:01
zy
INVALID

代码长度限制

16 KB

时间限制

50 ms

内存限制

64 MB

栈限制

8192 KB

解题思路

  1. 统计字符频率

  2. 输入的字符串是由若干字符组成的，首先需要统计每个字符出现的频率。

  3. 由于哈夫曼编码是根据字符的频率来生成的，所以这个步骤非常重要。

  4.  // 统计字符串中每个字符的频率
    for (int i = 0; i < code.size(); i++){
        num[code[i] - 'a']++;  // 更新频率
        if (num[code[i] - 'a'] == 1)
            word.push_back(code[i]);  // 记录出现的字符
    }
    //根据字符出现顺序记录频率用以创建哈夫曼树
    std::vector<int> a;
    for (int i = 0; i < word.size(); i++) {
        if (num[word[i] - 'a'] != 0){
            a.push_back(num[word[i] - 'a']);
            num[word[i] - 'a'] = 0;
        }
    }

  1. 构造哈夫曼树

  2. 哈夫曼树的构造：基于字符频率构建哈夫曼树。哈夫曼树是一种带权的二叉树，生成的树是最优的（即带权路径长度最短）。构建哈夫曼树的过程是：

    1. 将所有字符作为叶子节点，每个节点的权值就是字符的频率。
    2. 每次选择两个权值最小的节点合并为一个新节点，新节点的权值为两个子节点的权值之和。
    3. 重复这个过程，直到所有节点都合并成一棵树（最终剩下一个根节点）。
  3. 哈夫曼树的每个结点包含：
    • weight: 权值（字符频率）。
    • parent, lchild, rchild: 分别表示父节点、左孩子和右孩子的索引。

  4. 选择最小节点：为了实现哈夫曼树的构造，必须实现一个选择最小权值节点的函数（Select），该函数会在当前节点中选择两个最小权值的节点，并将它们合并为一个新节点。并且在选择时需要注意优先级，即频率相同时先出现的字符先加入到树里

  5. 生成哈夫曼编码

  6. 一旦哈夫曼树构建完成，我们可以通过遍历哈夫曼树来生成每个字符的哈夫曼编码。编码的过程如下：

    1. 从叶子节点开始，逐步回溯到根节点。
    2. 如果从某节点走向左子树，编码为 "0"；如果走向右子树，编码为 "1"。
    3. 每个字符的编码由从该字符所在叶子节点回溯到根节点的路径组成。

  7. 计算压缩前后数据量

  8. 压缩前的大小：直接计算输入字符串的长度。

  9. 压缩后的大小：每个字符的编码长度乘以该字符出现的频率，所有字符的结果加起来，得到压缩后所需要的总位数。再将总位数除以 8 以计算压缩后的字节数。

  10. 输出结果

  11. 输出压缩前的大小（字符个数）和压缩后的大小（字节数）。

  12. 输出每个字符的哈夫曼编码。

  13. 实现编码的解码过程：根据编码串和哈夫曼树，逐步恢复出原来的字符。

  14. 解码

  15. 解码过程是利用哈夫曼树，将编码串还原为原始字符。具体步骤如下：

    1. 从根节点开始，根据编码串的每一位（0 或 1）向左或向右遍历哈夫曼树。
    2. 一直遍历直到到达叶子节点，叶子节点对应的就是一个字符。
    3. 继续处理下一个编码片段，直到整个编码串被完全解码。

  16. 对于非法的编码即编译完时没有走到叶子节点

  17. // 如果到达叶子节点，返回对应字符，否则返回无效
    if (HT[k].lchild == 0 && HT[k].rchild == 0)
        postcode.push_back(word[k - 1]);
    else
        return "INVALID";

#include<iostream>
#include<climits>
#include<cmath>
#include<vector>

// 哈夫曼树的每个结点包含权值和其父节点、左子节点、右子节点的索引
template<class T>
class HuffmanTree
{
public:
    T weight;  // 结点的权值
    int parent, lchild, rchild;  // 结点的父节点、左孩子和右孩子的下标

    HuffmanTree() = default;

    // 通过一个权值初始化结点，并将父节点、左右子节点初始化为 0
    HuffmanTree(T weight) : weight(weight), parent(0), lchild(0), rchild(0)
    {}

    ~HuffmanTree() = default;
};

// 哈夫曼树的管理类，负责创建树并生成编码
template<class T>
class HuffmanTree_manager
{
public:
    // 用n个元素的数组代替叶子结点的权值构造HuffmanTree,返回一个数组指针
    HuffmanTree<T>* CreatTree(std::vector<T> a, int num)
    {
        // 如果节点数小于1，返回空树
        if (num < 1)
        {
            return nullptr;
        }

        // 只有一个节点时，直接构建一个简单的哈夫曼树，避免一个节点时无法编码，并默认一个节点是编码为0
        if (num == 1)
        {
            HuffmanTree<T>* HT = new HuffmanTree<T>[3] {};  // 分配大小为3的数组，数组0号不使用
            HT[1].weight = a[0];
            HT[1].parent = 2;  // 根节点指向叶子
            HT[2].lchild = 1;  // 根节点的左子树是叶子
            HT[2].weight = HT[1].weight;
            return HT;
        }

        // 初始化节点数
        int m = 2 * num - 1;  // 总节点数（包括叶子和非叶子节点）
        HuffmanTree<T>* HT = new HuffmanTree<T>[m + 1] {};  // 创建动态数组，大小为 2 * num - 1

        // 将叶子结点的权值赋给前 num 个节点
        for (int i = 1; i <= num; i++)
        {
            HT[i].weight = a[i - 1];
        }

        // 创建哈夫曼树，合并节点
        for (int i = num + 1; i <= m; i++)
        {
            int s1 = 0, s2 = 0;
            Select(i - 1, s1, s2);  // 选择两个权值最小的结点

            // 合并这两个结点，生成新结点
            if (s1 != 0) HT[s1].parent = i;
            if (s2 != 0) HT[s2].parent = i;
            HT[i].lchild = s1;  // 新节点的左子树
            HT[i].rchild = s2;  // 新节点的右子树
            HT[i].weight = HT[s1].weight + HT[s2].weight;  // 新节点的权值为左右子树权值之和
        }

        return HT;
    }

    // 用于选择权值最小的两个节点，并保持字典序
    void Select(int pos, int& s1, int& s2)
    {
        int minWeight1 = INT_MAX, minWeight2 = INT_MAX;

        for (int i = 1; i <= pos; i++)
        {
            if (HT[i].parent == 0 && HT[i].weight < minWeight1)
            {
                minWeight2 = minWeight1;
                s2 = s1;
                minWeight1 = HT[i].weight;
                s1 = i;
            }
            else if (HT[i].parent == 0 && HT[i].weight < minWeight2)
            {
                minWeight2 = HT[i].weight;
                s2 = i;
            }
        }
    }

    // 生成哈夫曼编码，通过回溯树的叶子节点到根节点
    void HuffmanTreeCode(HuffmanTree<int>* HT, std::vector<std::string>& codes, int n)
    {
        codes.clear();  // 清空之前的编码
        for (int i = 1; i <= n; i++)
        {
            std::string v;  // 存放当前结点的编码
            int k = i;
            int index = HT[i].parent;

            // 从叶子回溯到根节点，生成编码
            while (index != 0)
            {
                if (HT[index].lchild == k)
                    v = "0" + v;  // 左分支生成 "0"
                else
                    v = "1" + v;  // 右分支生成 "1"

                k = index;
                index = HT[index].parent;
            }

            codes.push_back(v);  // 将编码保存
        }
    }
};

// 译码函数，将编码转换回原字符
std::string decode(HuffmanTree<int>* HT, std::string code, std::vector<char> word, int n)
{
    int k = (n == 1) ? 2 : 2 * n - 1;  // 根节点初始化
    std::string postcode;
    int i = 0;

    // 遍历编码字符串，逐步向下查找字符
    while (i < code.size())
    {
        if (HT[k].lchild == 0 && HT[k].rchild == 0)
        {
            postcode.push_back(word[k - 1]);
            k = (n == 1) ? 2 : 2 * n - 1;  // 重置k为根节点
        }
        else
        {
            if (code[i] == '0') k = HT[k].lchild;  // 向左子树走
            else k = HT[k].rchild;  // 向右子树走
            i++;
        }
    }

    // 如果到达叶子节点，返回对应字符，否则返回无效
    if (HT[k].lchild == 0 && HT[k].rchild == 0)
        postcode.push_back(word[k - 1]);
    else
        return "INVALID";

    return postcode;
}

int main()
{
    std::vector<int> num(26, 0);  // 统计每个字母的出现频率
    std::string code;
    std::vector<char> word;

    std::cin >> code;  // 输入待编码字符串

    // 统计字符串中每个字符的频率
    for (int i = 0; i < code.size(); i++)
    {
        num[code[i] - 'a']++;  // 更新频率
        if (num[code[i] - 'a'] == 1)
            word.push_back(code[i]);  // 记录出现的字符
    }

    //根据字符出现顺序记录频率用以创建哈夫曼树
    std::vector<int> a;
    for (int i = 0; i < word.size(); i++)
    {
        if (num[word[i] - 'a'] != 0)
        {
            a.push_back(num[word[i] - 'a']);
            num[word[i] - 'a'] = 0;
        }
    }

    // 创建哈夫曼树
    HuffmanTree_manager<int> manager;
    HuffmanTree<int>* HT = manager.CreatTree(a, a.size());

    std::vector<std::string> codes;
    manager.HuffmanTreeCode(HT, codes, a.size());  // 生成哈夫曼编码

    int pre = code.size();  // 压缩前的大小
    double postbit = 0;
    for (int i = 0; i < a.size(); i++)
    {
        postbit += a[i] * codes[i].size();  // 计算压缩后的位数
    }

    int post = ceil(postbit / 8);  // 计算压缩后的字节数
    std::cout << pre << " " << post << std::endl;  // 输出前后的文本大小

    // 按字符出现次数递增顺序输出编码
    for (int i = 0; i < a.size(); i++)
    {
        int s = 0;
        for (int i = 0; i < a.size(); i++)
        {
            if (a[i] < a[s]) s = i;
        }
        std::cout << word[s] << ":" << codes[s] << std::endl;
        a[s] = INT_MAX;
    }

    // 译码过程
    std::string precode;
    std::cin >> precode;
    std::cout << decode(HT, precode, word, word.size()) << std::endl;

    std::cin >> precode;
    std::cout << decode(HT, precode, word, word.size()) << std::endl;
}

E 罪犯帮派

分数 10

作者 朱允刚

单位 吉林大学

Tabu市的警察局决定结束混乱，因此要采取行动根除城市中的几大帮派。目前的问题是，给出两个罪犯，他们是属于同一帮派么？城市里一共有多少个帮派？假设在Tabu市现有n名罪犯，编号为1到n，给出m条消息表示属于同一帮派的两个罪犯编号。请基于这些不完全的信息帮助警方计算出他们想要的信息。

输入格式:

输入第一行为三个正整数，n、m和q。n为罪犯数；m为给出的已知信息数量；q为查询数。接下来m行，每行2个正整数a和b，表示罪犯a和罪犯b属于同一帮派。接下来q行，每行2个正整数c和d，即查询罪犯c和d是否属于同一帮派。每行输入的整数以空格间隔，n、m、q均不超过1000。

输出格式:

输出为q+1行，前q行对应于输入的q个查询的结果，如果属于同一帮派，则输出“In the same gang.”，否则输出“In different gangs.”。最后一行为一个整数，表示帮派数目。

输入样例:

3 2 1
1 2
2 3
1 3

输出样例:

In the same gang.
1

代码长度限制

16 KB

时间限制

20 ms

内存限制

64 MB

栈限制

8192 KB

解题思路：

典型并查集的模板题

  1. 并查集初始化：
    • crime 数组：用于记录每个节点的父节点，初始时，每个人的父节点指向自己，表示每个人都是一个独立的集合。
    • sizes 数组：用于记录每个集合的大小，初始时每个集合的大小为1。
  2. 查找（Find）：
    • find() 函数用于找到某个元素的根节点，并使用路径压缩优化查询效率。如果当前节点的父节点不是自己，就递归查找其父节点，并将当前节点直接指向根节点，减少查找时间。
  3. 合并（Union）：
    • unite() 函数用于将两个元素所在的集合合并。首先通过 find() 查找它们各自的根节点。如果两个元素已经在同一个集合中，则无需操作；否则，将两个集合合并。合并时选择将较小的集合合并到较大的集合，保持树的平衡，从而避免生成深度过大的树。
  4. 查询（Query）：
    • 对于每个查询，使用 find() 查找两个元素的根节点。如果两个元素的根节点相同，则说明它们属于同一个集合；否则，它们属于不同的集合。
  5. 统计独立的帮派数量：
    • 最后，遍历所有元素，检查哪些元素是根节点（即 crime[i] == i），这些根节点代表了独立的帮派。统计根节点的数量即为独立帮派的数量。
#include<iostream>
#include<vector>
using namespace std;

// 查找操作，带路径压缩
// find()函数用于查找元素x所在的集合，并将路径上所有节点直接指向根节点，达到路径压缩的效果
int find(vector<int>& crime, int x)
{
    // 如果x是集合的根节点（自己指向自己），则返回x
    // 否则，递归查找其父节点，并将路径上的所有节点指向根节点，优化查询效率
    return crime[x] == x ? x : crime[x] = find(crime, crime[x]);
}

// 合并操作
// unite()函数用于将元素x和y所在的集合合并为一个集合
void unite(vector<int>& crime, vector<int>& sizes, int x, int y)
{
    // 找到x和y的根节点
    x = find(crime, x);
    y = find(crime, y);

    // 如果x和y已经在同一个集合中，则不需要合并
    if (x == y) return;

    // 合并时，选择将较小的树合并到较大的树下（按集合大小来合并，优化树的深度）
    if (sizes[x] < sizes[y]) {
        int v = x;
        x = y;
        y = v;
    }

    // 将y所在的集合合并到x所在的集合
    crime[y] = x;
    // 更新x所在集合的大小
    sizes[x] += sizes[y];
}

int main()
{
    int n, m, q;
    // 输入n（总人数），m（合并操作的次数），q（查询次数）
    cin >> n >> m >> q;

    // crime数组用来存储每个节点（即每个人）的父节点，初始时每个人都是自己的父节点
    vector<int> crime;
    // sizes数组用来存储每个集合的大小
    vector<int> sizes;

    // 初始化sizes数组，所有人的集合初始大小为1
    sizes.resize(n + 1, 1);

    // 初始化crime数组，使每个人的父节点都是自己
    for (int i = 0; i <= n; i++)
    {
        crime.push_back(i);
    }

    // 处理m个合并操作
    for (int i = 0; i < m; i++)
    {
        int a, b;
        // 输入每一对需要合并的元素a和b
        cin >> a >> b;
        // 将a和b所在的集合合并
        unite(crime, sizes, a, b);
    }

    // 处理q个查询操作
    for (int i = 0; i < q; i++)
    {
        int x, y;
        // 输入查询的两个元素x和y
        cin >> x >> y;
        // 查找x和y各自的根节点
        x = find(crime, x);
        y = find(crime, y);

        // 如果x和y在同一个集合中，则输出“同一个帮派”
        if (x == y)
        {
            cout << "In the same gang." << endl;
        }
        else
        {
            cout << "In different gangs." << endl;
        }
    }

    // 统计有多少个独立的帮派（即有多少个根节点）
    int count = 0;
    for (int i = 1; i <= n; i++)
    {
        // 如果i是根节点，说明它代表一个独立的帮派
        if (crime[i] == i) count++;
    }

    // 输出独立帮派的数量
    cout << count << endl;
}

F 二叉树路径和II

编写程序找出非空二叉树中和最大的路径，二叉树结点为不等于0的整数。本题的“路径”定义为二叉树中的结点序列v**i,...,v**j，序列中前一个结点是后一个结点的父结点，但路径不一定是以根结点为起点，也不一定是以叶结点为终点。路径的和定义为该路径所包含的所有结点的数据值之和。

输入格式:

输入为一组用空格间隔的整数，个数不超过100个，表示带空指针信息的二叉树先根序列。

输出格式:

输出为两行，第一行为该二叉树路径和的最大值，第二行为一组整数，每个整数后一个空格，表示该最大路径包含的结点值（按所在层数递增顺序输出）。如果存在多条满足条件的路径，则输出最短（包含结点个数最少）者，如果存在多条最短的路径，则输出最靠左上者。

输入样例1:

1 2 0 0 3 0 0

输出样例1:

4
1 3

输入样例2:

-1 2 0 0 3 4 0 0 0

输出样例2:

7
3 4

输入样例3:

3 2 0 0 -1 4 0 0 0

输出样例3:

6
3 -1 4

代码长度限制

16 KB

时间限制

50 ms

内存限制

64 MB

栈限制

8192 KB

解题思路：

  1. 题目分析

二叉树的路径和问题通常与树的深度优先搜索（DFS）有关，因为我们要从根节点递归地访问每一个节点。在这道题中，我们不仅要找到路径和最大值，还需要记录具体的路径，确保路径符合最短和最左的规则。

  1. 动态规划思想

我们可以使用递归来进行深度优先遍历（DFS）。对于每个节点，我们可以计算以下几种情况：

  • 仅从当前节点开始的最大路径和（可能只包含当前节点）。
  • 经过当前节点的最大路径和（可能包括其左子树的路径和以及右子树的路径和）。

  • 对于nowpath，如果路径和已经是负数重置

  • 递归函数设计

我们需要设计一个递归函数来遍历二叉树。每次递归调用时，我们会做以下几件事：

  • 计算最大路径和：对于每个节点，递归计算左子树和右子树的最大路径和。
  • 更新路径：如果当前路径和大于之前记录的最大路径和，就更新最大路径和及其路径。

  • 路径的选择：如果当前路径和等于最大路径和，并且当前路径更短或者更左，则更新路径。

  • 递归策略

对于每个节点，我们有两个选择：

  • 选择从该节点出发的路径。
  • 选择经过该节点的路径，包括其左右子树的路径。

递归的核心是利用后序遍历计算每个子树的最大路径和，并通过返回值来更新全局的最大路径和及路径。

  1. 递归更新全局变量

在递归时，我们两个通过两个比较更新两个信息：

  • 如果有更大路径和：
// 如果当前路径和大于已知的最大路径和，则更新最大路径和及其路径
    if (now_sum > maxworth)
    {
        maxworth = now_sum;

        maxpath.clear();  // 清空最大路径

        for (int i = 0; i < nowpath.size(); i++)
        {
            maxpath.push_back(nowpath[i]);  // 更新最大路径
        }
    }
  • 相同路径和但路径更短：
// 如果当前路径和等于最大路径和，并且当前路径小于最大路径，则更新最大路径
    if (now_sum == maxworth && maxpath.size() > nowpath.size())
    {
        maxpath.clear();
        for (int i = 0; i < nowpath.size(); i++)
        {
            maxpath.push_back(nowpath[i]);  // 更新最大路径
        }
    }

#include<iostream>  // 包含输入输出流的头文件
#include<climits>   // 包含整数限制的头文件，用于INT_MIN等常量
#include<vector>   // 包含向量的头文件

using namespace std;  // 使用标准命名空间

// 定义二叉树节点类
class Tree
{
public:
    int data;  // 节点存储的数据

    Tree* left;  // 指向左子树的指针
    Tree* right;  // 指向右子树的指针

    // 构造函数，初始化数据和子树指针
    Tree(int data) :data(data), left(nullptr), right(nullptr) { }
};

// 递归创建二叉树的函数
void Create(Tree*& tree)
{
    int k;
    cin >> k;  // 从标准输入读取一个整数

    if (k != 0)  // 如果输入不为0，则创建一个新的树节点
    {
        tree = new Tree(k);
    }
    else  // 如果输入为0，则不创建节点，返回
    {
        return;
    }

    Create(tree->left);  // 递归创建左子树
    Create(tree->right);  // 递归创建右子树
}

// 创建并返回二叉树根节点的函数
Tree* CreateRoot()
{
    int k;
    cin >> k;  // 从标准输入读取一个整数

    Tree* root;  // 声明根节点指针

    if (k != 0)  // 如果输入不为0，则创建一个新的根节点
    {
        root = new Tree(k);
    }
    else  // 如果输入为0，则返回空指针
    {
        return nullptr;
    }

    Create(root->left);  // 递归创建左子树
    Create(root->right);  // 递归创建右子树

    return root;  // 返回创建的根节点
}




// 全局变量，用于存储最大路径和及其路径
int maxworth = INT_MIN;
vector<int> maxpath;


// 递归寻找最大路径和的函数
void FindMax(Tree* root, vector<int> nowpath, int now_sum)
{
    if (!root)  // 如果节点为空，则返回
    {
        return;
    }

    if (now_sum <= 0)  // 如果当前路径和小于等于0，则重置路径和和路径
    {
        now_sum = root->data;

        nowpath.clear();  // 清空当前路径

        nowpath.push_back(root->data);  // 添加当前节点到路径
    }
    else  // 如果当前路径和大于0，则继续累加
    {
        now_sum += root->data;

        nowpath.push_back(root->data);  // 添加当前节点到路径
    }

    // 如果当前路径和大于已知的最大路径和，则更新最大路径和及其路径
    if (now_sum > maxworth)
    {
        maxworth = now_sum;

        maxpath.clear();  // 清空最大路径

        for (int i = 0; i < nowpath.size(); i++)
        {
            maxpath.push_back(nowpath[i]);  // 更新最大路径
        }
    }

    // 如果当前路径和等于最大路径和，并且当前路径小于最大路径，则更新最大路径
    if (now_sum == maxworth && maxpath.size() > nowpath.size())
    {
        maxpath.clear();
        for (int i = 0; i < nowpath.size(); i++)
        {
            maxpath.push_back(nowpath[i]);  // 更新最大路径
        }
    }

    // 递归遍历左右子树
    FindMax(root->left, nowpath, now_sum);

    FindMax(root->right, nowpath, now_sum);
}

// 主函数
int main()
{
    Tree* root = CreateRoot();  // 创建并获取根节点

    vector<int> nowpath;  // 声明当前路径

    int now_sum = INT_MIN;  // 初始化当前路径和为最小整数值

    FindMax(root, nowpath, now_sum);  // 寻找最大路径和

    cout << maxworth << endl;  // 输出最大路径和

    for (auto& i : maxpath)  // 输出最大路径
    {
        cout << i << " ";
    }

    cout << endl;  // 输出换行

    system("Pause");  // 暂停，等待用户操作
}

©OZY all right reserved该文件修订时间： 2026-06-25 14:57:48

评论区 - 计算机23级数据结构上机实验（第3-4周）

results matching ""

    No results matching ""