/*
* 题目名称：二叉树遍历
* 题目来源：华中科技大学复试上机题
* 题目链接：http://t.cn/AiKgDfLU
* 代码作者：杨泽邦(炉灰)
*/#include <iostream>
#include <cstdio>
#include <string>using namespace std;struct TreeNode {char data;TreeNode* leftChild;TreeNode* rightChild;TreeNode(char c): data(c), leftChild(NULL), rightChild(NULL) {}
};TreeNode* Build(string str1, string str2) {if (str1.size() == 0) { //返回空树return NULL;}char current = str1[0]; //当前字符TreeNode* root = new TreeNode(current); //创建新节点int position = str2.find(current); //寻找切分点root -> leftChild = Build(str1.substr(1, position), str2.substr(0, position));root -> rightChild = Build(str1.substr(position + 1), str2.substr(position + 1));return root;
}void PostOrder(TreeNode* root) { //后序遍历if (root == NULL) {return;}PostOrder(root->leftChild);PostOrder(root->rightChild);printf("%c", root->data);return;
}int main() {string str1, str2;while (cin >> str1 >> str2) {TreeNode* root = Build(str1, str2);PostOrder(root);printf("\n");}return 0;
}
/*
* 题目名称：二叉排序树
* 题目来源：华中科技大学复试上机题
* 题目链接：http://t.cn/AiKD0L5V
* 代码作者：杨泽邦(炉灰)
*/#include <iostream>
#include <cstdio>using namespace std;struct TreeNode {int data;TreeNode* leftChild;TreeNode* rightChild;TreeNode(int x): data(x), leftChild(NULL), rightChild(NULL) {}
};TreeNode* Insert(TreeNode* root, int x) {if (root == NULL) { //创建新节点root = new TreeNode(x);} else if (x < root->data) { //插入左子树root->leftChild = Insert(root->leftChild, x);} else if (root->data < x) { //插入右子树root->rightChild = Insert(root->rightChild, x);}return root;
}void PreOrder(TreeNode* root) { //前序遍历if (root == NULL) {return;}printf("%d ", root->data);PreOrder(root->leftChild);PreOrder(root->rightChild);return;
}void InOrder(TreeNode* root) { //中序遍历if (root == NULL) {return;}InOrder(root->leftChild);printf("%d ", root->data);InOrder(root->rightChild);return;
}void PostOrder(TreeNode* root) { //后序遍历if (root == NULL) {return;}PostOrder(root->leftChild);PostOrder(root->rightChild);printf("%d ", root->data);return;
}int main() {int n;while (scanf("%d", &n) != EOF) {TreeNode* root = NULL; //建立空树for (int i = 0; i < n; ++i) { //逐个插入int x;scanf("%d", &x);root = Insert(root, x);}PreOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");}return 0;
}
//优先队列
#include <iostream>
#include <cstdio>
#include <queue>using namespace std;priority_queue<int> myPriorityQueue;int main()
{int arr[10] = {3, 2, 4, 1, 5, 6, 9, 0, 8, 7};for(int i = 0; i < 10; ++i){myPriorityQueue.push(arr[i]);}int sum = 0;while (!myPriorityQueue.empty()){printf("%d",myPriorityQueue.top());sum += myPriorityQueue.top;myPriorityQueue.pop();}printf("\n%d\n",sum);return 0;
}
/*
* 题目名称：复数集合
* 题目来源：北京邮电大学复试上机题
* 题目链接：http://t.cn/Ai98yYlt
* 代码作者：杨泽邦(炉灰)
*/#include <iostream>
#include <cstdio>
#include <queue>
#include <string>using namespace std;struct Complex {int real; //实部int imag; //虚部Complex(int r, int i): real(r), imag(i) {}bool operator< (Complex c) const { //重载小于号if (real * real + imag * imag == c.real * c.real + c.imag * c.imag) {return imag > c.imag;} else {return real * real + imag * imag < c.real * c.real + c.imag * c.imag;}}
};int main() {int n;while (scanf("%d", &n) != EOF) {priority_queue<Complex> myPriorityQueue;while (n--) {string str;cin >> str;if (str == "Pop") {if (myPriorityQueue.empty()) {printf("empty\n");} else {Complex current = myPriorityQueue.top();myPriorityQueue.pop();printf("%d+i%d\n", current.real, current.imag);printf("SIZE = %d\n", myPriorityQueue.size());}} else {int a, b;scanf("%d+i%d", &a, &b);myPriorityQueue.push(Complex(a, b));printf("SIZE = %d\n", myPriorityQueue.size());}}}return 0;
}
/*
* 题目名称：哈夫曼树
* 题目来源：北京邮电大学复试上机题
* 题目链接：http://t.cn/AiCuGMki
* 代码作者：杨泽邦(炉灰)
*/#include <iostream>
#include <cstdio>
#include <queue>using namespace std;int main() {int n;while (scanf("%d", &n) != EOF) {priority_queue<int, vector<int>, greater<int> > myPriorityQueue;while (n--) {int x;scanf("%d", &x);myPriorityQueue.push(x);}int answer = 0;while (1 < myPriorityQueue.size()) {int a = myPriorityQueue.top();myPriorityQueue.pop();int b = myPriorityQueue.top();myPriorityQueue.pop();answer += a + b;myPriorityQueue.push(a + b);}printf("%d\n", answer);}return 0;
}
//映射
#include <iostream>
#include <cstdio>
#include <map>
#include <unorder_map>using namespace std;map<string,int> myMap;int main()
{myMap["Emma"] = 67;myMap["Benedict"] = 100;myMap.insert(pair<string,int>("Bob",72));myMap.insert(pair<string.int>("Mary",85));cout << "the score of Benedict: " << myMap["Benedict"] << endl;cout << "the score of Mary: " << myMap.at("Mary") << endl << endl;myMap.erase("Benedict");map<string,int>::iterator it; //定义迭代器for(it = myMap.begin();it != myMap.end(); it++){cout << "the score of " << it->first << ": " << it->second << endl;}it = myMap.find("Bob");if(it != myMap.end()){cout << "Bob is found" << endl;}else{cout << "Bob is not found" << endl;}cout << "the size of myMap: " << myMap.size();return 0;
}
/*
* 题目名称：查找学生信息
* 题目来源：清华大学复试上机题
* 题目链接：http://t.cn/AiCuVIuY
* 代码作者：杨泽邦(炉灰)
*/#include <iostream>
#include <cstdio>
#include <map>using namespace std;map<string, string> student;int main() {int n;scanf("%d", &n);getchar(); //吃掉回车for (int i = 0; i < n; ++i) {string str;getline(cin, str);int position = str.find(' '); //分界点string key = str.substr(0, position); //学号作为关键字student[key] = str; //信息作为映射值}int m;scanf("%d", &m);for (int i = 0; i < m; ++i) {string key;cin >> key;string answer = student[key];if (answer == "") { //找不到该学生answer = "No Answer!";}cout << answer << endl;}return 0;
}
