BST

推荐慕课网，刘宇波老师《算法与数据结构》 链接：http://coding.imooc.com/class/71.html BST_常用操作 课堂笔记 #include <iostream> 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 *root; int count; public: BST(){ root = NULL; count = 0; } ~BST(){ destroy(); } 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); } Value* serach(Key key){ return serach(root,key); } void preOrder(){ preOrder(root); } void inOrder(){ inOrder(root); } void postOrder(){ postOrder(root); } 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 node; } bool contain(Node* node,Key key){ if(node == NULL) return false; if(key == node->key) return true; else if(key < node->key) return contian(node->left,key); else return contian(node->right,key); } Value* serach(Node* node,Key key){ if(node == NULL) return NULL; if(key == node->key) return &(node->value); else if(key < node->value) return serach(node->left,key); else return serach(node->right,key); } void preOrder(Node* node){ if(node != NULL){ cout<<node->key<<endl; preOrder(node->left); preOrder(node->right); } } void inOrder(Node* node){ if(node != NULL){ inOrder(node->left); cout<<node->key<<endl; inOrder(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 -- ; } } }; int main() { return 0; }