优先队列:priority_queue
Type 为数据类型, Container 为保存数据的容器,Functional 为元素比较方式。
Container 必须是用数组实现的容器,比如 vector, deque 但不能用 list.
STL里面默认用的是 vector. 比较方式默认用 operator<, 所以如果你把后面俩个
参数缺省的话,优先队列就是大顶堆,队头元素最大。
而在求哈夫曼树中,我
们恰恰需要取得堆中最小的元素,于是我们使用如下语句定义一个小顶堆:
priority_queue
关于堆的有关操作如下:
Q.push(x);
将元素 x 放入堆 Q 中。
int a = Q.top();
取出堆顶元素,即最小的元素保存在 a 中。
Q.pop();
弹出堆顶元素,取出后堆会自动调整为一个新的小顶堆。
它的定义与之前我们使用过的队列一样在标准模板库 queue 中,所以在使用
它之前我们必须做相应预处理。
#include
30.哈夫曼树(九度)
1 30.哈夫曼树View Code
2 时间限制:1 秒
3 内存限制:32 兆
4 特殊判题:否
5 题目描述:
6 哈夫曼树,第一行输入一个数 n,表示叶结点的个数。需要用这些叶结点生
7 成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即 weight,题目需要输出
8 所有结点的值与权值的乘积之和。
9 输入:
10 输入有多组数据。
11 每组第一行输入一个数 n,接着输入 n 个叶节点(叶节点权值不超过 100,
12 2<=n<=1000)。
13 输出:
14 输出权值。
15 样例输入:
16 5
17 1 2 2 5 9
18 样例输出:
19 37
1 #includeView Code
2 #include
3 #include
4 #include
5 #include
6 #include
7 using namespace std;
8
9 priority_queue<int , vector<int> , greater<int> > Q; //建立一个小顶堆
10 int main () {
11 int n;
12 while (scanf ("%d",&n) != EOF) {
13 while(Q.empty() == false) Q.pop(); //清空堆中元素
14 for (int i = 1;i <= n;i ++) { //输入n个叶子结点权值
15 int x;
16 scanf ("%d",&x);
17 Q.push(x); //将权值放入堆中
18 }
19 int ans = 0; //保存答案
20 while(Q.size() > 1) { //当堆中元素大于1个
21 int a = Q.top();
22 Q.pop();
23 int b = Q.top();
24 Q.pop(); //取出堆中两个最小元素,他们为同一个结点的左右儿子,且该双亲结点的权值为它们的和
25 ans += a + b; //该父亲结点必为非叶子结点,固累加其权值
26 Q.push(a + b); //将该双亲结点的权值放回堆中
27 }
28 printf("%d\n",ans); //输出答案
29 }
30 return 0;
31 }
32.二叉树遍历(jiu du)
1 二叉树遍历(九度教程第 32 题)Problem
2 时间限制:1 秒
3 内存限制:32 兆
4 特殊判题:否题目描述:
5 二叉树的前序、中序、后序遍历的定义:
6 前序遍历:对任一子树,先访问跟,然后遍历其左子树,最后遍历其右子树;
7 中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树;
8 后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。
9 给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍
10 历与中序遍历能够唯一确定后序遍历)。
11 输入:
12 两个字符串,其长度 n 均小于等于 26。
13 第一行为前序遍历,第二行为中序遍历。二叉树中的结点名称以大写字母表
14 示:A,B,C....最多 26 个结点。
15 输出:
16 输入样例可能有多组,对于每组测试样例,输出一行,为后序遍历的字符串。
17 样例输入:
18 ABC
19 BAC
20 FDXEAG
21 XDEFAG
22 样例输出:
23 BCA
24 XEDGAF
1 #include';//初始化左右儿子为空
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include <string.h>
9 using namespace std;
10 struct Node { //树结点结构体
11 Node *lchild; //左儿子指针
12 Node *rchild; //右儿子指针
13 char c; //结点字符信息
14 }Tree[50]; //静态内存分配数组
15 int loc; //静态数组中已经分配的结点个数
16 Node *creat() { //申请一个结点空间,返回指向其的指针
17 Tree[loc].lchild = Tree[loc].rchild = NULL; cout <'
35.二叉排序树 (Binary Search Tree),(又:二叉搜索树,二叉查找树)
由于各个数字插入的顺序不同,所得到的二叉排序树的形态也很可能不同,
所以不同的插入顺序对二叉排序树的形态有重要的影响。但是,所有的二叉排序
树都有一个共同的特点:若对二叉排序树进行中序遍历,那么其遍历结果必然是
一个递增序列,这也是二叉排序树名字的来由,通过建立二叉排序树就能对原无
序序列进行排序,并实现动态维护。
1 例 3.5 二叉排序树 (九度教程第 3 5 题)problem
2 时间限制:1 秒
3 内存限制:32 兆
4 特殊判题:否
5 题目描述:
6 输入一系列整数,建立二叉排序数,并进行前序,中序,后序遍历。
7 输入:
8 输入第一行包括一个整数 n(1<=n<=100)。接下来的一行包括 n 个整数。
9 输出:
10 可能有多组测试数据,对于每组数据,将题目所给数据建立一个二叉排序树,
11 并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后
12 一个数据之后有一个空格。
13 样例输入:
14 5
15 1 6 5 9 8
16 样例输出:
17 1 6 5 9 8
18 1 5 6 8 9
19 5 8 9 6 1
20 提示:
21 输入中可能有重复元素,但是输出的二叉树遍历序列中重复元素不用输出。
1 #include依次输入n个数字
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include <string.h>
9 using namespace std;
10 struct Node { //二叉树结构体
11 Node *lchild; //左儿子指针
12 Node *rchild; //右儿子指针
13 int c;//保存数字
14 }Tree[110]; //静态数组
15 int loc; //静态数组中被使用元素个数
16 Node *creat() { //申请未使用的结点
17 Tree[loc].lchild = Tree[loc].rchild = NULL;
18 return &Tree[loc ++];
19 }
20 void postOrder(Node *T) { //后序遍历
21 if (T -> lchild != NULL) {
22 postOrder(T -> lchild);
23 }
24 if (T -> rchild != NULL) {
25 postOrder(T -> rchild);
26 }
27 printf("%d ",T -> c);
28 }
29 void inOrder(Node *T) { //中序遍历
30 if (T -> lchild != NULL) {
31 inOrder(T -> lchild);
32 }
33 printf("%d ",T -> c);
34 if (T -> rchild != NULL) {
35 inOrder(T -> rchild);
36 }
37 }
38 void preOrder(Node *T) { //前序遍历
39 printf("%d ",T -> c);
40 if (T -> lchild != NULL) {
41 preOrder(T -> lchild);
42 }
43 if (T -> rchild != NULL) {
44 preOrder(T -> rchild);
45 }
46 }
47 Node *Insert(Node *T,int x) { //插入数字
48 if (T == NULL) { //若当前树为空
49 T = creat(); //建立结点
50 T -> c = x; //数字直接插入其根结点
51 return T; //返回根结点指针
52 }
53 else if (xc) //若x小于根结点数值
54 T -> lchild = Insert(T -> lchild,x); //插入到左子树上
55 else if (x > T->c) //若x大于根结点数值
56 T -> rchild = Insert(T -> rchild,x); //插入到右子树上.若根结点数值与x一样,根据题目要求直接忽略
57 return T; //返回根节点指针
58 }
59 int main () {
60 int n;
61 while (scanf ("%d",&n) != EOF) {
62 loc = 0;
63 Node *T = NULL; //二叉排序树树根结点为空
64 for (int i = 0;i//
1 例 3.6 二叉搜索树(九度教程第 36 题)problem
2 时间限制:1 秒
3 内存限制:32 兆
4 特殊判题:否
5 题目描述:
6 判断两序列是否为同一二叉搜索树序列
7 输入:
8 开始一个数 n,(1<=n<=20) 表示有 n 个需要判断,n= 0 的时候输入结束。
9 接下去一行是一个序列,序列长度小于 10,包含(0~9)的数字,没有重复数字,
10 根据这个序列可以构造出一颗二叉搜索树。
11 接下去的 n 行有 n 个序列,每个序列格式跟第一个序列一样,请判断这两个
12 序列是否能组成同一颗二叉搜索树。
13 输出:
14 如果序列相同则输出 YES,否则输出 NO
15 样例输入:
16 2
17 567432
18 543267
19 576342
20 0
21 样例输出:
22 YES
23 NO
1 #includeView Code
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include <string.h>
9 using namespace std;
10
11 struct Node { //树节点结构体
12 Node *lchild;
13 Node *rchild;
14 int c;
15 }Tree[110];
16 int loc;
17 Node *creat() { //申请结点空间
18 Tree[loc].lchild = Tree[loc].rchild = NULL;
19 return &Tree[loc ++];
20 }
21 char str1[25] , str2[25]; //保存二叉排序树的遍历结果,将每一棵树的前序遍历得到的字符串与中序遍历得到的字符串连接,得到遍历结果字符串
22 int size1 , size2; //保存在字符数组中的遍历得到字符个数
23 char *str; //当前正在保存字符串
24 int *size; //当前正在保存字符串中字符个数
25 void postOrder(Node *T) { //前序遍历
26 if (T -> lchild != NULL) {
27 postOrder(T -> lchild);
28 }
29 if (T -> rchild != NULL) {
30 postOrder(T -> rchild);
31 }
32 str[ (*size) ++ ] = T -> c + '0'; //将结点中的字符放入正在保存的字符串中
33 }
34 void inOrder(Node *T) { //中序遍历
35 if (T -> lchild != NULL) {
36 inOrder(T -> lchild);
37 }
38 str[ (*size) ++ ] = T -> c + '0';
39 if (T -> rchild != NULL) {
40 inOrder(T -> rchild);
41 }
42 }
43 Node *Insert(Node *T,int x) { //将数字插入二叉树
44 if (T == NULL) {
45 T = creat();
46 T -> c = x;
47 return T;
48 }
49 else if (xc)
50 T -> lchild = Insert(T -> lchild,x);
51 else if (x > T->c)
52 T -> rchild = Insert(T -> rchild,x);
53 return T;
54 }
55 int main () {
56 int n;
57 char tmp[12];
58 while (scanf ("%d",&n) != EOF && n != 0) {
59 loc = 0; //初始化静态空间为未使用
60 Node *T = NULL;
61 scanf ("%s",tmp); //输入字符串
62 for (int i = 0;tmp[i] != 0;i ++) {
63 T = Insert(T,tmp[i] - '0'); //按顺序将数字插入二叉排序树
64 }
65 size1 = 0; //保存在第一个字符串中的字符初始化为0
66 str = str1; //将正在保存字符串设定为第一个字符串
67 size = &size1; //将正在保存字符串中的字符个数指针指向size1
68 postOrder(T); //前序遍历
69 inOrder(T); //中序遍历
70 str1[ size1 ] = 0; //向第一个字符串的最后一个字符后添加空字符,方便使用字符串函数
71 while(n -- != 0) { //输入n个其它字符串
72 scanf ("%s",tmp); //输入
73 Node *T2 = NULL;
74 for (int i = 0;tmp[i] != 0;i ++) { //建立二叉排序树
75 T2 = Insert(T2,tmp[i] - '0');
76 }
77 size2 = 0; //第二个字符串保存字符初始化为0
78 str = str2; //将正在保存字符串设定为第二个字符串
79 size = &size2; //正在保存字符串中字符数量指针指向size2
80 postOrder(T2); //前序遍历
81 inOrder(T2); //中序遍历
82 str2[ size2 ] = 0; //字符串最后添加空字符
83 puts (strcmp(str1,str2) == 0 ? "YES" : "NO"); //比较两个遍历字符串,若相同则输出YES,否则输出NO
84 }
85 }
86 return 0;
87 }