The meaning of a binary search tree is that the value of each left child in this binary tree is smaller than its parent node, and the value of each right child is smaller than the parent node An ordered array will appear after traversing the large and middle order
Insert
Insert a node every time it is inserted in a leaf node
It is relatively simple to implement
Recursive and non-recursive are implemented
bool _InsertR(Node* root,const K& key) {//Initialize the insertion node Node* node=new Node(key); node->_key=key; node->_left=node- >_right=node->_parent=NULL; //When the tree is empty, directly serve as the root node if((root)==NULL) {root=node; return true;} //Insert into the current node (*root) If((root)->_left == NULL && (root)->_key> key){ node->_parent=root; root->_left=node; return true;} //Insert into the current node (*Root) right child if((root)->_right == NULL && (root)->_key _parent=root; (root)->_right=node; return true;} if (root->_key> key) _InsertR(r oot->_left,key); else if(root->_key _right,key); else return true;
}bool _Insert2(Node*& root,const K& key) {if(root==NULL) {root=new Node(key); return true;} if(root->_key< key) return _Insert2(root->_right,key); else if(root->_key>key) return _Insert2(root->_left,key); else return false; }
Find
bool FindR(const K& key) {if(_root==NULL) return false; Node * cur=_root; while(cur) {if(cur->_key_right; else if(cur->_key>key) cur=cur->_left; else return true;} }< /pre>
It is difficult to delete a node. There are four cases 1. The deleted node has no left child
2. The deleted node has no right child
p> 3. The deleted node has no left or right children
4. The deleted node has both right and left children
Recursive implementation
bool _Remove(Node*& root,const K& key) {if (root==NULL) {return false;} if(root->_key_right,key);} else if(root->_key>key) {return _Remove(root->_left,key);} else {Node* del=root; if(root->_left==NULL) { root=root->_right;} else if(root->_right==NULL) {root=root->_left;} delete del;} return true; }
Non-recursive implementation
bool Remove(const K& key)//Non-recursive {if(_root==NULL) return false; Node* pre=NULL; Node* cur=_root; Node* del=cur; while (cur&&cur->_key!=key) {if(cur->_key>key) {pre=cur; cur=cur-> _left;} else if (cur->_key_right;}} if(cur->_left==NULL) {if(cur==_root) _root=cur-> _right; else if(cur==pre->_left) {pre->_left=cur->_right;} else {pre->_right=cur->_right; } del=cur;} else if (cur->_right==NULL) {if(cur==_root) {_root=cur->_left;} else if (pre->_left==cur) {pre->_left ==cur->_left;} else {pre->_right=cur->_left;} del=cur;} else {Node* minRight=cur->_right;//The leftmost node of the right child pre=cur; while ( minRight->_left) {pre=minRight; minRight=minRight->_left;} del=minRight; cur->_key=minRight->_key;//Exchange node value if(pre->_left==minRight) {pre- >_left=minRight->_right;} else {pre->_right=minRight->_right;}} delete del; return true; }
Source code
< /p>
#includeusing namespace std;templatestruct SearchBinaryTreeNode{ SearchBinaryTreeNode* _left; SearchBinaryTreeNode* _right; SearchBinaryTreeNode* _parent; K _key; SearchBinaryTreeNode(const K& key) :_key(key) ,_left(NULL) ,_right(NULL) ,_parent(NULL) {));templateclass Sea rchBinaryTree{ typedef SearchBinaryTreeNode Node;public: SearchBinaryTree() :_root(NULL) {} SearchBinaryTree(const SearchBinaryTree& t) {_root=t->_root;} ~SearchBinaryTree() {delete _root;} bool InsertR(const K& key) // Insert node {if (!_root) // Empty tree {_root = new Node(key); _root->_key = key;} else {_InsertR(_root, key);} return true; } bool Insert2(const K& key)//recursive {_Insert2(_root,key); return true;} bool Remove2(const K& key)//recursive {_Remove(_root,key); return true;} bool Remove(const K& key)//Non-recursive {if(_root==NULL) return false; Node* pre=NULL; Node* cur=_root; Node* del=cur; while (cur&&cur->_key!=key) {if(cur- >_key>key) {pre=cur; cur=cur->_left;} else if (cur->_key_right;}} if(cur->_left== NULL) {if(cur==_root) _root=cur->_right; else if(cur==pre->_left) {pre->_left=cur->_right;} else {pre->_right=cur-> _right;} del=cur;} else if (cur->_right==NULL) {if (cur==_root) {_root=cur->_left;} else if (pre->_left==cur) {pre->_left==cur->_left;} else {pre->_right=cur->_left ;} del=cur;} else {Node* minRight=cur->_right;//The leftmost node of the right child pre=cur; while (minRight->_left) {pre=minRight; minRight=minRight->_left;} del =minRight; cur->_key=minRight->_key;//Exchange node value if(pre->_left==minRight) {pre->_left=minRight->_right;} else {pre->_right=minRight-> _right;}} delete del; return true;} bool FindR(const K& key) {if(_root==NULL) return false; Node* cur=_root; while(cur) {if(cur->_key_right; else if(cur->_key>key) cur=cur->_left; else return true;}} void InOrder()//Inorder traversal {_InOrder(_root); cout<_key=key; node->_left=node->_right=node-> _parent=NULL; //When the tree is empty, it is directly used as the root node if((root)==NULL) {root=node; return true;} / / Insert the left child of the current node (*root) if((root)->_left == NULL && (root)->_key> key){ node->_parent=root; root->_left=node; return true;} //Insert the right child of the current node (*root) if((root)->_right == NULL && (root)->_key _parent=root; (root)- >_right=node; return true;} if(root->_key> key) _InsertR(root->_left,key); else if(root->_key _right,key); else return true;} bool _Insert2(Node*& root,const K& key) {if(root==NULL) {root=new Node(key); return true;} if(root->_key_right,key); else if(root->_key>key) return _Insert2(root->_left,key); else return false;} void _InOrder(Node* root) {Node* cur=root; if(cur= =NULL) return; _InOrder(cur->_left); cout<_key<<" "; _InOrder(cur->_right);} bool _Remove(Node*& root,const K& key) {if (root ==NULL) {return false;} if(root->_key_right,key);} else if(root->_key>key) {return _Remove(root->_left,key);} else {Node* del=root; if(root->_left==NULL) {root=root->_right;} else if(root->_right==NULL ) {root=root->_left;} delete del;} return true; }private: Node* _root;};void test(){SearchBinaryTree BSTree;//15,6,18,3,7,17 ,20,2,4,13,9BSTree.InsertR(15);BSTree.InsertR(6);BSTree.InsertR(18);BSTree.InsertR(3);BSTree.InsertR(7);BSTree.InsertR(17) ;BSTree.InsertR(20);BSTree.InsertR(2);BSTree.InsertR(4);BSTree.InsertR(13);BSTree.InsertR(9);BSTree.Insert2(10);BSTree.InOrder();BSTree .Remove2(13);BSTree.InOrder();BSTree.Remove(6);BSTree.InOrder();cout<