实验07 赫夫曼编码及综合2022(带程序填空)

A. 【程序填空】赫夫曼编码

题目描述

给定n个叶子的权值，根据这些权值构造huffman树，并输出huffman编码

参考课本第6.6节的算法6.12，注意算法中数组访问是从位置1开始

赫夫曼构建中，默认左孩子权值不大于右孩子权值

如果遇到两个孩子权值相等，那么按输入顺序或生成顺序来排列。

例如有一个叶子权值是29，后来生成一个中间结点权值也是29，那么叶子为左孩子，中间结点为右孩子

例如有两个叶子权值都是4，那么按输入顺序，先输入权值的叶子是左孩子

请完成以下程序填空

输入

第1行输入n，表示有n个叶子

第2行输入n个权值，权值都是正整数

输出

输出n行，每行输出格式：权值-赫夫曼编码

请参考样例

输入：

8
5 29 7 8 14 23 3 11

输出：

5-0001
29-10
7-1110
8-1111
14-110
23-01
3-0000
11-001

代码：

#include <iostream>
#include <cstring>
#include <string>
#include <sstream>    
using namespace std;const int maxW = 9999;       //设定无穷大权值//Huffman树结点结构
class HuffNode {    //哈夫曼树的结点结构
public:int weight;        //权值int parent;        //双亲下标int lchild;    //左孩子下标int rchild;    //右孩子下标
};//Huffman树结构
class HuffMan {
private:int len;        //结点总数，等于lnum*2-1int lnum;        //叶子数量HuffNode *HuffTree;    //保存构建后的赫夫曼树信息void selectMin(int n, int &x1, int &x2);  
//函数selectMin是从已生成的n个结点中(包含叶子)，选出未选的且权值最小的两个结点的下标
//两个下标结果保存在x1和x2中
//第一小权值的结点下标保存在x1，第二小权值的结点下标保存在x2
//如果不想用这个函数，就在类外定义中定义一个空函数体，避免语法错误string *HuffCode; //保存叶子的赫夫曼编码char ** HC;        //保存叶子的赫夫曼编码
//如果不喜欢用string，可以用二维字符数组HC
//HuffCode和HC，两者只用一个保存赫夫曼编码就可以了 public:HuffMan(int n,int w[]); //输入叶子数量和叶子权重，初始化HuffTree和HuffCode（或HC）void buildTree();        //构建赫夫曼树，保存在HuffTree中void Coding();            //生成赫夫曼编码，保存在HuffCode或HC中void printCode();        //输出赫夫曼编码~HuffMan();                //回收空间
};//请完成Huffman树的剩下部分类定义
HuffMan ::~HuffMan() {delete[]HuffTree;delete[]HuffCode;len = 0; lnum = 0;
}void HuffMan::selectMin(int n, int& x1, int& x2) {int j;x1 = 0; x2 = 0;for (j = 1; j < n; j++) {if (HuffTree[j].parent == 0) {if (x1 == 0)x1 = j;else if (x2 == 0) x2 = j;if (HuffTree[j].weight < HuffTree[x1].weight) {x2 = x1; x1 = j;}else if (x2 != 0 && HuffTree[j].weight < HuffTree[x2].weight) x2 = j;}}
}HuffMan::HuffMan(int n, int w[]) {lnum = n;len = 2 * lnum - 1;HuffTree = new HuffNode[len + 1];HuffCode = new string[lnum + 1];//位置从1开始int i = 1;for (i = 1; i <= len; i++) {HuffTree[i].weight = 0;HuffTree[i].lchild = 0;HuffTree[i].rchild = 0;HuffTree[i].parent = 0;}for (i = 1; i <= lnum; i++)HuffTree[i].weight = w[i - 1];
}void HuffMan::buildTree() {int x1, x2;for (int i = lnum + 1; i <= len; i++) {selectMin(i, x1, x2);HuffTree[x1].parent = i;HuffTree[x2].parent = i;HuffTree[i].lchild = x1;HuffTree[i].rchild = x2;HuffTree[i].weight = HuffTree[x1].weight + HuffTree[x2].weight;}
}void HuffMan::Coding() {int  i, j, c, f;         // c,f是结点在数组中的下标for (i = 1; i <= lnum; i++) { // c,f是结点在数组中的下标for (c = i, f = HuffTree[i].parent; f != 0; c = f, f = HuffTree[f].parent) {if (c == HuffTree[f].lchild) HuffCode[i] = '0' + HuffCode[i];else HuffCode[i] = '1' + HuffCode[i];}}
}void HuffMan::printCode() {for (int i = 1; i <= lnum; i++)cout << HuffTree[i].weight << "-" << HuffCode[i] << endl;
}
//主函数如下
int main(void)
{    int n, wt[100];cin>>n;for(int i=0;i<n;i++)cin>>wt[i];HuffMan huff(n,wt);huff.buildTree();huff.Coding();huff.printCode();return 0;
}

B. 【程序填空】赫夫曼解码

题目描述

在掌握赫夫曼树构建的基础上，实现赫夫曼解码

赫夫曼构建中，默认左孩子权值不大于右孩子权值

如果遇到两个孩子权值相等，那么按输入顺序或生成顺序来排列。

例如有一个叶子权值是29，后来生成一个中间结点权值也是29，那么叶子为左孩子，中间结点为右孩子

例如有两个叶子权值都是4，那么按输入顺序，先输入权值的叶子是左孩子

请完成以下程序填空

输入

第一行输入n，表示有n个叶子

第二行输入n个叶子权值，权值全是正整数

第三行输入n个叶子对应的字符，权值全是正整数

第四行输入k，表示要输入k个编码串

接着输入k个编码串

输出

输出k行，每行输出一个编码串的解码结果。

如果编码串非法，则对应的一行输出error，不输出已解码的字符

输入：

5
15 4 4 3 2
K G C M W
2
11011010000001
0000011100010

输出：

KKCGWM
error

代码：

#include <iostream>
#include <string>
using namespace std;const int maxW = 9999;       //设定无穷大权值//Huffman树结点结构
class HuffNode {    //哈夫曼树的结点结构
public:char letter;//结点对应的字符int weight;    //权值int parent;    //双亲下标int lchild;    //左孩子下标int rchild;    //右孩子下标
};//Huffman树结构
class HuffMan {
private:int len;        //结点总数，等于lnum*2-1int lnum;        //叶子数量HuffNode *HuffTree;    //保存构建后的赫夫曼树信息void selectMin(int n, int &x1, int &x2);  
//函数selectMin是从已生成的n个结点中(包含叶子)，选出未选的且权值最小的两个结点的下标
//两个下标结果保存在x1和x2中
//第一小权值的结点下标保存在x1，第二小权值的结点下标保存在x2
//如果不想用这个函数，就在类外定义中定义一个空函数体，避免语法错误public:HuffMan(int n,int w[], char c[]); 
//构造函数HuffMan根据输入叶子数量、叶子权重、字符集合，初始化HuffTreevoid buildTree();        //构建赫夫曼树，保存在HuffTree中void Decoding(string cs);    
//函数Decoding是根据参数编码串cs进行赫夫曼解码
//如果编码串cs有错，函数Decoding直接输出error，不输出已解码的字符~HuffMan();    //回收HuffTree空间  
};
//以下完成Huffman类的定义填空
HuffMan::~HuffMan() {if (HuffTree) delete[]HuffTree;len = lnum = 0;
}void HuffMan::selectMin(int n,int &x1,int &x2) {x1 = x2 = 0;for (int i = 1; i <= n; i++) {if (HuffTree[i].parent == 0) {if (x1 == 0) x1 = i;else if (x2 == 0)x2 = i;if (HuffTree[i].weight < HuffTree[x1].weight) {x2 = x1; x1 = i;}else if (x2 != 0 && HuffTree[i].weight < HuffTree[x2].weight)x2 = i;}}
}HuffMan::HuffMan(int n,int w[],char c[]) {lnum = n;len = 2 * n - 1;HuffTree = new HuffNode[len + 1];for (int i = 1; i <= len; i++) {HuffTree[i].weight = 0;HuffTree[i].lchild = 0;HuffTree[i].rchild = 0;HuffTree[i].letter = 0;HuffTree[i].parent = 0;}for (int i = 1; i <= lnum; i++) {HuffTree[i].weight = w[i - 1];HuffTree[i].letter = c[i - 1];}
}
void HuffMan::buildTree() {int x1, x2;for (int i = lnum + 1; i <= len; i++) {selectMin(i - 1, x1, x2);HuffTree[x1].parent = i;HuffTree[x2].parent = i;HuffTree[i].lchild = x1;HuffTree[i].rchild = x2;HuffTree[i].weight = HuffTree[x1].weight + HuffTree[x2].weight;}
}void HuffMan::Decoding(string cs) {string decode;int k = len;for (int i = 0; i < cs.length(); i++) {if (cs[i] == '0') {if (HuffTree[k].lchild)k = HuffTree[k].lchild;else {cout << "error" << endl;return;}}else {if (HuffTree[k].rchild)k = HuffTree[k].rchild;else {cout << "error" << endl;return;}}if (HuffTree[k].lchild == 0 && HuffTree[k].rchild == 0) {decode += HuffTree[k].letter;k = len;}}if (k == len) cout << decode << endl;else cout << "error" << endl;
}
int main()
{    int i, n, wt[100];char ct[100];string cstr;cin>>n;for(i=0;i<n;i++)cin>>wt[i];for(i=0;i<n;i++)cin>>ct[i];HuffMan huff(n,wt, ct);huff.buildTree();    //构建赫夫曼树cin>>i;while (i--){    cin>>cstr;huff.Decoding(cstr); //赫夫曼解码}return 0;
}

C. DS树--带权路径和

题目描述

计算一棵二叉树的带权路径总和，即求赫夫曼树的带权路径和。

已知一棵二叉树的叶子权值，该二叉树的带权案路径和APL等于叶子权值乘于根节点到叶子的分支数，然后求总和。如下图中，叶子都用大写字母表示，权值对应为：A-7，B-6，C-2，D-3

树的带权路径和 = 7*1 + 6*2 + 2*3 + 3*3 = 34

本题二叉树的创建参考前面的方法

输入

第一行输入一个整数t，表示有t个二叉树

第二行输入一棵二叉树的先序遍历结果，空树用字符‘0’表示，注意输入全是英文字母和0，其中大写字母表示叶子

第三行先输入n表示有n个叶子，接着输入n个数据表示n个叶子的权值，权值的顺序和前面输入的大写字母顺序对应

以此类推输入下一棵二叉树

输出

输出每一棵二叉树的带权路径和

输入：

2
xA00tB00zC00D00
4 7 6 2 3
ab0C00D00
2 10 20

输出：

34
40

#include <iostream>
#include <string>
using namespace std;
class BiTreeNode {
public:char  data;                    //数据域BiTreeNode* leftChild, * rightChild;    //左右子树指针BiTreeNode() :leftChild(NULL), rightChild(NULL) {}~BiTreeNode() {}
};class BiTree {
private:BiTreeNode* root;    //根结点指针string sTree;        //建树字符串int pos,sum=0;            //标识建树字符串的当前字符位置int* arry;int j = 0;//路径数组下标int road[100];int high=0;BiTreeNode* CreateTree();//建树私有函数void PreOrder(BiTreeNode* t);    //先序遍历实现void InOrder(BiTreeNode* t);    //中序遍历实现void PostOrder(BiTreeNode* t);    //后序遍历实现void findroad(BiTreeNode* t);
public:BiTree() :root(NULL) {};void Create(string vArray,int arr[],int n);    //建树公有接口，参数是特定的先序遍历字符串void PreOrder();            //先序遍历公有接口void InOrder();                //中序遍历公有接口void PostOrder();            //后序遍历公有接口void findroad();void calculate();
};
//二叉树公有接口的实现
void BiTree::Create(string vArray,int arr[],int n)
{pos = 0;sTree.assign(vArray);    //把参数保存到内部字符串root = CreateTree();    //建树成功后root指向根结点arry = new int[n];for (int i = 0; i < n; i++)arry[i] = arr[i];/*for (int i = 0; i < n; i++)cout << arry[i];*/
}
void BiTree::PreOrder()
{PreOrder(root);
}
void BiTree::InOrder()
{InOrder(root);
}
void BiTree::PostOrder()
{PostOrder(root);
}
void BiTree::findroad()
{findroad(root);
}
//请完成上述类内部的私有函数实现
BiTreeNode* BiTree::CreateTree()
{BiTreeNode* node;int l = sTree.length();if (sTree[pos] != '0'){node = new BiTreeNode;node->data = sTree[pos];pos++;node->leftChild = CreateTree();node->rightChild = CreateTree();}else{pos++;node = NULL;}return node;
}
void BiTree::PreOrder(BiTreeNode* t)
{if (t == NULL)return;cout << t->data;PreOrder(t->leftChild);PreOrder(t->rightChild);}
void BiTree::InOrder(BiTreeNode* t)
{if (t == NULL)return;InOrder(t->leftChild);cout << t->data;InOrder(t->rightChild);
}
void BiTree::PostOrder(BiTreeNode* t)
{if (t == NULL)return;PostOrder(t->leftChild);PostOrder(t->rightChild);cout << t->data;
}
void BiTree::findroad(BiTreeNode* t)
{if (t!=NULL){if (t->leftChild==NULL && t->rightChild==NULL){road[j] = high;j++;}else{if (t->leftChild != NULL){high++;findroad(t->leftChild);}if (t->rightChild != NULL){high++;findroad(t->rightChild);}}high--;}
}
void BiTree::calculate() 
{/*cout << j << endl;*/for (int i = 0; i < j; i++){sum += arry[i] * road[i];}cout << sum << endl;
}//主函数
int main()
{int t;string vArray;cin >> t;while (t--){cin >> vArray;BiTree myTree;int n;cin >> n;int* a = new int[n];for (int i = 0; i < n; i++){cin >> a[i];}myTree.Create(vArray,a,n);myTree.findroad();myTree.calculate();/*myTree.PreOrder();        cout << endl;*//*myTree.InOrder();        cout << endl;myTree.PostOrder();        cout << endl;*/delete[]a;}return 0;
}

D. DS树--二叉树之最大路径

题目描述

给定一颗二叉树的逻辑结构（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构

二叉树的每个结点都有一个权值，从根结点到每个叶子结点将形成一条路径，每条路径的权值等于路径上所有结点的权值和。编程求出二叉树的最大路径权值。如下图所示，共有4个叶子即有4条路径，

路径1权值=5 + 4 + 11 + 7 = 27路径2权值=5 + 4 + 11 + 2 = 22

路径3权值=5 + 8 + 13 = 26路径4权值=5 + 8 + 4 + 1 = 18

可计算出最大路径权值是27。

该树输入的先序遍历结果为ABCD00E000FG00H0I00，各结点权值为：

A-5，B-4，C-11，D-7，E-2，F-8，G-13，H-4，I-1

输入

第一行输入一个整数t，表示有t个测试数据

第二行输入一棵二叉树的先序遍历，每个结点用字母表示

第三行先输入n表示二叉树的结点数量，然后输入每个结点的权值，权值顺序与前面结点输入顺序对应

以此类推输入下一棵二叉树

输出

每行输出每棵二叉树的最大路径权值，如果最大路径权值有重复，只输出1个

输入：

2
AB0C00D00
4 5 3 2 6
ABCD00E000FG00H0I00
9 5 4 11 7 2 8 13 4 1

输出：

11
27

代码：

#include <iostream>
#include<queue>
using namespace std;class HTNode
{
private:char data;int weight;HTNode* lchild, * rchild;
public:HTNode() :weight(0), lchild(NULL), rchild(NULL) {}~HTNode() {}friend class HuffmanTree;
};class HuffmanTree
{
private:HTNode* root;int LeafNum;int Maxroad;queue<int> weights;
public:~HuffmanTree();void CreateTree();void CreateTree(HTNode*& p, int& i, int& j);void getRoad();void getRoad(HTNode* p, int Level);
};HuffmanTree::~HuffmanTree()
{delete root;}void HuffmanTree::CreateTree(HTNode*& p, int& i, int& j)
{char c;cin >> c;if (c == '0') { p = NULL;}else {p = new HTNode;p->data = c;CreateTree(p->lchild, i, j);CreateTree(p->rchild, i, j);}}void HuffmanTree::CreateTree()
{int i = 0;int j = 0;CreateTree(root, i, j);
}void  HuffmanTree::getRoad(HTNode* t, int road)
{if (t){    t->weight = weights.front() + road;weights.pop();getRoad(t->lchild, t->weight);getRoad(t->rchild, t->weight);if (!t->lchild && !t->rchild)if (t->weight > Maxroad)Maxroad = t->weight;}}
void HuffmanTree::getRoad() {int n;cin >> n;Maxroad=0;while (n--){int e;cin >> e;weights.push(e);}getRoad(root, 0);cout << Maxroad<<endl ;}int main(void)
{int t;cin >> t;while (t--){HuffmanTree myTree;myTree.CreateTree();myTree.getRoad();}return 0;
}

E. DS二叉树—二叉树镜面反转

题目描述

假设二叉树用二叉链表存储，用先序序列结果创建。输入二叉树的先序序列，请你先创建二叉树，并对树做个镜面反转，再输出反转后的二叉树的先序遍历、中序遍历、后序遍历和层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。

--程序要求--

程序中不允许使用STL库等第三方对象或函数实现本题的要求

输入

测试次数t

每组测试数据是一个二叉树的先序遍历序列，#表示空树

输出

对每棵二叉树，输出镜面反转后的先序、中序、后序和层次遍历序列。如果空树，输出四个NULL（后面不加空格，每个NULL独自一行，中间没有空行）。如下：

NULL

NULL

NULL

NULL

输入：

3
41#32###65##7##
AB#C##D##
AB##C##

输出：

4 6 7 5 1 3 2 
7 6 5 4 3 2 1 
7 5 6 2 3 1 4 
4 6 1 7 5 3 2 
A D B C 
D A C B 
D C B A 
A D B C 
A C B 
C A B 
C B A 
A C B 

代码：

#include<iostream>
using namespace std;
class node {
public:char data;node* left, * right;node() { left = right = NULL; }~node(){}
};
class tree {node* root;int pos;string str;node* createtree();void preOrder(node* root);void inOrder(node* root);void postOrder(node* root);void levelOrder(node* root);void exchange(node* root);
public:void create(string s);void inOrder();void preOrder();void postOrder();void exchange();void levelOrder();
};
void tree::exchange() {if (root != NULL) {exchange(root);}
}
void tree::exchange(node* root) {if (root != NULL) {exchange(root->left);exchange(root->right);node* p = new node();p = root->left;root->left = root->right;root->right = p;}
}
void tree::create(string s) {pos = 0;str = s;root = createtree();
}
node* tree::createtree() {node* p = new node();char c = str[pos++];if (c == '#') p = NULL;else {p->data = c;p->left = createtree();p->right = createtree();}return p;
}
void tree::preOrder() {if (str[0] == '#') cout << "NULL";else preOrder(root);cout << endl;
}
void tree::preOrder(node* root) {if (root) {cout << root->data << ' ';preOrder(root->left);preOrder(root->right);}
}
void tree::inOrder() {if (str[0] == '#') cout << "NULL";else inOrder(root);cout << endl;
}
void tree::inOrder(node* root) {if (root) {inOrder(root->left);cout << root->data << ' ';inOrder(root->right);}
}
void tree::postOrder() {if (str[0] == '#') cout << "NULL";else postOrder(root);cout << endl;
}
void tree::postOrder(node* root) {if (root) {postOrder(root->left);postOrder(root->right);cout << root->data << ' ';}
}
void tree::levelOrder() {if (str[0] == '#') cout << "NULL";else levelOrder(root);cout << endl;
}
void tree::levelOrder(node* root) {//不给用STL，有点大病）node** que = new node*[100];for (int i = 0; i < 100; i++) que[i] = new node();int front = 0, rear = 0,temp=0;node* p = root;que[temp++] = p; rear++;while (1) {p = que[front];front++;cout << p->data << " ";if (p->left) {que[temp++] = p->left; rear++;}if (p->right) {que[temp++] = p->right; rear++;}if (front == rear) break;}
}
int main() {int t; cin >> t;string s;while (t--) {cin >> s;tree t;t.create(s);t.exchange();t.preOrder();t.inOrder();t.postOrder();t.levelOrder();}
}