编写代码选题十二：动态查找表 【问题描述】 利用二叉排序树完成动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点。 【任务要求】 算法输入：指定一组数据。 算法输出：显示二叉排序树的中序遍历结果、查找成功与否的信息、插入和删除后的中序遍历结果(排序结果)。 算法要点：二叉排序树建立方法、动态查找方法,对树进行中序遍历。 【测试数据】 自行设定，注意边界等特殊情况。

以下是使用 C++ 编写的二叉排序树代码，可以实现动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点：

#include <iostream>
using namespace std;

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

class BinarySearchTree {
public:
    BinarySearchTree() : 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; // already exists
            }
        }
    }

    void remove(int val) {
        root = removeHelper(root, val);
    }

    bool 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 true;
            }
        }
        return false;
    }

    void inorderTraversal() {
        inorderHelper(root);
        cout << endl;
    }

private:
    TreeNode* root;

    TreeNode* removeHelper(TreeNode* root, int val) {
        if (!root) {
            return NULL;
        }
        if (val < root->val) {
            root->left = removeHelper(root->left, val);
        } else if (val > root->val) {
            root->right = removeHelper(root->right, val);
        } else {
            if (!root->left && !root->right) {
                delete root;
                return NULL;
            } else if (!root->left) {
                TreeNode* right = root->right;
                delete root;
                return right;
            } else if (!root->right) {
                TreeNode* left = root->left;
                delete root;
                return left;
            } else {
                TreeNode* successor = root->right;
                while (successor->left) {
                    successor = successor->left;
                }
                root->val = successor->val;
                root->right = removeHelper(root->right, successor->val);
            }
        }
        return root;
    }

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

int main() {
    BinarySearchTree bst;

    // insert nodes
    bst.insert(5);
    bst.insert(3);
    bst.insert(7);
    bst.insert(2);
    bst.insert(4);
    bst.insert(6);
    bst.insert(8);

    // inorder traversal
    cout << "Inorder Traversal: ";
    bst.inorderTraversal();

    // search nodes
    cout << "Search 6: " << (bst.search(6) ? "Found" : "Not Found") << endl;
    cout << "Search 9: " << (bst.search(9) ? "Found" : "Not Found") << endl;

    // remove nodes
    bst.remove(3);
    bst.remove(5);

    // inorder traversal after removal
    cout << "Inorder Traversal after Removal: ";
    bst.inorderTraversal();

    return 0;
}

使用上述代码可以完成动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点。