关于二叉树的一些基本操作，C++

骑猪看日落 2022-12-12 15:02 278阅读 0赞

#include <iostream>
    #include <cassert>
    #include <queue>
    
    using namespace std;
    
    template<typename Key, typename Value>
    
    class BST{ 
    private:
        struct Node{ 
            Key key;
            Value value;
            Node *left;
            Node *right;
    
            Node(Key key, Value value){ 
                this->key = key;
                this->value = value;
                this->left = this->right = NULL;
            }
    
            Node(Node *node){ 
                this->key = node->key;
                this->value = node->value;
                this->left = node->left;
                this->right = node->right;
            }
        };
    
        Node *root;
        int count;
    
    public:
        BST(){ 
            root = NULL;
            count = 0;
        }
    
        ~BST(){ 
            destroy(root);
        }
    
        int size(){ 
            return count;
        }
    
        bool isEmpty(){ 
            return count == 0;
        }
    
        void insert(Key key, Value value){ 
            root = insert(root, key, value);
        }
    
        bool contain(Key key){ 
            return contain(root, key);
        }
    
    // 因为c++返回值不能为空，所以这里返回一个指针，
    // 防止因为找不到元素导致报错
        Value* search(Key key){ 
            return search( root, key);
        }
    
        void preOder(){ 
            preOder(root);
        }
    
        void inOder(){ 
            inOder(root);
        }
    
        void postOrder(){ 
            postOrder(root);
        }
    
    // 层序遍历(广搜)
        void levelOrder(){ 
            queue<Node*> q;
            q.push(root);
            while ( !q.empty() ){ 
                Node *node = q.front();
                q.pop();
                cout << node->key << endl;
    
                if( node->left )
                    q.push( node-> left );
                if( node->right )
                    q.push( node->right );
            }
        }
    
    // 寻找最小的键值
        Key minimum(){ 
            assert( count != 0 );
            Node* minNode = minimum( root );
            return minNode->key;
        }
    
    // 寻找最大的键值
        Key maximum(){ 
            assert( count != 0 );
            Node* maxNode = maximum( root );
            return maxNode->key;
        }
    
    // 删除最小值所在节点
        void removeMin(){ 
            if( root )
                root = removeMin( root );
        }
    
    // 删除最大值所在节点
        void removeMax(){ 
            if( root )
                root = removeMax( root );
        }
    
    // 删除键值为key的节点
        void remove(Key key){ 
            root = remove(root, key);
        }
    
    private:
    //插入结点
        Node* insert(Node *node, Key key, Value value){ 
            if( node == NULL ){ 
                count ++;
                return new Node(key, value);
            }
            if( key == node->key)
                node->value = value;
            else if( key < node->key )
                node->left = insert(node->left , key, value);
            else
                node->right = insert(node->right, key, value);
            return root;
        }
    
    //查找是否有元素
        bool contain(Node* node, Key key, Value value){ 
            if( node == NULL )
                return false;
            if( key == node->key )
                return true;
            else if( key < node->key )
                return contain( node->left, key);
            else
                return contain( node->right, key);
        }
    
    // 查找key对应的value
        Value* search(Node* node, Key key){ 
    
            if( node == NULL )
                return NULL;
            if( key == node->key )
                return &(node->value);
            else if( key < node->key )
                return search( node->left , key);
            else
                return search( node->right , key);
        }
    
    
    //前序遍历
        void preOrder(Node* node){ 
            if( node != NULL ){ 
                cout << node->key << endl;
                preOder(node->left);
                preOder(node->right);
            }
        }
    
    //中序遍历
        void inOrder(Node* node){ 
            if( node != NULL){ 
                inOder(node->left);
                cout << node->key << endl;
                inOder(node->right);
            }
        }
    
    //后序遍历
        void postOrder(Node* node){ 
            if( node != NULL ){ 
                postOrder(node->left);
                postOrder(node->right);
                cout << node->key << endl;
            }
        }
    
        void destroy(Node* node){ 
            if( node != NULL ){ 
                destroy( node-> left );
                destroy( node-> right);
    
                delete node;
                count --;
            }
        }
    
        Node* minimum(Node* node){ 
            if(node->left == NULL)
                return node;
            return minimum(node->left);
        }
    
        Node* maximum(Node* node){ 
            if(node->right == NULL)
                return node;
            return maximum(node->right);
        }
    
        Node* removeMin(Node* node){ 
            if( node->left == NULL ){ 
                Node* rightNode = node->right;
                delete node;
                count--;
                return rightNode;
            }
            node->left = removeMin(node->left);
            return node;
        }
    
        Node* removeMax(Node* node){ 
            if( node->right == NULL ){ 
                Node* leftNode = node->left;
                delete node;
                count--;
                return leftNode;
            }
            node->right = removeMax(node->right);
            return node;
        }
    
        Node* remove(Node* node, Key key){ 
            if( node == NULL )
                return NULL;
            if( key < node->key ){ 
                node->left = remove( node->key, key);
                return node;
            }
            else if( key > node->key ){ 
                node->right = remove( node->right, key);
                return node;
            }
            else{ 
                if( node->left == NULL ){ 
                    Node *rightNode = node->right;
                    delete node;
                    count --;
                    return rightNode;
                }
                if( node->right == NULL ){ 
                    Node *leftNode = node->left;
                    delete node;
                    count --;
                    return leftNode;
                }
    
                Node *delNode = node;
                Node *successor = new Node(minimum(node->right));
                count++;
                successor->right = removeMin(node->right);
                successor->left = node->left;
    
                delete delNode;
                count--;
                return successor;
            }
        }
    };
    
    
    int main(){ 
        return 0;
    }