1. What is a binary search tree
1. Each node has a key code (key) as the basis for searching, and the key codes of all nodes are different from each other.
2. The key code (key) of all nodes on the left subtree is less than the key code (key) of the root node.
3. The key code (key) of all nodes on the right subtree is greater than the key code (key) of the root node.
4. The left and right subtrees are binary search trees.
Two. Code implementation of binary search tree (here we are mainly concerned with adding, deleting, checking and modifying)
< pre code_snippet_id="1948660" snippet_file_name="blog_20161025_1_9898293" class="cpp" name="code">#pragma onceusing namespace std;templatestruct SelectBinaryTreeNode{ typedef SelectBinaryTreeNode Node; K _key; Node* _left; Node* _right; SelectBinaryTreeNode(const K& key) :_key(key), _left(NULL), _right(NULL) {}};templateclass SelectBinaryTree{public: typedef SelectBinaryTreeNode Node; SelectBinaryTree() { } SelectBinaryTree(const SelectBinaryTree& sbt) //Copy construction, recursive realization {_root=_Copy(sbt._root);} ~SelectBinaryTree() //Destruct, recursive realization {_Delete(_root);} bool Find(const K& key) //Non-recursive search {if (NULL == _root) return false; Node* cur = _root; while (cur) {if (cur->_key _right; else if (cur->_key >key) cur = cur->_left; else return true;} return false;} bool FindR(const K& key) //Recursive search {return _FindR(_root, key);} void InOrder() //In-order traversal { _InOrder(_root ); cout << endl;} bool Insert(const K& key) //Non-recursive insert {if (NULL == _root) {_root = new Node(key); return true;} Node* cur = _root; Node* parent = NULL; while (cur) {if (cur->_key _right;} else if (cur->_key>key) {parent = cur; cur = cur-> _left;} else return false;} if (parent->_key _right = new Node(key);} else parent->_left = new Node(key); return true;} bool InsertR(const K& key) //Recursive insert {return _InsertR(_root, key);} bool RemoveR(const K& key) //Recursive delete {return _RemoveR(_root, key);} bool Remove(const K& key) //Non-recursive delete {if (NULL == _root) return false; Node* cur = _root; Node* parent = NULL; while (cur) {if (cur->_key _right;} else if (cur->_key>key) {parent = cur; cur = cur->_left;} else //found to delete {Node* del = cur; if (cur->_left == NULL) //left Empty {if (parent == NULL) //to delete Is the root node _root = cur->_right; else {if (parent->_left == cur) parent->_left = cur->_right; else parent->_right = cur->_right;}} else if (cur ->_right == NULL) //right is empty {if (NULL == parent) _root = cur->_left; else {if (parent->_left == cur) parent->_left = cur->_left; else parent->_right = cur->_left;}} else // Both left and right are not empty {Node* pcur = cur->_right; Node* pparent = cur; while (pcur->_left) //Find the most right tree Left node {pparent = pcur; pcur = pcur->_left;} //K tmp = cur->_key; //cur->_key = pcur->_key; //pcur->_key = tmp; //Find Later, it should be exchanged as above, but because pcur is about to be deleted, it is good to assign directly cur->_key = pcur->_key; del = pcur; if (pparent->_left == pcur) pparent->_left = pcur ->_right; else pparent->_right = pcur->_right;} delete del; return true;}} return false; }protected: bool _RemoveR(Node*& root, const K& key) {if (root->_ke y _right, key); else if (root->_key>key) return _RemoveR(root->_left, key); else {Node* del = root; if (root->_left == NULL) //The left of the node to be deleted is empty {root = root->_right;} else if (root->_right == NULL )//The right of the node to be deleted is empty {root = root-> _left;} else // Both left and right are not empty {Node* pcur = root->_right; while (pcur->_left) {pcur = pcur->_left;} root->_key = pcur->_key; del = pcur ;} delete del; return true;} return false;} bool _InsertR(Node*& root, const K& key) {if (NULL == root) {root = new Node(key); return true;} if (root- >_key _right, key); else if (root->_key>key) return _InsertR(root->_left, key); else return false;} bool _FindR(Node* root, const K& key) {if (NULL == root) return false; if (root->_key == key) return true; else if (root->_key _right, key); else if ( root->_key>key) _FindR(root->_left, key);} void _Delete(Node* root) //Recursive delete {if (root) {_Delete(root->_left); _Delete(root->_right); delete root;}} Node* _Copy(Node* sroot) //Recursive copy {Node* cur = NULL; if (sroot) {cur = new Node(sroot->_key); cur->_left = _Copy(sroot->_left); cur->_right = _Copy(sroot->_right);} return cur;} void _InOrder(Node* root) {if (NULL == root) return; _InOrder(root->_left); cout << root->_key<<" "; _InOrder(root->_right); }private: Node* _root ;};void TestSelectBinaryTree() //Test the non-recursive version {int a[] = {5, 3, 4, 1, 7, 8, 2, 6, 0, 9 }; SelectBinaryTree sbt; for (size_t i = 0; i sbt1(sbt); //Test copy construction sbt1.InOrder (); sbt.InOrder(); sbt.Remove(0); sbt.Remove(1); sbt.Remove(2); sbt.Remove(3); sbt.Remove(4); sbt.Remove(5) ; sbt.Remove(6); sbt.Remove(7); sbt.Remove(8); sbt.Remove(9); sbt.InOrder(); //cout< sbt; for (size_t i = 0; i sbt1(sbt) ; //Test copy construction sbt1.InOrder(); sbt.InOrder(); sbt.RemoveR(0); sbt.InOrder(); sbt.RemoveR(1); sbt.InOrder(); sbt.RemoveR(2) ; sbt.InOrder(); sbt.RemoveR(3); sbt.InOrder(); sbt.RemoveR(4); sbt.InOrder(); sbt.RemoveR(5); sbt.InOrder(); sbt.RemoveR( 6); sbt.InOrder(); sbt.RemoveR(7); sbt.InOrder(); sbt.RemoveR(8); sbt.InOrder(); sbt.RemoveR(9); sbt.InOrder(); // cout<
