类实现

时间限制: 1 Sec  内存限制: 128 MB

题目描述

给出一个数据序列，建立二叉排序树，并实现查找功能

对二叉排序树进行中序遍历，可以得到有序的数据序列

输入

第一行输入t，表示有t个数据序列

第二行输入n，表示首个序列包含n个数据

第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开

第四行输入m，表示要查找m个数据

从第五行起，输入m行，每行一个要查找的数据，都是自然数

以此类推输入下一个示例

输出

第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到

从第二行起，输出查找结果，如果查找成功输出查找次数，如果查找失败输出-1

以此类推输出下一个示例的结果

样例输入

1
6
22 33 55 66 11 44
7
11
22
33
44
55
66
77

样例输出

11 22 33 44 55 66
2
1
2
4
3
4
-1

解决方案

#include <iostream>
class Tree {
private:
    struct Node {
        int data;
        Node *leftChild, *rightChild;
        Node() = default;
        explicit Node(int data) : data(data), leftChild(nullptr), rightChild(nullptr) {}
    };
    Node *_root{};
    static void addRoot(int data, Node* parent) {
        if (data > parent->data) {
            if (parent->rightChild == nullptr) {
                parent->rightChild = new Node(data);
            } else {
                addRoot(data, parent->rightChild);
            }
        } else {
            if (parent->leftChild == nullptr) {
                parent->leftChild = new Node(data);
            } else {
                addRoot(data, parent->leftChild);
            }
        }
    }
    static int find(Node *root, int index, int *times) {
        (*times)++;
        if (root->data == index) {
            return *times;
        } else if (root->data < index) {
            if (root->rightChild == nullptr) {
                return -1;
            } else {
                return find(root->rightChild, index, times);
            }
        } else {
            if (root->leftChild == nullptr) {
                return -1;
            } else {
                return find(root->leftChild, index, times);
            }
        }
    }
    void print(Node *node) {
        if (node->leftChild != nullptr) {
            print(node->leftChild);
        }
        std::cout << node->data << " ";
        if (node->rightChild != nullptr) {
            print(node->rightChild);
        }
    }
public:
    explicit Tree(int data) {
        _root = new Node(data);
    }
    void addRoot(int data) {
        addRoot(data, _root);
    }
    void print() {
        print(_root->leftChild);
        std::cout << _root->data << " ";
        print(_root->rightChild);
        std::cout << std::endl;
    }
    int find(int index) {
        int times = 0;
        return find(_root, index, &times);
    }
};
int main() {
    size_t T;
    std::cin >> T;
    while (T--) {
        int size, data;
        std::cin >> size;
        std::cin >> data;
        Tree tree(data);
        for (int i = 1; i < size; ++i) {
            std::cin >> data;
            tree.addRoot(data);
        }
        tree.print();
        int count;
        std::cin >> count;
        while (count--) {
            int index;
            std::cin >> index;
            std::cout << tree.find(index) << std::endl;
        }
    }
}

括号匹配

时间限制: 1 Sec  内存限制: 128 MB

题目描述

处理表达式过程中需要对括号匹配进行检验，括号匹配包括三种：“(”和“)”，“[”和“]”，“{”和“}”。例如表达式中包含括号如下：

( ) [ ( ) ( [ ] )  ]  {  }
1 2 3 4 5 6 7 8 9 10 11 12

从上例可以看出第1和第2个括号匹配，第3和第10个括号匹配，4和5匹配，6和9匹配，7和8匹配，11和12匹配。从中可以看到括号嵌套的的情况是比较复杂的，使用堆栈可以很方便的处理这种括号匹配检验，可以遵循以下规则：

1、 当接收第1个左括号，表示新的一组匹配检查开始；随后如果连续接收到左括号，则不断进堆栈。

2、 当接受第1个右括号，则和最新进栈的左括号进行匹配，表示嵌套中1组括号已经匹配消除

3、 若到最后，括号不能完全匹配，则说明输入的表达式有错

建议使用C++自带的stack对象来实现

stack类使用的参考代码

//n包含头文件<stack>  ：
#include <stack>
//n创建一个堆栈对象s（注意stack是模板类）：
stack <char>  s;
//堆栈的数据类型是字符型n把一个字符ct压入堆栈：
s.push(ct);
//n把栈顶元素弹出：
s.pop();
//n获取栈顶元素，放入变量c2：
c2 = s.top();

n判断堆栈是否空： s.empty()，如果为空则函数返回true，如果不空则返回false

输入

第一行输入一个t，表示下面将有t组测试数据。接下来的t行的每行输入一个表达式，表达式只考虑英文半角状态输入，无需考虑中文全角输入

输出

对于每一行的表达式，检查括号是否匹配，匹配则输入ok，不匹配则输出error

样例输入

2
(a+b)[4*5+(-6)]
[5*8]/{(a+b)-6

样例输出

ok
error

提示

算法流程

1、初始化，i=0，建立堆栈，栈为空

2、输入表达式，建立指针指向表达式的头部

3、读入表达式的第i个字符

4、如果第i个字符是左括号，入栈

5、如果第i个字符是右括号，检查栈顶元素是否匹配

   A.如果匹配，弹出栈顶元素

   B.如果不匹配，报错退出

6、i++，指向下一个字符，是否已经表达式末尾

   A. 未到末尾，重复步骤3

   B. 已到达末尾

      a. 堆栈为空，输出ok

      b. 堆栈不为空，输出error

解决方案

#include <iostream>
#include <stack>
#include <string>
bool isBracketMatch(std::string &str) {
    std::stack<char> s;
    for (char i : str) {
        switch (i) {
            case '(':
            case '[':
            case '{':
                s.push(i);
                break;
            case ')':
                if (s.top() == '(') {
                    s.pop();
                } else {
                    return false;
                }
                break;
            case ']':
                if (s.top() == '[') {
                    s.pop();
                } else {
                    return false;
                }
                break;
            case '}':
                if (s.top() == '{') {
                    s.pop();
                } else {
                    return false;
                }
                break;
            default:
                break;
        }
    }
    return s.empty();
}
int main() {
    int n;
    std::cin >> n;
    while (n--) {
        std::string str;
        std::cin >> str;
        if (isBracketMatch(str)) {
            std::cout << "ok" << std::endl;
        } else {
            std::cout << "error" << std::endl;
        }
    }
}

KMP算法

时间限制: 1 Sec  内存限制: 128 MB

题目描述

学习KMP算法，给出主串和模式串，求模式串在主串的位置

输入

第一个输入t，表示有t个实例

第二行输入第1个实例的主串，第三行输入第1个实例的模式串

以此类推

输出

第一行输出第1个实例的模式串的next值

第二行输出第1个实例的匹配位置，位置从1开始计算，如果匹配成功输出位置，匹配失败输出0

以此类推

样例输入

3 qwertyuiop tyu aabbccdd ccc aaaabababac abac 

样例输出

-1 0 0  5 -1 0 1  0 -1 0 0 1  8 

提示

 为什么next值和课本的不一样？？？

解决方案

#include <iostream>
#include <string>
class MyString {
private:
    std::string mainStr; //串
    static void getNext(std::string p, int next[]) {
        next[0] = -1;
        next[1] = 0;
        int temp = 0;
        int L = p.length();
        for (int i = 2; i < L; ++i) { //从第二个字符开始，依次计算next的值
            while (temp > 0 && p[i - 1] != p[temp]) {
                temp = next[temp];
            }
            if (p[i - 1] == p[temp]) {
                temp++;
            }
            next[i] = temp;
        }
    };
    int KMPFind(std::string p, const int next[]) {
        int i = 0, j = 0;
        while (mainStr[i] != '\0' && p[j] != '\0') {
            if (mainStr[i] == p[j]) {
                ++i;
                ++j;
            } else {
                j = next[j];
            }
            if (j == -1) {
                ++i;
                ++j;
            }
        }
        if (p[j] == '\0') {
            return i - j;
        } else {
            return -1;
        }
    };
public:
    MyString(); //构造函数
    ~MyString(); //析构函数
    void setVal(const std::string &sp); //设定主串字符内容和长度
    int KMPFindSubstr(const std::string &p);
};
MyString::MyString() { //构造函数，定义对象并赋初始串值
    mainStr = "";
}
MyString::~MyString() { //析构函数
    mainStr = "";
}
void MyString::setVal(const std::string &sp) {
    mainStr = "";
    mainStr.assign(sp);
}
int MyString::KMPFindSubstr(const std::string &p) { //主串从pos开始查找子串p。找到返回p在主串开始的位置，否贼返回-1
    int L = p.length();
    int *next = new int[L];
    getNext(p, next);
    for (int j = 0; j < L; ++j) {
        std::cout << next[j] << ' ';
    }
    std::cout << std::endl;
    int v = KMPFind(p, next);
    delete[]next;
    return v;
}
int main() {
    size_t t;
    std::cin >> t;
    while (t--) {
        std::string mainStr, subStr;
        std::cin >> mainStr;
        std::cin >> subStr;
        MyString myString;
        myString.setVal(mainStr);
        std::cout << myString.KMPFindSubstr(subStr) + 1 << std::endl;
    }
}

二叉树构建与遍历

时间限制: 1 Sec  内存限制: 128 MB

题目描述

 给定一颗二叉树的逻辑结构。

（先序遍历的结果，空树用字符‘#’表示，例如AB#C##D##），建立该二叉树的二叉链式存储结构，并输出该二叉树的先序遍历、中序遍历和后序遍历结果。

输入

 第一行输入一个整数t，表示有t个二叉树

第二行起输入每个二叉树的先序遍历结果，空树用字符‘#’表示，连续输入t行。

输出

 输出每个二叉树的先序遍历、中序遍历和后序遍历结果。

样例输入

2 AB#C##D## AB##C## 

样例输出

ABCD BCAD CBDA ABC BAC BCA 

解决方案

#include <iostream>
class BiTree {
public:
    BiTree() : root(nullptr) {}
    void assign(std::string &string) {
        int index = 0;
        assign(string, index, root);
    }
    void print() {
        preOrderTraversal(root);
        std::cout << std::endl;
        inOrderTraversal(root);
        std::cout << std::endl;
        postOrderTraversal(root);
        std::cout << std::endl;
    }
private:
    struct Node {
        char data;
        Node *left;
        Node *right;
        Node() : data(0), left(nullptr), right(nullptr) {}
        explicit Node(char data) : data(data), left(nullptr), right(nullptr) {}
        Node(char data, Node &left, Node &right) : data(data), left(&left), right(&right) {}
    };
    Node *root;
    static void assign(const std::string &string,int &index, Node *&pNode) {
        char data = string[index++];
        if (data != '#') {
            pNode = new Node(data);
            assign(string, index, pNode->left);
            assign(string, index, pNode->right);
        } else {
            pNode = nullptr;
        }
    }
    static void preOrderTraversal(Node *node) {
        if (node) {
            std::cout << node->data;
            preOrderTraversal(node->left);
            preOrderTraversal(node->right);
        }
    };
    static void inOrderTraversal(Node *node) {
        if (node) {
            inOrderTraversal(node->left);
            std::cout << node->data;
            inOrderTraversal(node->right);
        }
    }
    static void postOrderTraversal(Node *node) {
        if (node) {
            postOrderTraversal(node->left);
            postOrderTraversal(node->right);
            std::cout << node->data;
        }
    }
};
int main() {
    size_t t;
    std::cin >> t;
    while (t--) {
        std::string string;
        std::cin >> string;
        BiTree biTree;
        biTree.assign(string);
        biTree.print();
    }
}

Huffman编码与解码

时间限制: 1 Sec  内存限制: 128 MB

题目描述

1、问题描述

给定n个字符及其对应的权值，构造Huffman树，并进行huffman编码和译（解）码。

构造Huffman树时，要求左子树根的权值小于、等于右子树根的权值。

进行Huffman编码时，假定Huffman树的左分支上编码为‘0’，右分支上编码为‘1’。

2、算法

构造Huffman树算法：

⑴ 根据给定的n个权值(w1, w2, …, wn)构成n棵二叉树的集合F={T1, T2, …, Tn}，其中每棵二叉树Ti中只有一个权值为wi的根结点。

⑵ 在F中选取两棵根结点的权值最小的树，作为左、右子树构造一棵新的二叉树，且置其根结点的权值为其左、右子树权值之和。

⑶ 在F中删除这两棵树，同时将新得到的二叉树加入F中。

(4) 重复⑵, ⑶，直到F只含一棵树为止。

3、Huffman编码算法：

⑴ 从Huffman树的每一个叶子结点开始。

⑵ 依次沿结点到根的路径，判断该结点是父亲结点的左孩子还是右孩子，如果是左孩子则得到编码‘0’，否则得到编码‘1’，先得到的编码放在后面。

⑶ 直到到达根结点，编码序列即为该叶子结点对应的Huffman编码。

4、Huffman译（解）码算法：

⑴ 指针指向Huffman树的根结点，取第一个Huffman码。

⑵ 如果Huffman码为‘0’，将指针指向当前结点的左子树的根结点；如果Huffman码为‘1’，将指针指向当前结点的右子树的根结点。

⑶ 如果指针指向的当前结点为叶子结点，则输出叶子结点对应的字符；否则，取下一个Huffman码，并返回⑵。

⑷ 如果Huffman码序列未结束，则返回⑴继续译码。

输入

第一行测试次数

第2行：第一组测试数据的字符个数n，后跟n个字符

第3行：第一组测试数据的字符权重

待编码的字符串s1

编码串s2

其它组测试数据类推

输出

第一行~第n行,第一组测试数据各字符编码值

第n+1行，串s1的编码值

第n+2行，串s2的解码值，若解码不成功，输出error!

其它组测试数据类推

样例输入

2 5 A B C D E 15 4 4 3 2 ABDEC 00000101100 4 A B C D 7 5 2 4 ABAD 1110110 

样例输出

A :1 B :010 C :011 D :001 E :000 1010001000011 error! A :0 B :10 C :110 D :111 0100111 DAC 

解决方案

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <arpa/nameser.h>
class Huffman {
private:
    struct Node {
        int weight;
        char data;
        Node *left, *right;
        Node *parent;
        std::vector<int> code;
        Node(char data, int weight) : data(data), weight(weight), left(nullptr), right(nullptr), parent(nullptr) {};
        Node(Node *left, Node *right) : left(left), right(right) {
            weight = left->weight + right->weight;
            data = '\0';
            left->parent = this;
            right->parent = this;
            parent = nullptr;
        }
    };
    Node *_root;
    std::vector<Node *> nodeVector;
    std::vector<Node *> elementList;
    static bool temp(const Node *a, const Node *b) {
        return a->weight > b->weight;
    }
    void generate(Node *element, std::vector<int> &HuffmanCode) {
        if (element == element->parent->left) {
            HuffmanCode.push_back(0);
        } else {
            HuffmanCode.push_back(1);
        }
        if (element->parent != _root) {
            generate(element->parent, HuffmanCode);
        }
    }
public:
    Huffman(std::vector<int> &weightVector, std::vector<char> &dataVector) {
        _root = nullptr;
        for (size_t i = 0; i < weightVector.size(); ++i) {
            Node *node = new Node(dataVector[i], weightVector[i]);
            nodeVector.push_back(node);
            elementList.push_back(node);
        }
    }
    void constructorHuffman() {
        while (nodeVector.size() != 1) {
            std::sort(nodeVector.begin(), nodeVector.end(), temp);
            if (nodeVector[nodeVector.size() - 1]->weight == nodeVector[nodeVector.size() - 2]->weight) {
                Node *root = new Node(nodeVector[nodeVector.size() - 2], nodeVector[nodeVector.size() - 1]);
                nodeVector.pop_back();
                nodeVector.pop_back();
                nodeVector.push_back(root);
            } else {
                Node *root = new Node(nodeVector[nodeVector.size() - 1], nodeVector[nodeVector.size() - 2]);
                nodeVector.pop_back();
                nodeVector.pop_back();
                nodeVector.push_back(root);
            }
        }
        _root = nodeVector[0];
        coding();
    }
    void coding() {
        for (auto & i : elementList) {
            std::vector<int> code;
            generate(i, code);
            i->code.assign(code.begin(), code.end());
        }
    }
    void print() {
        for (auto & i : elementList) {
            std::cout << i->data << " :";
            printCode(i);
            std::cout << std::endl;
        }
    }
    static void printCode(Node *node) {
        for (int i = (int) node->code.size() - 1; i >= 0; --i) {
            std::cout << node->code[i];
        }
    }
    void encode(const std::string &string) {
        std::string encode;
        for (char i1 : string) {
            for (auto & i2 : elementList) {
                if (i2->data == i1) {
                    printCode(i2);
                }
            }
        }
        std::cout << std::endl;
    }
    void decode(const std::string &string) {
        std::string decode;
        Node *ptr = _root;
        for (char i1 : string) {
            if (i1 == '0') {
                ptr = ptr->left;
            } else {
                ptr = ptr->right;
            }
            if (ptr == nullptr) {
                std::cout << "error!" << std::endl;
                return;
            } else if (ptr->data != 0) {
                decode.push_back(ptr->data);
                ptr = _root;
            }
        }
        if (ptr == _root) {
            std::cout << decode << std::endl;
        } else {
            std::cout << "error!" << std::endl;
        }
    }
};
int main() {
    size_t n;
    std::cin >> n;
    while (n--) {
        int size;
        std::cin >> size;
        std::vector<int> weightVector(size);
        std::vector<char> dataVector(size);
        for (int i = 0; i < size; ++i) {
            std::cin >> dataVector[i];
        }
        for (int j = 0; j < size; ++j) {
            std::cin >> weightVector[j];
        }
        Huffman huffman(weightVector, dataVector);
        huffman.constructorHuffman();
        huffman.print();
        std::string string;
        std::cin >> string;
        huffman.encode(string);
        std::cin >> string;
        huffman.decode(string);
    }
}

二叉树高度

时间限制: 1 Sec  内存限制: 128 MB

题目描述

给出一棵二叉树，求它的高度。二叉树的创建采用前面实验的方法。

注意，二叉树的层数是从1开始

输入

第一行输入一个整数t，表示有t个二叉树

第二行起输入每个二叉树的先序遍历结果，空树用字符‘0’表示，连续输入t行

输出

每行输出一个二叉树的高度

样例输入

1 AB0C00D00 

样例输出

3

解决方案

#include <iostream>
class BiTree {
public:
    BiTree() : root(nullptr) {}
    void assign(std::string &string) {
        int index = 0;
        assign(string, index, root);
    }
    void printHeight() {
        search(root, 0);
        std::cout << treeHeight << std::endl;
    }
private:
    struct Node {
        char data;
        Node *left;
        Node *right;
        int height = 0;
        Node() : data(0), left(nullptr), right(nullptr) {}
        explicit Node(char data) : data(data), left(nullptr), right(nullptr) {}
        Node(char data, Node &left, Node &right) : data(data), left(&left), right(&right) {}
    };
    Node *root;
    int treeHeight = 0;
    static void assign(const std::string &string,int &index, Node *&pNode) {
        char data = string[index++];
        if (data != '0') {
            pNode = new Node(data);
            assign(string, index, pNode->left);
            assign(string, index, pNode->right);
        } else {
            pNode = nullptr;
        }
    }
    void search(Node* node, int height) {
        if (node != nullptr) {
            node->height = height + 1;
            if (node->height > treeHeight) {
                treeHeight = node->height;
            }
            search(node->left, node->height);
            search(node->right, node->height);
        }
    }
};
int main() {
    size_t t;
    std::cin >> t;
    while (t--) {
        std::string string;
        std::cin >> string;
        BiTree biTree;
        biTree.assign(string);
        biTree.printHeight();
    }
}

折半查找

时间限制: 1 Sec  内存限制: 128 MB

题目描述

给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始

要求使用折半查找算法

输入

第一行输入n，表示队列有n个数据
第二行输入n个数据，都是正整数，用空格隔开
第三行输入t，表示有t个要查找的数值
第四行起，输入t个数值，输入t行

输出

每行输出一个要查找的数值在队列的位置，如果查找不成功，输出字符串error

样例输入

8
11 22 33 44 55 66 77 88
3
22
88
99

样例输出

2
8
error

解决方案

#include <iostream>
#include <algorithm>
int halfSearch(const int a[], int key, int low, int high) {
    if (low > high) {
        return 0;
    }
    int mid = (low + high) / 2;
    if (a[mid] == key) {
        return mid;
    } else if (a[mid] > key) {
        halfSearch(a, key, low, mid - 1);
    } else {
        halfSearch(a, key, mid + 1, high);
    }
}
int main() {
    size_t size;
    std::cin >> size;
    int *p = new int[size + 1];
    for (size_t i = 1; i <= size; ++i) {
        std::cin >> p[i];
    }
    std::sort(p + 1, p + size);
    size_t T;
    std::cin >> T;
    while (T--) {
        int key;
        std::cin >> key;
        int flag = halfSearch(p, key, 1, size);
        if (flag) {
            std::cout << flag << std::endl;
        } else {
            std::cout << "error" << std::endl;
        }
    }
}

顺序索引查找

时间限制: 1 Sec  内存限制: 128 MB

题目描述

给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始

要求使用顺序索引查找算法，其中索引表查找和块内查找都采用不带哨兵、从头开始的顺序查找方法。

输入

第一行输入n，表示主表有n个数据
第二行输入n个数据，都是正整数，用空格隔开
第三行输入k，表示主表划分为k个块，k也是索引表的长度
第四行输入k个数据，表示索引表中每个块的最大值
第五行输入t，表示有t个要查找的数值
第六行起，输入t个数值，输入t行

输出

每行输出一个要查找的数值在队列的位置和查找次数，数据之间用短划线隔开，如果查找不成功，输出字符串error

样例输入

18
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53
3
22 48 86
6
13
5
48
40
53
90

样例输出

3-4
error
12-8
error
18-9
error

解决方案

#include <iostream>
#include <algorithm>
void find(int *maximum, int *point, int *p, int size) {
    for (int i = *point; i <= size; ++i) {
        if (maximum[0] < p[i]) {
            maximum[1] = --i;
            *point = i;
            return;
        }
    }
    maximum[1] = size;
}
int half_search(const int a[], int key, int low, int high) {
    if (low > high) {
        return 0;
    }
    int mid = (low + high) / 2;
    if (a[mid] == key) {
        return mid;
    } else if (a[mid] > key) {
        half_search(a, key, low, mid - 1);
    } else {
        half_search(a, key, mid + 1, high);
    }
    return 0;
}
int find_block(int **maximum, int max_size, int flag, int *find) {
    for (int i = 0; i < max_size; ++i) {
        (*find)++;
        if (flag <= maximum[i][0]) {
            return i;
        }
    }
    return max_size - 1;
}
int find_flag(int block, int **maximum, int max_size, int flag, int *find, const int *p) {
    int low, high;
    if (block == 0) {
        low = 1;
        high = maximum[block][1];
    } else {
        low = maximum[block - 1][1] + 1;
        high = maximum[block][1];
    }
    for (int i = low; i <= high; ++i) {
        (*find)++;
        if (flag == p[i]) {
            return i;
        }
    }
    return 0;
}
int main() {
    size_t size;
    std::cin >> size;
    //input array
    int *p = new int[size + 1];
    for (size_t i = 1; i <= size; ++i) {
        std::cin >> p[i];
    }
    //input maximum
    int max_size, point = 1, index;
    std::cin >> max_size;
    int **maximum = new int *[max_size];
    for (int k = 0; k < max_size; ++k) {
        maximum[k] = new int[2];
    }
    for (int j = 0; j < 3; ++j) {
        std::cin >> index;
        maximum[j][0] = index;
        find(maximum[j], &point, p, size);
    }
    //input index
    int index_size;
    std::cin >> index_size;
    for (int l = 0; l < index_size; ++l) {
        int find = 0, flag = 0;
        std::cin >> flag;
        int value;
        value = find_flag(find_block(maximum, max_size, flag, &find), maximum, max_size, flag, &find, p);
        if (value) {
            std::cout << value << "-" << find << std::endl;
        } else {
            std::cout << "error" << std::endl;
        }
    }
}

二叉排序树之创建和插入

时间限制: 1 Sec  内存限制: 128 MB

题目描述

给出一个数据序列，建立二叉排序树，并实现插入功能

对二叉排序树进行中序遍历，可以得到有序的数据序列

输入

第一行输入t，表示有t个数据序列

第二行输入n，表示首个序列包含n个数据

第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开

第四行输入m，表示要插入m个数据

从第五行起，输入m行，每行一个要插入的数据，都是自然数且和前面的数据不等

以此类推输入下一个示例

输出

第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到

从第二行起，输出插入第m个数据后的有序序列，输出m行

以此类推输出下一个示例的结果

样例输入

1
6
22 33 55 66 11 44
3
77
50
10

样例输出

11 22 33 44 55 66
11 22 33 44 55 66 77
11 22 33 44 50 55 66 77
10 11 22 33 44 50 55 66 77

解决方案

#include <iostream>
class Tree {
private:
    struct Node {
        int data;
        Node *leftChild, *rightChild;
        Node() = default;
        explicit Node(int data) : data(data), leftChild(nullptr), rightChild(nullptr) {}
    };
    Node *_root{};
    static void addRoot(int data, Node* parent) {
        if (data > parent->data) {
            if (parent->rightChild == nullptr) {
                parent->rightChild = new Node(data);
            } else {
                addRoot(data, parent->rightChild);
            }
        } else {
            if (parent->leftChild == nullptr) {
                parent->leftChild = new Node(data);
            } else {
                addRoot(data, parent->leftChild);
            }
        }
    }
    void print(Node *node) {
        if (node->leftChild != nullptr) {
            print(node->leftChild);
        }
        std::cout << node->data << " ";
        if (node->rightChild != nullptr) {
            print(node->rightChild);
        }
    }
public:
    explicit Tree(int data) {
        _root = new Node(data);
    }
    void addRoot(int data) {
        addRoot(data, _root);
    }
    void print() {
        print(_root->leftChild);
        std::cout << _root->data << " ";
        print(_root->rightChild);
        std::cout << std::endl;
    }
};
int main() {
    size_t T;
    std::cin >> T;
    while (T--) {
        int size, data;
        std::cin >> size;
        std::cin >> data;
        Tree tree(data);
        for (int i = 1; i < size; ++i) {
            std::cin >> data;
            tree.addRoot(data);
        }
        tree.print();
        int size_index, index;
        std::cin >> size_index;
        for (int j = 0; j < size_index; ++j) {
            std::cin >> index;
            tree.addRoot(index);
            tree.print();
        }
    }
}

二叉排序树之查找

时间限制: 1 Sec  内存限制: 128 MB

题目描述

给出一个数据序列，建立二叉排序树，并实现查找功能

对二叉排序树进行中序遍历，可以得到有序的数据序列

输入

第一行输入t，表示有t个数据序列

第二行输入n，表示首个序列包含n个数据

第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开

第四行输入m，表示要查找m个数据

从第五行起，输入m行，每行一个要查找的数据，都是自然数

输出

以此类推输入下一个示例

第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到

从第二行起，输出查找结果，如果查找成功输出查找次数，如果查找失败输出-1

以此类推输出下一个示例的结果

样例输入

1
6
22 33 55 66 11 44
7
11
22
33
44
55
66
77

样例输出

11 22 33 44 55 66
2
1
2
4
3
4
-1

解决方案

#include <iostream>
class Tree {
private:
    struct Node {
        int data;
        Node *leftChild, *rightChild;
        Node() = default;
        explicit Node(int data) : data(data), leftChild(nullptr), rightChild(nullptr) {}
    };
    Node *_root{};
    static void addRoot(int data, Node* parent) {
        if (data > parent->data) {
            if (parent->rightChild == nullptr) {
                parent->rightChild = new Node(data);
            } else {
                addRoot(data, parent->rightChild);
            }
        } else {
            if (parent->leftChild == nullptr) {
                parent->leftChild = new Node(data);
            } else {
                addRoot(data, parent->leftChild);
            }
        }
    }
    static int find(Node *root, int index, int *times) {
        (*times)++;
        if (root->data == index) {
            return *times;
        } else if (root->data < index) {
            if (root->rightChild == nullptr) {
                return -1;
            } else {
                return find(root->rightChild, index, times);
            }
        } else {
            if (root->leftChild == nullptr) {
                return -1;
            } else {
                return find(root->leftChild, index, times);
            }
        }
    }
    void print(Node *node) {
        if (node->leftChild != nullptr) {
            print(node->leftChild);
        }
        std::cout << node->data << " ";
        if (node->rightChild != nullptr) {
            print(node->rightChild);
        }
    }
public:
    explicit Tree(int data) {
        _root = new Node(data);
    }
    void addRoot(int data) {
        addRoot(data, _root);
    }
    void print() {
        print(_root->leftChild);
        std::cout << _root->data << " ";
        print(_root->rightChild);
        std::cout << std::endl;
    }
    int find(int index) {
        int times = 0;
        return find(_root, index, &times);
    }
};
int main() {
    size_t T;
    std::cin >> T;
    while (T--) {
        int size, data;
        std::cin >> size;
        std::cin >> data;
        Tree tree(data);
        for (int i = 1; i < size; ++i) {
            std::cin >> data;
            tree.addRoot(data);
        }
        tree.print();
        int count;
        std::cin >> count;
        while (count--) {
            int index;
            std::cin >> index;
            std::cout << tree.find(index) << std::endl;
        }
    }
}