第十章 非线性数据结构

/*
* 题目名称：二叉树遍历
* 题目来源：华中科技大学复试上机题
* 题目链接：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;
}