template 
     
      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 *root;    int count;public:    BST(){        root = NULL;        count = 0;    }    ~BST(){        // TODO: ~BST()    }    int size(){        return count;    }    bool isEmpty(){        return count == 0;    }};
     

 

插入新的节点：

public：    void insert(Key key, Value value){        root = insert(root, key, value);    }private:    // 向以node为根的二叉搜索树中,插入节点(key, value)    // 返回插入新节点后的二叉搜索树的根    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    // key > node->key            node->right = insert( node->right, key, value);        return node;    }};

 

是否包含有键值为key的节点：

public： bool contain(Key key){        return contain(root, key);    }private：// 查看以node为根的二叉搜索树中是否包含键值为key的节点    bool contain(Node* node, Key key){        if( node == NULL )            return false;        if( key == node->key )            return true;        else if( key < node->key )            return contain( node->left , key );        else // key > node->key            return contain( node->right , key );    }

 

查找：

public：    Value* search(Key key){        return search( root , key );    }private：     // 在以node为根的二叉搜索树中查找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 // key > node->key            return search( node->right, key );    }

 

前序遍历：

public：    // 前序遍历    void preOrder(){        preOrder(root);    }private：    // 对以node为根的二叉搜索树进行前序遍历    void preOrder(Node* node){        if( node != NULL ){            cout<
     
      key<
      
       left);            preOrder(node->right);        }    }
      
     

中序遍历：

public：    // 中序遍历    void inOrder(){        inOrder(root);    }private：    // 对以node为根的二叉搜索树进行中序遍历    void inOrder(Node* node){        if( node != NULL ){            inOrder(node->left);            cout<
     
      key<
      
       right);        }    }
      
     

后序遍历：

public：    // 后序遍历    void postOrder(){        postOrder(root);    }private：     // 对以node为根的二叉搜索树进行后序遍历    void postOrder(Node* node){        if( node != NULL ){            postOrder(node->left);            postOrder(node->right);            cout<
     
      key<
     

 

析构函数：

public：    ~BST(){        destroy( root );    }private：    void destroy(Node* node){        if( node != NULL ){            destroy( node->left );            destroy( node->right );            delete node;            count --;        }    }

层序遍历：

public：     // 层序遍历    void levelOrder(){        queue
     
       q;        q.push(root);        while( !q.empty() ){            Node *node = q.front();            q.pop();            cout<
      
       key<
       
        left )                q.push( node->left );            if( node->right )                q.push( node->right );        }    }
       
      
     

 

最小键值：

public：    // 寻找最小的键值    Key minimum(){        assert( count != 0 );        Node* minNode = minimum( root );        return minNode->key;    }private：    // 在以node为根的二叉搜索树中,返回最小键值的节点    Node* minimum(Node* node){        if( node->left == NULL )            return node;        return minimum(node->left);    }

最大键值：

public：     // 寻找最大的键值    Key maximum(){        assert( count != 0 );        Node* maxNode = maximum(root);        return maxNode->key;    }private：     // 在以node为根的二叉搜索树中,返回最大键值的节点    Node* maximum(Node* node){        if( node->right == NULL )            return node;        return maximum(node->right);    }

删除最小节点：

public：     // 从二叉树中删除最小值所在节点    void removeMin(){        if( root )            root = removeMin( root );    }private：    // 删除掉以node为根的二分搜索树中的最小节点    // 返回删除节点后新的二分搜索树的根    Node* removeMin(Node* node){        if( node->left == NULL ){            Node* rightNode = node->right;            delete node;            count --;            return rightNode;        }        node->left = removeMin(node->left);        return node;    }

删除最大节点：

public：     // 从二叉树中删除最大值所在节点    void removeMax(){        if( root )            root = removeMax( root );    }private：    // 删除掉以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;    }

删除任意节点：

public：    Node(Node *node){            this->key = node->key;            this->value = node->value;            this->left = node->left;            this->right = node->right;        }

 

public：    // 从二叉树中删除键值为key的节点    void remove(Key key){        root = remove(root, key);    }private：    // 删除掉以node为根的二分搜索树中键值为key的节点    // 返回删除节点后新的二分搜索树的根    Node* remove(Node* node, Key key){        if( node == NULL )            return NULL;        if( key < node->key ){            node->left = remove( node->left , key );            return node;        }        else if( key > node->key ){            node->right = remove( node->right, key );            return node;        }        else{   // key == node->key            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->left != NULL && node->right != NULL            Node *successor = new Node(minimum(node->right));            count ++;            successor->right = removeMin(node->right);            successor->left = node->left;            delete node;            count --;            return successor;        }    }