题解 | #二叉排序树#

如果要做出这个题目，我们首先需要知道如何实现一个二叉排序树。

主要核心部分就是insert函数

struct TreeNode{
    int val;
    struct TreeNode *left, *right;
    TreeNode(int val): val(val), left(NULL), right(NULL) {}
};

TreeNode* insert(TreeNode* root, int x) {
    if (root == NULL) {
        root = new TreeNode(x);
    }
    else if (x < root->val) root->left = insert(root->left, x);
    else if (x > root->val) root->right = insert(root->right, x);
    return root;
}

完整代码如下：

#include <iostream>
using namespace std;

struct TreeNode{
    int val;
    struct TreeNode *left, *right;
    TreeNode(int val): val(val), left(NULL), right(NULL) {}
};

TreeNode* insert(TreeNode* root, int x) {
    if (root == NULL) {
        root = new TreeNode(x);
    }
    else if (x < root->val) root->left = insert(root->left, x);
    else if (x > root->val) root->right = insert(root->right, x);
    return root;
}

void dfs_pre(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";
    dfs_pre(root->left);
    dfs_pre(root->right);
}
void dfs_in(TreeNode* root) {
    if (!root) return;
    dfs_in(root->left);
    cout << root->val << " ";
    dfs_in(root->right);
}
void dfs_ba(TreeNode* root) {
    if (!root) return;
    dfs_ba(root->left);
    dfs_ba(root->right);
    cout << root->val << " ";
}

int main() {
    int n;
    while (cin >> n) { 
        TreeNode *root = NULL;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            root = insert(root, x);
        }    
        dfs_pre(root);
        cout << endl;
        dfs_in(root);
        cout << endl;
        dfs_ba(root);
        cout << endl;

    }
}