c++构建二叉查找树

在 C++ 中，构建二叉查找树（Binary Search Tree, BST）通常涉及创建一个节点结构体，该结构体包含数据元素和两个指针，分别指向左子树和右子树。以下是一个简单的步骤描述：

1. 首先，定义一个 Node 类，它有一个整型的数据域 `val` 和两个指向 Node 的引用 `left` 和 `right`。

struct Node {
    int val;
    Node* left;
    Node* right;
};

2. 然后创建一个函数，比如 `insert` 或 `buildBST`，用于插入新节点并保持BST特性（左子树小于根，右子树大于根）。这个过程通常采用递归的方式：

Node* insert(Node* root, int val) {
    if (root == nullptr) {
        return new Node{val, nullptr, nullptr}; // 如果树为空，新建节点
    }
    if (val < root->val) {
        root->left = insert(root->left, val); // 如果值小，递归左子树
    } else {
        root->right = insert(root->right, val); // 如果值大，递归右子树
    }
    return root;
}

3. 可以从一个空的根节点开始插入值，得到完整的BST：

Node* buildBST(vector<int>& nums) {
    if (nums.empty()) {
        return nullptr;
    }
    return insert(new Node{nums}, nums), nums.erase(nums.begin());
}

4. 要遍历BST，你可以选择前序、中序或后序遍历。例如，前序遍历可以这样实现：

void preOrder(Node* node) {
    if (node != nullptr) {
        cout << node->val << " ";
        preOrder(node->left);
        preOrder(node->right);
    }
}