二叉搜索树是这样定义的： 左子树如果有，key值都比根节点的key值小， 右子树如果有，key值都比根节点的key值大， 左子树和右子树都是二叉搜索树； 模拟实现一个模板类BSTree.hpp实现搜索二叉树的一些基本功能
#pragma once #include<iostream> template<class K> struct BSTreeNode { BSTreeNode(const K& key) :_key(key), _left(NULL), _right(NULL){} K _key; BSTreeNode* _left; BSTreeNode* _right; }; template<class K> class BSTree { typedef BSTreeNode<K> Node; public: BSTree() :_root(NULL){} BSTree(const BSTree & t) { _copy(t._root); } void InOrder() { _InOrder(_root); std::cout << std::endl; } bool InsertR(const K& key)//递归 { return _InsertR(_root, key); } bool Insert(const K& key) { if (_root == NULL) { _root = new Node(key); } else { Node* parent = NULL; Node* root = _root; while (root) { parent = root; if (key > root->_key) root = root->_right; else if (key < root->_key) root = root->_left; else return false; } if (key < parent->_key) parent->_left = new Node(key); else parent->_right = new Node(key); } return true; } bool RemoveR(const K& key)//递归 { return _RemoveR(_root, key); } bool Remove(const K& key) { Node* parent = _root; Node* root = _root; while (root) { if (key > root->_key) { parent = root; root = root->_right; } else if (key < root->_key) { parent = root; root = root->_left; } else { break; } }//找到要删除的位置 Node* del = root; if (root == NULL) return false;//没找到位置 if (root->_left == NULL) { if (root == _root) _root = _root->_right; else { if (root == parent->_right) parent->_right = root->_right;//要删除的点左边没东西，让父节点指向它的右节点即可； else parent->_left = root->_left; } } else if (root->_right == NULL) { if (root == _root) _root = _root->_left; else { if (root == parent->_right) parent->_right = root->_right; else parent->_left = root->_left; } } else { Node* rootL = root->_left; parent = root; while (rootL->_right)//左右两边都有节点，找左边最大的节点 { parent = rootL; rootL = rootL->_right; } root->_key = rootL->_key; del = rootL; if (root == parent->_right) parent->_right = rootL->_left; else parent->_left = rootL->_left; } delete del; del = NULL; return true; } Node* FindR(const K& key) { return _FindR(_root, key); } Node* Find(const K& key) { Node* root = _root; while (root) { if (key > root->_key) root = root->_right; else if (key < root->_key) root = root->_left; else return root; } return root; } ~BSTree() { _delete(_root); } private: Node* _FindR(Node* root, const K& key) { if (root == NULL) return NULL; if (key > root->_key) return _FindR(root->_right, key); else if (key < root->_key) return _FindR(root->_left, key); else return root; } bool _RemoveR(Node* &root, const K& key) { if (root == NULL) return false; if (key > root->_key) return _RemoveR(root->_right, key); else if (key < root->_key) return _RemoveR(root->_left, key); else { Node* del = root; if (root->_left == NULL) { root = root->_right; } else if (root->_right == NULL) { root = root->_left; } else { Node* parent = root; Node* left = root->_left; while (left->_right) { parent = left; left = left->_right; } del = left; root->_key = left->_key; if (left == parent->_right) parent->_right = left->_left; else parent->_left = left->_left; } delete del; } return true; } bool _InsertR(Node*& root, const K& key) { if (root == NULL) root = new Node(key); if (key > root->_key) return _InsertR(root->_right, key); else if (key < root->_key) return _InsertR(root->_left, key); else return false; } void _InOrder(Node* root) { if (root) { _InOrder(root->_left); std::cout << root->_key << " "; _InOrder(root->_right); } } void _copy(Node* root) { if (root == NULL) return; Node *_root = new Node(root->_key); _root->_left = NULL; _root->_right = NULL; if (root->_left) _copy(root->_left); if (root->_right) _copy(root->_right); } void _delete(Node*& root) { if (root != NULL) { _delete(root->_left); _delete(root->_right); delete root; root = NULL; } } protected: Node* _root; };