Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· openaiHugging Face Suzhen/CodeChat

c++二叉搜索树怎么用

  1. User

    c++二叉搜索树怎么用

  2. Assistant

    在C++中实现二叉搜索树可以通过定义一个节点类来保存节点的数据和指向左右子节点的指针。下面是一个简单的二叉搜索树的实现示例:

    #include <iostream>
    
    using namespace std;
    
    class TreeNode {
    public:
        int val;
        TreeNode* left;
        TreeNode* right;
        
        TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
    };
    
    class BST {
    public:
        TreeNode* root;
        
        BST() : root(nullptr) {}
        
        void insert(int value) {
            root = insertNode(root, value);
        }
        
        TreeNode* insertNode(TreeNode* node, int value) {
            if (node == nullptr) {
                return new TreeNode(value);
            }
            
            if (value < node->val) {
                node->left = insertNode(node->left, value);
            } else {
                node->right = insertNode(node->right, value);
            }
            
            return node;
        }
        
        bool search(int value) {
            return searchNode(root, value);
        }
        
        bool searchNode(TreeNode* node, int value) {
            if (node == nullptr) {
                return false;
            }
            
            if (value == node->val) {
                return true;
            } else if (value < node->val) {
                return searchNode(node->left, value);
            } else {
                return searchNode(node->right, value);
            }
        }
        
        void remove(int value) {
            root = removeNode(root, value);
        }
        
        TreeNode* removeNode(TreeNode* node, int value) {
            if (node == nullptr) {
                return nullptr;
            }
            
            if (value < node->val) {
                node->left = removeNode(node->left, value);
            } else if (value > node->val) {
                node->right = removeNode(node->right, value);
            } else {
                if (node->left == nullptr && node->right == nullptr) {
                    delete node;
                    return nullptr;
                } else if (node->left == nullptr) {
                    TreeNode* temp = node->right;
                    delete node;
                    return temp;
                } else if (node->right == nullptr) {
                    TreeNode* temp = node->left;
                    delete node;
                    return temp;
                } else {
                    TreeNode* minNode = findMin(node->right);
                    node->val = minNode->val;
                    node->right = removeNode(node->right, minNode->val);
                }
            }
            
            return node;
        }
        
        TreeNode* findMin(TreeNode* node) {
            if (node->left != nullptr) {
                return findMin(node->left);
            } else {
                return node;
            }
        }
        
        void inorderTraversal() {
            inorder(root);
        }
        
        void inorder(TreeNode* node) {
            if (node != nullptr) {
                inorder(node->left);
                cout << node->val << " ";
                inorder(node->right);
            }
        }
    };
    
    int main() {
        BST bst;
        
        bst.insert(5);
        bst.insert(3);
        bst.insert(8);
        bst.insert(2);
        bst.insert(4);
        bst.insert(7);
        bst.insert(9);
        
        cout << "Inorder traversal: ";
        bst.inorderTraversal();
        cout << endl;
        
        cout << "Search 5: " << (bst.search(5) ? "found" : "not found") << endl;
        cout << "Search 10: " << (bst.search(10) ? "found" : "not found") << endl;
        
        bst.remove(3);
        
        cout << "Inorder traversal after removing 3: ";
        bst.inorderTraversal();
        cout << endl;
        
        return 0;
    }
    

    以上示例实现了一个二叉搜索树的基本功能,包括插入节点、搜索节点、删除节点和中序遍历等操作。运行该程序会输出以下结果:

    Inorder traversal: 2 3 4 5 7 8 9
    Search 5: found
    Search 10: not found
    Inorder traversal after removing 3: 2 4 5 7 8 9
    

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.