二叉查找树代码

以下是 C++ 语言实现的二叉查找树代码：

#include <iostream>

using namespace std;

// 定义二叉查找树节点结构体
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 向二叉查找树中插入节点的函数
TreeNode* insert(TreeNode* root, int val) {
    if (root == NULL) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);
    } else if (val > root->val) {
        root->right = insert(root->right, val);
    }
    return root;
}

// 在二叉查找树中查找节点的函数
bool search(TreeNode* root, int val) {
    if (root == NULL) {
        return false;
    }
    if (root->val == val) {
        return true;
    } else if (val < root->val) {
        return search(root->left, val);
    } else {
        return search(root->right, val);
    }
}

// 中序遍历二叉查找树
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

int main() {
    TreeNode* root = NULL;

    root = insert(root, 5);
    root = insert(root, 2);
    root = insert(root, 7);
    root = insert(root, 1);
    root = insert(root, 3);
    root = insert(root, 6);
    root = insert(root, 8);

    cout << "Inorder traversal: ";
    inorderTraversal(root);
    cout << endl;

    int val = 3;
    cout << "Search " << val << ": " << (search(root, val) ? "Found" : "Not found") << endl;

    val = 4;
    cout << "Search " << val << ": " << (search(root, val) ? "Found" : "Not found") << endl;

    return 0;
}

这段代码中，我们首先定义了二叉查找树节点的结构体 `TreeNode`，包含一个 `val` 表示节点值，以及两个指针 `left` 和 `right` 分别表示左右子节点。

接着，我们实现了两个函数：`insert` 和 `search`。`insert` 函数用于向二叉查找树中插入节点，如果当前节点为空，则新建一个节点，并返回该节点作为新的子节点；如果待插入节点值小于当前节点，则继续在当前节点的左子树中插入；否则，在当前节点的右子树中插入。

`search` 函数用于在二叉查找树中查找节点，如果当前节点为空，则直接返回 false；如果当前节点的值等于待查找值，则返回 true；否则，如果待查找值小于当前节点，则在左子树中继续查找；否则，在右子树中继续查找。

最后，我们实现了中序遍历二叉查找树的函数 `inorderTraversal`，以及一个简单的 `main` 函数，用于测试插入和查找节点的功能。