对{4,5,19,23,2,8}}C++实现二叉搜索树

实现二叉搜索树的基本思路如下：

1. 定义叉搜索树的节点结构体，包含值、左子树指针和右子树指针。
2. 定义二叉搜索树类，包含根节点指针和插入、查找、删除等操作函数。
3. 插入操作：从根节点开始比较，如果要插入的值比当前节点值小，则向左子树递归；如果要插入的值比当前节点值大，则向右子树递归；如果当前节点为空，则在该节点处新建一个节点。
4. 查找操作：从根节点开始比较，如果要查找的值比当前节点值小，则向左子树递归查找；如果要查找的值比当前节点值大，则向右子树递归查找；如果当前节点值等于要查找的值，则返回该节点。
5. 删除操作：先查找要删除的节点，如果该节点是叶子节点，则直接删除；如果该节点只有一个子节点，则将子节点替换该节点；如果该节点有两个子节点，则找到该节点右子树中的最小值节点替换该节点，并删除最小值节点。

下面是一个用 C++ 实现的二叉搜索树示例代码，可以插入一个整数序列并进行查找、删除等操作：

#include <iostream>
using namespace std;

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

class BST {
private:
    TreeNode* root;

public:
    BST() : root(NULL) {}

    void insert(int val) {
        if (!root) {
            root = new TreeNode(val);
            return;
        }
        TreeNode* cur = root;
        while (cur) {
            if (val < cur->val) {
                if (!cur->left) {
                    cur->left = new TreeNode(val);
                    return;
                }
                cur = cur->left;
            } else if (val > cur->val) {
                if (!cur->right) {
                    cur->right = new TreeNode(val);
                    return;
                }
                cur = cur->right;
            } else {
                return;  // 已存在该节点
            }
        }
    }

    TreeNode* search(int val) {
        TreeNode* cur = root;
        while (cur) {
            if (val < cur->val) {
                cur = cur->left;
            } else if (val > cur->val) {
                cur = cur->right;
            } else {
                return cur;
            }
        }
        return NULL;  // 未找到该节点
    }

    TreeNode* findMin(TreeNode* node) {
        while (node->left) {
            node = node->left;
        }
        return node;
    }

    void remove(int val) {
        if (!root) {
            return;
        }
        TreeNode* cur = root;
        TreeNode* parent = NULL;
        while (cur) {
            if (val < cur->val) {
                parent = cur;
                cur = cur->left;
            } else if (val > cur->val) {
                parent = cur;
                cur = cur->right;
            } else {
                if (!cur->left && !cur->right) {  // 叶子节点
                    if (!parent) {  // 根节点
                        root = NULL;
                    } else if (cur == parent->left) {
                        parent->left = NULL;
                    } else {
                        parent->right = NULL;
                    }
                    delete cur;
                } else if (cur->left && !cur->right) {  // 只有左子节点
                    if (!parent) {  // 根节点
                        root = cur->left;
                    } else if (cur == parent->left) {
                        parent->left = cur->left;
                    } else {
                        parent->right = cur->left;
                    }
                    delete cur;
                } else if (!cur->left && cur->right) {  // 只有右子节点
                    if (!parent) {  // 根节点
                        root = cur->right;
                    } else if (cur == parent->left) {
                        parent->left = cur->right;
                    } else {
                        parent->right = cur->right;
                    }
                    delete cur;
                } else {  // 有两个子节点
                    TreeNode* minNode = findMin(cur->right);
                    cur->val = minNode->val;
                    remove(minNode->val);
                }
                return;
            }
        }
    }
};

int main() {
    int arr[] = {4, 5, 19, 23, 2, 8};
    int n = sizeof(arr) / sizeof(int);

    BST tree;
    for (int i = 0; i < n; i++) {
        tree.insert(arr[i]);
    }

    TreeNode* node = tree.search(19);
    if (node) {
        cout << "找到节点：" << node->val << endl;
    } else {
        cout << "未找到节点" << endl;
    }

    tree.remove(19);
    node = tree.search(19);
    if (node) {
        cout << "找到节点：" << node->val << endl;
    } else {
        cout << "未找到节点" << endl;
    }

    return 0;
}