Binary search tree, also called binary sort tree, binary search tree. It has the following characteristics:
The value of the left subtree Less than the value of the root node, the value of the right subtree is greater than the value of the root node; the result of the in-order traversal of the binary search tree
yesone an ascending sequence.
Of course, the empty tree is also a binary search tree.
Satisfy the properties of the binary search tree globally, but also locally.
Since it has the above properties, the binary tree search is quite convenient, of course, insertion and deletion, complexity It will also be obvious
dropLow.
Search: Starting from the root node, if the key to be inserted is smaller than the key of the root node, move to the left Go, otherwise go to the right and find
toreturn directly, if it has gone to the empty but not found, it means that the key to be searched does not exist. The implementation is given below
generationCode:
bool FindNonR(const K& key) {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; }
The recursive version is relatively simple, so the implementation will not be given here.
Insert: Find a suitable empty position, insert the element, if you want to insert the value, search in the original It has been saved in the binary tree
can’t insert it. The following drawing instructions:
According to the diagram above, write the following code:
bool InsertNonR(const K& key) {if (NULL == _root)//empty Tree {_root = new Node(key); return true;} //Not an empty tree Node* cur = _root; Node* parent = NULL; while (cur) {if (cur->_key _right;} else if (cur->_key> key) {parent = cur; cur = cur->_left;} else//Already existing value {return false;}} Node* NewNode = new Node (key); if (key < parent->_key) parent->_left = NewNode ; else parent->_right = NewNode; return true; }
< p>From the figure above, we can see that the inserted element must remember the parent node, otherwise the connection operation cannot be realized.
Binary search tree can also be implemented recursively: the implementation code is given below: p>
bool _InsertR(Node*& root, const K& key) {if (root == NULL) {root = new Node(key); return true;} Node* cur = root; if (cur->_key < key) {_InsertR(cur->_right,key);} else if (cur->_key> key) {_InsertR(cur->_left, key);} else return false; }
In this code, we can see: In the formal parameters, we use reference to pass parameters, which cleverly use the quoteUsed
Property: the alias of the variable, both of which are modified at the same time.
When the original tree is empty Tree (_root == NULL), the change of root directly affects the change of _root;
When there are some elements in the original tree, (using the example above, insert 3)
< span style="font-family:SimHei; font-size:24px"> (some search steps are omitted in the previous section) The left of 4 is empty, go to the first if of the function, create A new node, connected to
root, the root at this time is 4left alias, so both have changed, played a role in connection.
Delete: Find the element you want to delete and delete it. This is more complicated. Illustration:
The code implementation is given below:
bool RemoveNonR(const K& key) {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 {Node* del = NULL; //Directly delete leaf nodes if (cur->_left == NULL && cur->_right == NULL) {if (parent && cur == parent->_left) {parent->_left = NULL; del = cur;} else if (parent && cur == parent->_right) {parent->_right = NULL; del = cur;} else {del = cur; _root = NULL;}} //A node with only one child else if (cur->_left == NULL || cur->_right == NULL) {//Only the left child if (cur->_left != NULL) {if (parent == NULL) {_root = parent->_left; del = cur;} else if (parent->_left == cur) {parent->_left = cur->_left;} else {parent->_right = cur->_left;}} //Only right child else {if (parent == NULL) {_root = cur->_right; del = cur;} else if (parent->_right == cur) {parent-> _right = cur->_right;} else//cur is the left child of parent {parent->_left = cur ->_right;}}} else//Node with two children {Node* tmp = cur->_right;//Find the leftmost node of the right subtree while (tmp && tmp->_left) {parent = tmp; tmp = tmp->_left;} swap(cur->_key,tmp->_key); //Delete tmp node //tmp is a leaf node, tmp has only one child node if (tmp == parent-> _left) {parent->_left = tmp->_right;} else {parent->_right = tmp->_right;} del = tmp;} delete del; del = NULL; return true;}} //Not found to delete的值 return false; }
For deleting operations, you can also use recursive implementation:
Code:
bool _RemoveR( Node*& root,const K& key) {if (root == NULL) return false; if (root->_key _right,key);} else if (root->_key> key ) {_RemoveR(root->_left,key);} else {Node* del = root; Node* parent = root; if (root->_left == NULL)//Only right child {root = root->_right ;} else if (root->_right ==NULL) {root = root->_left;} else {Node* minRight = root->_right; //Find the leftmost node of the right subtree while (minRight->_left ) {parent = minRight; minRight = minRight->_left;} root->_key = minRight->_key; if (minRight == parent->_right) {parent->_right = minRight->_right;} else {parent- > _LEFT = minright -> _ right;} DEL = minright;} Return true;}
In this code, finding the node to be deleted is a recursive operation. After finding, if the node has only one child or not
If you have children, directly Point the pointer to the current node Its child nodes or empty, using references, are well connected
up. If the current node has left and right children, use the non-recursive method to solve it.
[Complete Code]
#pragma once#includeusing namespace std;#includetemplatestruct SearchBinaryTreeNode{ K _key; SearchBinaryTreeNode* _left; SearchBinaryTreeNode* _right; SearchBinaryTreeNode(const K& key) :_key(key) ,_left(NULL ) ,_right(NULL) {}};templateclass SearchBinaryTree{ typedef SearchBinaryTreeNode Node;public: SearchBinaryTree() :_root(NULL) {} void InorderNonR() {_InorderNonR(_root);} void InsertR (const K& key) {_InsertR(_root,key);} void InOrderR() {_InOrderR(_root); cout << endl;} void RemoveR(const K& key) {_RemoveR(_root,key);} bool RemoveNonR(const K& key) {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 {Node* del = NULL; //Directly delete leaf nodes if (cur->_left == NULL && cur->_right == NULL) {if (parent && cur == parent->_left) {parent->_left = NULL; del = cur;} else if (parent && cur = = parent->_right) {parent->_right = NULL; del = cur;} else {del = cur; _root = NULL;}} //Node with only one child else if (cur->_left == NULL | | cur->_right == NULL) {//Only the left child if (cur->_left != NULL) {if (parent == NULL) {_root = parent->_left; del = cur;} else if (parent ->_left == cur) {parent->_left = cur->_left;} else {parent->_right = cur->_left;}} //Only the right child else {if (parent == NULL) {_root = cur->_right; del = cur;} else if (parent->_right == cur) {parent->_right = cur->_right;} else//cur is the left child of parent {parent->_left = cur->_right;}}} else//Node with two children {Node* tmp = cur->_right; //Find the leftmost node of the right subtree while (tmp && tmp->_left) {parent = tmp; tmp = tmp->_left;} swap(cur->_key,tmp->_key); //Delete tmp Node //tmp is a leaf node, tmp has only one child node if (tmp == parent->_left) {parent->_left = tmp->_right;} else {parent->_right = tmp->_right;} del = tmp;} delete del; del = NULL; return true;}} //The value to be deleted was not found return false;} bool FindNonR(const K& key) {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 InsertNonR(const K& key) {if (NULL == _root)//Empty tree {_root = new Node(key); return true;} //Not an empty tree Node* cur = _root; Node* parent = NULL; while (cur) {if (cur->_k ey _right;} else if (cur->_key> key) {parent = cur; cur = cur->_left;} else//Already existing value {return false ;}} Node* NewNode = new Node(key); if (key _key) parent->_left = NewNode; else parent->_right = NewNode; return true; }protected: bool _RemoveR(Node*& root ,const K& key) {if (root == NULL) return false; if (root->_key _right,key);} else if (root->_key> key) {_RemoveR( root->_left,key);} else {Node* del = root; Node* parent = root; if (root->_left == NULL)//Only right child {root = root->_right;} else if (root->_right ==NULL) {root = root->_left;} else {Node* minRight = root->_right; //Find the leftmost node of the right subtree while (minRight->_left) {parent = minRight; minRight = minRight->_left;} root->_key = minRight->_key; if (minRight == parent->_right) {parent->_right = minRight->_right;} else {parent->_left = minRight->_right;} del = minRight;} delete del;} return true;} void _InOrderR(Node* root) {if (root == NULL) return; _InOrderR(root->_left); cout << root- >_key << ""; _InOrderR(root->_right);} bool _InsertR(Node*& root, const K& key) {if (root == NULL) {root = new Node(key); return true;} Node * cur = root; if (cur->_key _right,key);} else if (cur->_key> key) {_InsertR(cur->_left, key);} else return false;} void _InorderNonR(Node* root) {if (NULL != root) {Node* cur = root; stack s; while (cur || !s.empty()) {while (cur) { s.push(cur); cur = cur->_left;} Node* top = s.top(); s.pop(); cout << top->_key << ""; cur = top->_right; }} cout << endl; }private: Node* _root;};void TestBinaySearchNonR(){ SearchBinaryTree bs; //int array[] = {2,4,1,3,6,5 }; int array [] = {5,3,4,1,7,8,2,6,0,9}; for (size_t i = 0; i <10; ++i) {bs.InsertNonR(array[i]) ;} bs .InorderNonR(); bs.FindNonR(3); bs.RemoveNonR(0); bs.InorderNonR(); bs.RemoveNonR(1); bs.RemoveNonR(2); bs.RemoveNonR(3); bs.RemoveNonR( 4); bs.RemoveNonR(5); bs.RemoveNonR(6); bs.RemoveNonR(7); bs.RemoveNonR(8); bs.RemoveNonR(9); bs.InorderNonR();)void TestBinaySearchR(){ SearchBinaryTree bs; int array[] = {5,3,4,1,7,8,2,6,0,9 }; for (size_t i = 0; i <10; ++i) {bs .InsertR(array[i]);} bs.InOrderR(); cout <
The realization of binary search tree is here~~~