#include #include #include using namespace std;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(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; }int main() { srand(time(NULL)); BST bst = BST (); int n = 10000; for( int i = 0 ; i < n ; i ++ ){ int key = rand()%n; // 为了后续测试方便,这里value值取和key值一样 int value = key; //cout< <<" "; bst.insert(key,value); } // test remove // remove elements in random order int order[n]; for( int i = 0 ; i < n ; i ++ ) order[i] = i; shuffle( order , n ); for( int i = 0 ; i < n ; i ++ ) if( bst.contain( order[i] )){ bst.remove( order[i] ); cout<<"After remove "< <<" size = "< <
1. 插入insert
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 ){ // 如果节点为空,就在此节点处加入x信息 count ++; return new Node(key, value); } if( key == node->key ) node->value = value; //如果相等,就把频率加1 else if( key < node->key ) node->left = insert( node->left , key, value); // 如果x小于节点的值,就继续在节点的左子树中插入x else // key > node->key node->right = insert( node->right, key, value); // 如果x大于节点的值,就继续在节点的右子树中插入x return node;}复制代码
2. 包含contain
bool contain(Key key){ return contain(root, key);}// 查看以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 );}复制代码
3. 搜索search
Value* search(Key key){ return search( root , key );}// 在以node为根的二叉搜索树中查找key所对应的valueValue* 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 );}复制代码
4. 遍历
void preOrder(){ preOrder(root);}// 对以node为根的二叉搜索树进行前序遍历void preOrder(Node* node){ if( node != NULL ){ cout< key< left); preOrder(node->right); }}复制代码
void inOrder(){ inOrder(root);}// 对以node为根的二叉搜索树进行中序遍历void inOrder(Node* node){ if( node != NULL ){ inOrder(node->left); cout< key< right); }}复制代码
void postOrder(){ postOrder(root);}// 对以node为根的二叉搜索树进行后序遍历void postOrder(Node* node){ if( node != NULL ){ postOrder(node->left); postOrder(node->right); cout< key<
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 ); }}复制代码
5. 寻找最小/大键值
Key minimum(){ assert( count != 0 ); Node* minNode = minimum( root ); return minNode->key;}// 在以node为根的二叉搜索树中,返回最小键值的节点Node* minimum(Node* node){ if( node->left == NULL ) return node; return minimum(node->left);}复制代码
Key maximum(){ assert( count != 0 ); Node* maxNode = maximum(root); return maxNode->key;}// 在以node为根的二叉搜索树中,返回最大键值的节点Node* maximum(Node* node){ if( node->right == NULL ) return node; return maximum(node->right);}复制代码
6. 从二叉树中删除最小/大值所在节点
void removeMin(){ if( root ) root = removeMin( root );}// 删除掉以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;}复制代码
void removeMax(){ if( root ) root = removeMax( root );}// 删除掉以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;}复制代码
7. 删除remove
void remove(Key key){ root = remove(root, key);}// 删除掉以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; }}复制代码