利用C++二叉排序树完成动态查找表的建立

C语言中可以利用二叉排序树来完成动态查找表的建立。二叉排序树是指一种特殊的二叉树，其每个节点的值都大于左子树上的值，而小于右子树上的值，通过这种方式可以构建出一个有序的树结构，从而实现动态查找表的建立。

相关问题

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

以下是使用 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;
}

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

C++根据二叉排序树的抽象数类型确定义，使用链表示实现一个二叉排序树并编写测试main()函数测试算法的正二叉排序树的基础功能： 1、建立并打印此时二叉排序树2、查找3、插入并打印此时二叉排序树4、删除并打印此时二叉排序树5、销毁二叉排序树。

好的，我可以帮你回答这个问题。

首先，我们需要定义一个二叉排序树的结构体。它应该包含一个值，以及指向左子树和右子树的指针。

struct BSTNode {
    int value;
    BSTNode* left;
    BSTNode* right;
};

接下来，我们可以实现一个函数来创建一个新的节点。

BSTNode* createNode(int value) {
    BSTNode* node = new BSTNode;
    node->value = value;
    node->left = nullptr;
    node->right = nullptr;
    return node;
}

然后，我们可以实现一个函数来插入一个值到树中。如果树为空，我们可以创建一个新节点并将其设置为根节点。否则，我们可以按照二叉排序树的规则将值插入到正确的位置。

void insert(BSTNode*& root, int value) {
    if (root == nullptr) {
        root = createNode(value);
    } else if (value < root->value) {
        insert(root->left, value);
    } else {
        insert(root->right, value);
    }
}

接下来，我们可以实现一个函数来查找一个值是否在树中。如果找到了，我们返回节点指针。否则，我们返回nullptr。

BSTNode* find(BSTNode* root, int value) {
    if (root == nullptr || root->value == value) {
        return root;
    } else if (value < root->value) {
        return find(root->left, value);
    } else {
        return find(root->right, value);
    }
}

接下来，我们可以实现一个函数来删除一个节点。如果节点没有子节点，我们可以直接删除它。如果节点有一个子节点，我们可以将其子节点替换为该节点。如果节点有两个子节点，我们可以将其替换为其右子树中最小的节点，并将其右子树中的该节点删除。

void remove(BSTNode*& root, int value) {
    if (root == nullptr) {
        return;
    } else if (value < root->value) {
        remove(root->left, value);
    } else if (value > root->value) {
        remove(root->right, value);
    } else {
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            root = nullptr;
        } else if (root->left == nullptr) {
            BSTNode* temp = root;
            root = root->right;
            delete temp;
        } else if (root->right == nullptr) {
            BSTNode* temp = root;
            root = root->left;
            delete temp;
        } else {
            BSTNode* temp = root->right;
            while (temp->left != nullptr) {
                temp = temp->left;
            }
            root->value = temp->value;
            remove(root->right, temp->value);
        }
    }
}

最后，我们可以实现一个函数来销毁整个树。我们可以使用递归来删除每个节点。

void destroy(BSTNode*& root) {
    if (root == nullptr) {
        return;
    }
    destroy(root->left);
    destroy(root->right);
    delete root;
    root = nullptr;
}

现在我们已经实现了二叉排序树的基本功能，我们可以编写一个测试main()函数来测试它们的正确性。

#include <iostream>
using namespace std;

void inorder(BSTNode* root) {
    if (root == nullptr) {
        return;
    }
    inorder(root->left);
    cout << root->value << " ";
    inorder(root->right);
}

int main() {
    BSTNode* root = nullptr;

    insert(root, 5);
    insert(root, 3);
    insert(root, 7);
    insert(root, 1);
    insert(root, 9);

    cout << "Inorder traversal of the BST: ";
    inorder(root);
    cout << endl;

    BSTNode* node = find(root, 7);
    if (node != nullptr) {
        cout << "Found " << node->value << endl;
    } else {
        cout << "7 not found" << endl;
    }

    insert(root, 2);
    cout << "Inorder traversal of the BST after inserting 2: ";
    inorder(root);
    cout << endl;

    remove(root, 3);
    cout << "Inorder traversal of the BST after removing 3: ";
    inorder(root);
    cout << endl;

    destroy(root);

    return 0;
}

输出应该为：

Inorder traversal of the BST: 1 3 5 7 9 
Found 7
Inorder traversal of the BST after inserting 2: 1 2 3 5 7 9 
Inorder traversal of the BST after removing 3: 1 2 5 7 9