先来学习二叉搜索树BST。BST满足左子树<根<右子树，中序序列是有序序列。使用递归或双指针的循环法构建二叉树。双指针法即给出待插入的节点位置以及其父亲节点位置。
第一题是二叉排序树。
#include <iostream>
#include <stdio.h>
using namespace std;
struct TreeNode{int data;TreeNode* left;TreeNode* right;
};
void InsertBST(TreeNode* &root, int data){TreeNode* pNew = new TreeNode;pNew->data = data;pNew->left = NULL;pNew->right = NULL;if(root == NULL){root = pNew;printf("-1\n");}else {TreeNode * pCur = root;//用于向下探索TreeNode* pPre;//pPre指向pCur的父亲while(1){if(pCur->data > data){pPre = pCur;pCur = pCur->left;if(pCur == NULL){pPre->left = pNew;printf("%d\n",pPre->data);break;}}else {pPre = pCur;pCur = pCur->right;if(pCur == NULL){pPre->right = pNew;printf("%d\n", pPre->data);break;}}}}
}
int main()
{int n;scanf("%d",&n);TreeNode* root = NULL;for(int i = 0; i<n;i++){int val;scanf("%d", &val);InsertBST(root, val);}return 0;
}第二题是二叉搜索树。注意读字符串以“\0”为结尾。
#include <stdio.h>
#include <vector>
using namespace std;
struct Treenode {char data;Treenode* left;Treenode* right;
};
void bulidBST(Treenode*& root, char num) {Treenode* pNew = new Treenode;pNew->data = num;pNew->left = NULL;pNew->right = NULL;if (root == NULL) {root = pNew;} else {Treenode* pCur = root;Treenode* pPre;while (1) {if (pCur->data - num > 0) {pPre = pCur;pCur = pCur->left;if (pCur == NULL) {pPre->left = pNew;break;}} else {pPre = pCur;pCur = pCur->right;if (pCur == NULL) {pPre->right = pNew;break;}}}}
}
void Preoerder(Treenode* root, vector<char>& vec) {if (root == NULL) return;else {vec.push_back(root->data);Preoerder(root->left, vec);Preoerder(root->right, vec);}
}
int main() {int n;scanf("%d", &n);char num[10];scanf("%s", num);Treenode* root1 = NULL;for (int j = 0; num[j] != '\0'; j++) {bulidBST(root1, num[j]);//build tree}vector<char> res;Preoerder(root1, res);// for(int i =0;i<res.size();i++){// printf("%c", vec[i]);// }for (int i = 0; i < n; i++) {char num1[10];scanf("%s", num1);Treenode* root = NULL;for (int j = 0; num1[j] != '\0'; j++) {bulidBST(root, num1[j]);//build tree}vector<char> vec;Preoerder(root, vec);bool issame = true;for (int k = 0; k < res.size(); k++) {if (res[k] != vec[k]) issame = false;}if (issame == true) printf("YES\n");else printf("NO\n");}}第三题是二叉搜索树。照葫芦画瓢。
#include <stdio.h>
using namespace std;
struct Treenode{int data;Treenode* left;Treenode* right;
};
void bulidBST(Treenode* &root, int num){Treenode* pNew = new Treenode;pNew->data = num;pNew->left = NULL;pNew->right = NULL;if(root == NULL){root = pNew;}else{Treenode* pPre;Treenode* pCur = root;while(1){if(pCur->data>num){pPre = pCur;pCur = pCur->left;if(pCur == NULL){pPre->left = pNew;break;}}else if(pCur->data < num){pPre = pCur;pCur = pCur->right;if(pCur == NULL){pPre->right = pNew;break;}}else break;}}
}
void Preorder(Treenode* root){if(root == NULL) return;else{printf("%d ", root->data);Preorder(root->left);Preorder(root->right);}
}
void Inorder(Treenode* root){if(root == NULL) return;else{Inorder(root->left);printf("%d ", root->data);Inorder(root->right);}
}
void Postorder(Treenode* root){if(root == NULL) return;else{Postorder(root->left);Postorder(root->right);printf("%d ", root->data);}
}
int main(){int n;scanf("%d", &n);Treenode* root = NULL;for(int i = 0; i<n;i++){int num;scanf("%d", &num);bulidBST(root, num);}Preorder(root);printf("\n");Inorder(root);printf("\n");Postorder(root);printf("\n");
}第四题是二叉搜索树。超时了。
#include <stdio.h>
using namespace std;
struct Treenode{int data;int parent;Treenode* left;Treenode* right;
};
void buildBST(Treenode* &root, int num){Treenode* pNew = new Treenode;pNew->data = num;pNew->parent = 0;pNew->left =NULL;pNew->right = NULL;if(root == NULL){root = pNew;}else{Treenode* pPre;Treenode* pCur = root;while(1){if(pCur->data>num){pPre = pCur;pCur = pCur->left;if(pCur == NULL){pPre->left = pNew;pNew->parent = pPre->data;break;}}else if(pCur->data < num){pPre = pCur;pCur = pCur->right;if(pCur == NULL){pPre->right = pNew;pNew->parent = pPre->data;break;}}else break;}}
}
void findParent(Treenode* root, int num){if(root == NULL) return;else{if(root->data==num) printf("%d ", root->parent);else if (root->data>num) findParent(root->left, num);else findParent(root->right, num);}
}
int main(){int n;scanf("%d", &n);Treenode* root = NULL;for(int i = 0; i<n;i++){int num;scanf("%d",&num);buildBST(root, num);//建立二叉树}for(int i = 1; i<n+1;i++){findParent(root, i);}
}下面学习优先队列。优先队列每次出最大的，优先队列的底层由二叉堆实现。二叉堆是一棵完全二叉树，可以顺序存储。大根堆满足根大于左孩子且根大于右孩子。小根堆则相反。使用时包含头文件#include <queue>。priority_queue<int> myque。支持pop出队列中的最大值，push入队，top获取对首，就是最大值。empty判断队列是否为空。Type类型必须支持< 运算符。想实现小根堆，可以修改<运算符的含义（用于自定义类），或者取相反数（用于int等）。
第五题是复数集合。
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <climits>
#include <string>
using namespace std;
struct Fnum {int x;int y;int m;
};
bool cmp(Fnum left, Fnum right) {if (left.m < right.m) return true; //左边小右边大else if (left.m == right.m && left.y > right.y) return true;else return false;
}
int main() {int n;vector<Fnum> res;while (scanf("%d", &n) != EOF) {char op[10];for (int i = 0; i < n; i++) {scanf("%s", op);string op1 = op;if (op1 == "Pop") {if (res.size() == 0) printf("empty\n");else {sort(res.begin(), res.end(), cmp);printf("%d+i%d\n", res[res.size() - 1].x, res[res.size() - 1].y);res.pop_back();printf("SIZE = %d\n", (int)res.size());}} else if (op1 == "Insert") {char num[100];scanf("%s", num);string str = "";int i;for (i = 0; num[i] != '+'; i++) {str += num[i];}int a = stoi(str);str = "";for (int j = i + 2; num[j] != '\0'; j++) {str += num[j];}int b = stoi(str);Fnum newnode;newnode.x = a;newnode.y = b;newnode.m = a * a + b * b;res.push_back(newnode);printf("SIZE = %d\n", (int)res.size());}}}}#include <stdio.h>#include <string>#include <queue>using namespace std;struct Complex {int re;int im;//构造函数 简化初始化的过程//构造函数 在类的内部 名字和类名一样 没有返回值Complex(int re1, int im1){re = re1;im = im1;}};// 自定义一个 < 运算符 //运算符重载//重载<号 原本的小于号 有两个参数 返回值是bool//自定义一个函数 参数的个数不变 返回值的类型不变 //名字是operator 运算符//若left<right返回真 大根堆//若left<right 返回false 小根堆bool operator < (Complex lhs, Complex rhs){// lhs的模小于rhs的模if(lhs.re*lhs.re + lhs.im*lhs.im < rhs.re*rhs.re + rhs.im*rhs.im){return true;}else if(lhs.re*lhs.re + lhs.im*lhs.im == rhs.re*rhs.re + rhs.im*rhs.im){return lhs.im > rhs.im;}else{return false;}}int main() {int n;scanf("%d", &n);priority_queue<Complex> pqueue;for (int i = 0; i < n; ++i) {char actionArr[30];scanf("%s", actionArr);string action = actionArr;if (action == "Pop") {if (pqueue.empty()) {printf("empty\n");}else {printf("%d+i%d\n", pqueue.top().re, pqueue.top().im);pqueue.pop();printf("SIZE = %d\n", pqueue.size());}}else if (action == "Insert") {int re, im;scanf("%d+i%d", &re, &im); //格式化输入//Complex c;//c.re = re;//c.im = im;Complex c(re,im);pqueue.push(c);printf("SIZE = %d\n", pqueue.size());}}return 0;}第六题是中位数。
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main(){int n;while(scanf("%d", &n)!=EOF){if(n == 0) break;vector<int> res;for(int i = 0;i<n;i++){int m;scanf("%d", &m);res.push_back(m);}sort(res.begin(), res.end());int size = res.size();if(size%2 == 1) printf("%d\n", res[(size-1)/2]);else{printf("%d\n", (res[(size/2)]+res[(size/2)-1])/2);}}
}
第七题是哈夫曼树。首先维护一个小根堆，选出最小的两个，wpl加上最小的两个值，合并后插回小根堆。知道堆中只有一个元素即可返回wpl。
#include <stdio.h>
#include <queue>
using namespace std;
int main() {int n;priority_queue<int> myque;while (scanf("%d", &n) != EOF) {for (int i = 0; i < n; i++) {int m;scanf("%d", &m);myque.push(-1 * m);}int wpl = 0;while (1) {if (myque.size() < 2) break;int num1 = myque.top();myque.pop();int num2 = myque.top();myque.pop();wpl = wpl + num2 + num1;myque.push(num2 + num1);}printf("%d\n", -1 * (wpl));}
}
第八题是搬水果。就是wpl。
#include <stdio.h>
#include <queue>
using namespace std;
int main() {int n;scanf("%d", &n);priority_queue<int> myque;for (int i = 0; i < n; i++) {int m;scanf("%d", &m);myque.push(-1 * m);}int wpl = 0;while (myque.size() >= 2) {int num1 = myque.top();myque.pop();int num2 = myque.top();myque.pop();wpl += num2 + num1;myque.push(num2 + num1);}printf("%d", -1 * wpl);
}