实验07 赫夫曼编码及综合
二叉树的每个结点都有一个权值，从根结点到每个叶子结点将形成一条路径，每条路径的权值等于路径上所有结点的权值和。编程求出二叉树的最大路径权值。第三行先输入n表示有n个叶子，接着输入n个数据表示n个叶子的权值，权值的顺序和前面输入的大写字母顺序对应。第三行先输入n表示二叉树的结点数量，然后输入每个结点的权值，权值顺序与前面结点输入顺序对应。第二行先输入n，表示第1个实例有n个权值，接着输入n个权值，权
·
文章目录
A. DS树–带权路径和
时间限制
1s
内存限制
128MB
题目描述
计算一棵二叉树的带权路径总和，即求赫夫曼树的带权路径和。
已知一棵二叉树的叶子权值，该二叉树的带权案路径和APL等于叶子权值乘于根节点到叶子的分支数，然后求总和。如下图中，叶子都用大写字母表示，权值对应为：A-7，B-6，C-2，D-3
树的带权路径和 = 71 + 62 + 23 + 33 = 34
本题二叉树的创建参考前面的方法
输入
第一行输入一个整数t，表示有t个二叉树
第二行输入一棵二叉树的先序遍历结果，空树用字符‘0’表示，注意输入全是英文字母和0，其中大写字母表示叶子
第三行先输入n表示有n个叶子，接着输入n个数据表示n个叶子的权值，权值的顺序和前面输入的大写字母顺序对应
以此类推输入下一棵二叉树
输出
输出每一棵二叉树的带权路径和
输入样例1
2
xA00tB00zC00D00
4 7 6 2 3
ab0C00D00
2 10 20
输出样例1
34
40
代码
#include <bits/stdc++.h>
using namespace std;
int a[1000];//每个叶子的重量
int cnt;//几个叶子
int we[10000];//每个叶子的权重
char cha[1000];//每个叶子是什么
class BiTreeNode {
public:
char data;
int wei = 0;
int deep;
BiTreeNode *LeftChild;
BiTreeNode *RightChild;
BiTreeNode() : LeftChild(NULL), RightChild(NULL) {}
~BiTreeNode() {}
};
class BiTree {
private:
BiTreeNode *Root;
int pos, pos2;
string strTree;
BiTreeNode *CreateBiTree(int d);
int cal(BiTreeNode *t);
public:
BiTree() {}
~BiTree() {}
void CreateTree(string TreeArray);
void cal();
};
void BiTree::CreateTree(string TreeArray) {
pos = 0;
pos2 = 0;
strTree.assign(TreeArray);
Root = CreateBiTree(1);
}
BiTreeNode *BiTree::CreateBiTree(int d) {
BiTreeNode *T;
char ch;
ch = strTree[pos++];
if (ch == '0')
T = NULL;
else {
T = new BiTreeNode();
T->data = ch;
T->deep=d;
if (T->data <= 'Z' && T->data >= 'A')
T->wei = a[pos2++];
T->LeftChild = CreateBiTree(d+1);
T->RightChild = CreateBiTree(d+1);
}
return T;
}
void BiTree::cal() {
cout << cal(Root)<<endl;
}
int BiTree::cal(BiTreeNode *t) {
if(t==NULL) return 0;
if(t->LeftChild==NULL&&t->RightChild==NULL)
return (t->deep-1)*(t->wei);
int m=cal(t->LeftChild);
int n=cal(t->RightChild);
return m+n;
}
int main(void) {
int t, i, cnt;
string str;
cin >> t;
while (t--) {
BiTree p;
cin >> str;
int pos = 0;
for (i = 0; str[i] != '\0'; i++)
if (str[i] <= 'Z' && str[i] >= 'A') cha[pos++] = str[i];
cha[pos] = '\0';
cin >> cnt;
for (i = 0; i < cnt; i++)
cin >> a[i];
p.CreateTree(str);
p.cal();
}
return 0;
}
B. DS二叉树–赫夫曼树的构建与编码（含代码框架）
题目描述
给定n个权值，根据这些权值构造huffman树，并进行huffman编码
参考课本算法，注意数组访问是从位置1开始
要求：赫夫曼的构建中，默认左孩子权值不大于右孩子权值
代码框架参考如下：
输入
第一行输入t，表示有t个测试实例
第二行先输入n，表示第1个实例有n个权值，接着输入n个权值，权值全是小于1万的正整数
依此类推
输出
逐行输出每个权值对应的编码，格式如下：权值-编码
即每行先输出1个权值，再输出一个短划线，再输出对应编码，接着下一行输入下一个权值和编码。
以此类推
输入样例1
1
5 15 4 4 3 2
输出样例1
15-1
4-010
4-011
3-001
2-000
代码
#include <bits/stdc++.h>
using namespace std;
const int MaxW = 9999;
class HuffNode {
public:
int weight, parent, leftchild, rightchild;
};
class HuffMan {
private:
void MakeTree();
void SelectMin(int pos, int *s1, int *s2);
public:
int len;
int num;
HuffNode *huffTree;
string *huffCode;
void MakeTree(int n, int wt[]);
void Coding();
void Destroy();
};
void HuffMan::MakeTree(int n, int wt[]) {
int i;
num = n;
len = 2 * n - 1;
huffTree = new HuffNode[2 * n];
huffCode = new string[num + 1];
for (i = 1; i <= n; i++)
huffTree[i].weight = wt[i - 1];
for (i = 1; i <= len; i++) {
if (i > n) huffTree[i].weight = 0;
huffTree[i].parent = 0;
huffTree[i].leftchild = 0;
huffTree[i].rightchild = 0;
}
MakeTree();
}
void HuffMan::SelectMin(int pos, int *s1, int *s2) {
int w1, w2, i;
w1 = w2 = MaxW;
*s1 = *s2 = 0;
for (i = 1; i <= pos; i++) {
if (huffTree[i].weight < w1 && huffTree[i].parent == 0) {
w2 = w1;
*s2 = *s1;
w1 = huffTree[i].weight;
*s1 = i;
} else {
if (huffTree[i].weight < w2 && huffTree[i].parent == 0) {
w2 = huffTree[i].weight;
*s2 = i;
}
}
}
}
void HuffMan::MakeTree() {
int i, s1, s2;
for (i = num + 1; i <= len; i++) {
SelectMin(i - 1, &s1, &s2);
huffTree[s1].parent = i;
huffTree[s2].parent = i;
huffTree[i].leftchild = s1;
huffTree[i].rightchild = s2;
huffTree[i].weight = huffTree[s1].weight+huffTree[s2].weight;
}
}
void HuffMan::Destroy() {
len = 0;
num = 0;
delete[]huffTree;
delete[]huffCode;
}
void HuffMan::Coding() {
char *cd;
int i, c, f, start;
cd = new char[num];
cd[num - 1] = '\0';
for (i = 1; i <= num; i++) {
start = num - 1;
for (c = i, f = huffTree[i].parent; f != 0; c = f, f = huffTree[f].parent) {
if (huffTree[f].leftchild == c) cd[--start] = '0';
else cd[--start] = '1';
}
huffCode[i].assign(&cd[start]);
}
delete[]cd;
}
int main() {
int t, n, i, j;
int wt[800]= {0};
HuffMan myHuff;
cin >> t;
while (t--) {
cin >> n;
for (i = 0; i < n; i++)
cin >> wt[i];
myHuff.MakeTree(n, wt);
myHuff.Coding();
for (j = 1; j <= n; j++) {
cout << myHuff.huffTree[j].weight << '-';
cout << myHuff.huffCode[j] << endl;
}
myHuff.Destroy();
}
return 0;
}
C. DS二叉树–赫夫曼树解码（含代码框架）
题目描述
已知赫夫曼编码算法和程序，在此基础上进行赫夫曼解码
在赫夫曼树的类定义中增加了一个公有方法：
int Decode(const string codestr, char txtstr[]);//输入编码串codestr，输出解码串txtstr
该方法如果解码成功则返回1，解码失败则返回-1，本程序增加宏定义ok表示1，error表示-1
解码方法的代码框架如下：
输入
第一行输入t，表示有t个测试实例
第二行先输入n，表示第1个实例有n个权值，接着输入n个权值，权值全是小于1万的正整数
第三行输入n个字母，表示与权值对应的字符
第四行输入k，表示要输入k个编码串
第五行起输入k个编码串
以此类推输入下一个示例
输出
每行输出解码后的字符串，如果解码失败直接输出字符串“error”，不要输出部分解码结果
输入样例1
2
5 15 4 4 3 2
A B C D E
3
11111
10100001001
00000101100
4 7 5 2 4
A B C D
3
1010000
111011
111110111
输出1
AAAAA
ABEAD
error
BBAAA
error
DCD
代码
#include <bits/stdc++.h>
using namespace std;
#define ok 1
#define error -1
const int MaxW = 9999;
char jie[800]= {'#'};
class HuffNode {
public:
int weight, parent, leftchild, rightchild;
char charecter;
};
class HuffMan {
private:
void MakeTree();
void SelectMin(int pos, int *s1, int *s2);
public:
int len;
int num;
HuffNode *huffTree;
string *huffCode;
void MakeTree(int n, int wt[], char ch[]);
int Decode(const string codestr, char txtstr[]);
void Coding();
void Destroy();
};
void HuffMan::MakeTree(int n, int wt[], char ch[]) {
int i;
num = n;
len = 2 * n - 1;
huffTree = new HuffNode[2 * n];
huffCode = new string[num + 1];
for (i = 1; i <= n; i++) {
huffTree[i].weight = wt[i - 1];
huffTree[i].charecter = ch[i - 1];
}
for (i = 1; i <= len; i++) {
if (i > n) {
huffTree[i].weight = 0;
huffTree[i].charecter = '#';
}
huffTree[i].parent = 0;
huffTree[i].leftchild = 0;
huffTree[i].rightchild = 0;
}
MakeTree();
}
void HuffMan::SelectMin(int pos, int *s1, int *s2) {
int w1, w2, i;
w1 = w2 = MaxW;
*s1 = *s2 = 0;
for (i = 1; i <= pos; i++) {
if (huffTree[i].weight < w1 && huffTree[i].parent == 0) {
w2 = w1;
*s2 = *s1;
w1 = huffTree[i].weight;
*s1 = i;
} else {
if (huffTree[i].weight < w2 && huffTree[i].parent == 0) {
w2 = huffTree[i].weight;
*s2 = i;
}
}
}
}
void HuffMan::MakeTree() {
int i, s1, s2;
for (i = num + 1; i <= len; i++) {
SelectMin(i - 1, &s1, &s2);
huffTree[s1].parent = i;
huffTree[s2].parent = i;
huffTree[i].leftchild = s1;
huffTree[i].rightchild = s2;
huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;
}
}
int HuffMan::Decode(const string codestr, char txtstr[]) {
int i, k, c;
char ch;
c = len;// len是 2*n +1
k = 0;
for (i = 0; i < codestr.size(); i++) {
ch = codestr[i];
if (ch == '0') c = huffTree[c].leftchild;
else if (ch == '1') c = huffTree[c].rightchild;
else return error;
if (huffTree[c].leftchild == NULL && huffTree[c].rightchild == NULL) {
txtstr[k] = huffTree[c].charecter;
k++;
c = len;
} else ch = '\0';
}
if (ch == '\0') return error;
else txtstr[k] = '\0';
return ok;
}
void HuffMan::Destroy() {
len = 0;
num = 0;
delete[]huffTree;
delete[]huffCode;
}
void HuffMan::Coding() {
char *cd;
int i, c, f, start;
cd = new char[num];
cd[num - 1] = '\0';
for (i = 1; i <= num; i++) {
start = num - 1;
for (c = i, f = huffTree[i].parent; f != 0; c = f, f = huffTree[f].parent) {
if (huffTree[f].leftchild == c) cd[--start] = '0';
else cd[--start] = '1';
}
huffCode[i].assign(&cd[start]);
}
delete[]cd;
}
int main() {
int t, n, i, j;
int wt[800] = {0};
char ch[800] = {'#'};
HuffMan myHuff;
cin >> t;
while (t--) {
string yuan;
cin >> n;
for (i = 0; i < n; i++)
cin >> wt[i];
for (i = 0; i < n; i++)
cin >> ch[i];
myHuff.MakeTree(n, wt, ch);
myHuff.Coding();
int key;
cin>>key;
for(j=0;j<key;j++){
cin>>yuan;
if(myHuff.Decode(yuan,jie)==1) cout<<jie<<endl;
else if(myHuff.Decode(yuan,jie)==-1) cout<<"error"<<endl;
}
myHuff.Destroy();
}
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个
输入样例1 <-复制
2
AB0C00D00
4 5 3 2 6
ABCD00E000FG00H0I00
9 5 4 11 7 2 8 13 4 1
输出样例1
11
27
代码
#include <bits/stdc++.h>
using namespace std;
int a[1000];//每个节点的重量
int cnt;//几个节点
int we[10000];//每个节点的权重
char cha[1000];//每个节点是什么
class BiTreeNode {
public:
char data;
int wei = 0;
int deep;
BiTreeNode *LeftChild;
BiTreeNode *RightChild;
BiTreeNode() : LeftChild(NULL), RightChild(NULL) {}
~BiTreeNode() {}
};
class BiTree {
private:
BiTreeNode *Root;
int pos,pos2;
string strTree;
BiTreeNode *CreateBiTree(int d);
int cal(BiTreeNode *t);
public:
BiTree() {}
~BiTree() {}
void CreateTree(string TreeArray);
void cal();
};
void BiTree::CreateTree(string TreeArray) {
pos = 0;
pos2=0;
strTree.assign(TreeArray);
Root = CreateBiTree(1);
}
BiTreeNode *BiTree::CreateBiTree(int d) {
BiTreeNode *T;
char ch;
ch = strTree[pos++];
if (ch == '0')
T = NULL;
else {
T = new BiTreeNode();
T->data = ch;
T->deep=d;
T->wei = a[pos2++];
T->LeftChild = CreateBiTree(d+1);
T->RightChild = CreateBiTree(d+1);
}
return T;
}
void BiTree::cal() {
cout << cal(Root)<<endl;
}
int BiTree::cal(BiTreeNode *t) {
if(t==NULL) return 0;
if(t->LeftChild==NULL&&t->RightChild==NULL)
return t->wei;
int m=cal(t->LeftChild);
int n=cal(t->RightChild);
return max(m,n)+t->wei;
}
int main(void) {
int t, i, cnt;
string str;
cin >> t;
while (t--) {
BiTree p;
cin >> str;
cin >> cnt;
for (i = 0; i < cnt; i++)
cin >> a[i];
p.CreateTree(str);
p.cal();
}
return 0;
}
E. DS森林叶子编码
题目描述
给定一组森林，编写程序生成对应的二叉树，输出这颗二叉树叶结点对应的二进制编码.规定二叉树的左边由0表示，二叉树的右边由1表示。
输入：
N B 表示N个树，每结点最多B个分支
第2行至第N+1行，每个树的先序遍历
输出
每行表示一个叶结点对应的二进制编码.
输入样例1 <-复制
3 3
A B 0 0 0 C 0 0 0 D 0 0 0
E F 0 0 0 0 0
G H 0 0 0 I J 0 0 0 0 0 0
输出样例1
0 1 1
1 0
1 1 0 1 0
代码
#include <bits/stdc++.h>
using namespace std;
int B,N;
class BiTreeNode {
public:
char data;
int wei = 0;
BiTreeNode *LeftChild;
BiTreeNode *RightChild;
BiTreeNode() : LeftChild(NULL), RightChild(NULL) {}
};
class TreeNode {
public:
char data2;
TreeNode**Child;
TreeNode() {
Child=new TreeNode*[B];
for(int i=0; i<B; i++)
Child[i]=NULL;
}
};
class Tree {
private:
TreeNode *root;
TreeNode* Create() {
TreeNode* T=NULL;
char ch;
cin>>ch;
if(ch!='0') {
T = new TreeNode();
T->data2 = ch;
for(int j=0; j<B; j++)
T->Child[j] = Create();
}
return T;
}
BiTreeNode* change(TreeNode* t) {
BiTreeNode* p=NULL;
if(t!=NULL) {
p=new BiTreeNode;
p->data=t->data2;
p->LeftChild=change(t->Child[0]);
if(p->LeftChild){
BiTreeNode *r=p->LeftChild;
for(int i=1;i<B;i++){
r->RightChild=change(t->Child[i]);
if(r->RightChild) r=r->RightChild;
}
}
}
return p;
}
public:
void Create2() {
root= Create();
}
BiTreeNode* change() {
return change(root);
}
};
class BiTree {
private:
BiTreeNode *Root;
void prin(BiTreeNode *t,string s){
if(t){
if(t->LeftChild==NULL&&t->RightChild==NULL){
int L;
L=s.size();
s=s.substr(0,L-1);
cout<<s<<endl;
}
prin(t->LeftChild,s+"0 ");
prin(t->RightChild,s+"1 ");
}
}
public:
BiTree() {}
~BiTree() {}
void connect(BiTreeNode **t){
for(int i=0;i<N-1;i++)
t[i]->RightChild=t[i+1];
Root=t[0];
}
void prin(){
string str="";
prin(Root,str);
}
};
int main(void) {
int i;
cin >> N>>B;
Tree*F=new Tree[N];
BiTreeNode **Bi=new BiTreeNode*[N];
for(i=0; i<N; i++)
F[i].Create2();
for(i=0; i<N; i++)
Bi[i]=F[i].change();
BiTree tr;
tr.connect(Bi);
tr.prin();
return 0;
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
3
0- 0
已为社区贡献2条内容
所有评论(0)