#include #include using namespace std; template struct BTNode { T _val; BTNode* _left; BTNode* _right; BTNode(const T& val = T()) :_val(val), _left(nullptr), _right(nullptr) { } }; template class BSTree { public: typedef BTNode Node; public: Node* find(const T& val) { Node* cur=_root; while (cur) { if (cur->_val == val) { return cur; } else if (cur->_val < val) { cur=cur->_right; } else { cur=cur->_left; } } return nullptr; } bool insert(const T& val) { if (_root == nullptr) { _root=new Node(val); return true; } Node* parent=nullptr; Node* cur=_root; while (cur) { parent=cur; if (cur->_val == val) { return false; } else if (cur->_val > val) { cur=cur->_left; } else { cur=cur->_right; } } cur=new Node(val); if (cur->_val > parent->_val) { parent->_right=cur; } else { parent->_left=cur; } return true; } void inorder() { Node* cur=_root; look(cur); } void look(Node* cur) { if (cur == nullptr) { return; } look(cur->_left); cout<_val; look(cur->_right); } bool erase(const T& val) { if (_root == nullptr) { return false; } Node* parent; Node* cur = _root; while (cur) { if (cur->_val == val) { break; } else if (cur->_val > val) { parent = cur; cur = cur->_left; } else { parent = cur; cur = cur->_right; } } if (cur == nullptr) { return false; } if (cur->_left == nullptr && cur->_right == nullptr) { if (cur == _root) { _root = nullptr; } else if (parent->_left == cur) { parent->_left = nullptr; delete cur; } else { parent->_right = nullptr; delete cur; } } else if (cur->_left == nullptr) { if (cur == _root) { _root = _root->_right; } else if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } delete cur; } else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else if (parent->_left = cur) { parent->_left = cur->_left; } else if (parent->_right = cur) { parent->_right = cur->_left; } delete cur; } else { Node* leftMostNode = cur->_right; Node* par = cur; while (leftMostNode->_left) { par = leftMostNode; leftMostNode = leftMostNode->_left; } cur->_val = leftMostNode->_val; if (par->_left == leftMostNode) { par->_left = leftMostNode->_right; } else { par->_right = leftMostNode->_right; } delete leftMostNode; } } ~BSTree() { destroy(_root); } void destroy(Node* root) { if (root == nullptr) { return; } destroy(root->_left); destroy(root->_right); delete root; } BSTree() { } BSTree(const BSTree& bs) { _root=copy(bs._root); } Node* copy(Node* cur) { if (cur == nullptr) { return nullptr; } Node* root=new Node(cur->_val); root->_left=copy(cur->_left); root->_right=copy(cur->_right); return root; } BSTree& operator = (const BSTree bs) { swap(_root,bs._root); return this; } private: Node _root=nullptr; }; void test() { BSTreebs; bs.insert(1); bs.insert(3); bs.insert(6); bs.insert(2); bs.insert(8); bs.insert(9); bs.inorder(); BSTreebs2(bs); cout<<endl; BSTreebs3=bs; bs2.inorder(); bs3.inorder(); } int main() { test(); return 0; }
