百度站长工具网站提交,网站建设属于行政那个模块,大学生个体创业的网站建设,建筑公司网站的目标用户A. 【程序填空】赫夫曼编码题目描述给定n个叶子的权值#xff0c;根据这些权值构造huffman树#xff0c;并输出huffman编码参考课本第6.6节的算法6.12#xff0c;注意算法中数组访问是从位置1开始赫夫曼构建中#xff0c;默认左孩子权值不大于右孩子权值如果遇到两个孩子权…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或HCvoid 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];cinn;for(int i0;in;i)cinwt[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;cinn;for(i0;in;i)cinwt[i];for(i0;in;i)cinct[i];HuffMan huff(n,wt, ct);huff.buildTree(); //构建赫夫曼树cini;while (i--){ cincstr;huff.Decoding(cstr); //赫夫曼解码}return 0;
}C. DS树--带权路径和题目描述计算一棵二叉树的带权路径总和即求赫夫曼树的带权路径和。已知一棵二叉树的叶子权值该二叉树的带权案路径和APL等于叶子权值乘于根节点到叶子的分支数然后求总和。如下图中叶子都用大写字母表示权值对应为A-7B-6C-2D-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,sum0; //标识建树字符串的当前字符位置int* arry;int j 0;//路径数组下标int road[100];int high0;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-leftChildNULL t-rightChildNULL){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-5B-4C-11D-7E-2F-8G-13H-4I-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
#includequeue
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;queueint 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;Maxroad0;while (n--){int e;cin e;weights.push(e);}getRoad(root, 0);cout Maxroadendl ;}int main(void)
{int t;cin t;while (t--){HuffmanTree myTree;myTree.CreateTree();myTree.getRoad();}return 0;
}E. DS二叉树—二叉树镜面反转题目描述假设二叉树用二叉链表存储用先序序列结果创建。输入二叉树的先序序列请你先创建二叉树并对树做个镜面反转再输出反转后的二叉树的先序遍历、中序遍历、后序遍历和层序遍历的序列。所谓镜面反转是指将所有非叶结点的左右孩子对换。 --程序要求--程序中不允许使用STL库等第三方对象或函数实现本题的要求输入测试次数t每组测试数据是一个二叉树的先序遍历序列#表示空树输出对每棵二叉树输出镜面反转后的先序、中序、后序和层次遍历序列。如果空树输出四个NULL后面不加空格每个NULL独自一行中间没有空行。如下NULLNULLNULLNULL输入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 代码#includeiostream
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,temp0;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();}
}
