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

#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; }