Binary search tree

1. Content arrangement description

The binary tree is in front C The data structure phase has been talked about , This section is named binary tree advanced because ：
1. map and set Features need to pave the way for a binary search tree , The binary search tree is also a tree structure
2. Understand the characteristics of binary search tree , Help to understand better map and set Characteristics of
3. Some interview questions in the binary tree are a little difficult , It's not easy for everyone to accept , And it's easy to forget for a long time
4. There are some OJ Question use C Language implementation is troublesome
2. Binary search tree

2.1 Binary search tree concept

Binary search tree is also called binary sort tree , It could be an empty tree , Or a binary tree with the following properties :
If its left subtree is not empty , Then the values of all nodes on the left subtree are smaller than the values of the root nodes
If its right subtree is not empty , Then the value of all nodes on the right subtree is greater than the value of the root node
Its left and right subtrees are also binary search trees

2.2 Binary search tree operation

1. Binary search tree lookup

 2. Binary search tree insertion
The specific process of insertion is as follows ：
a. The tree is empty. , And just insert

 b. The tree is not empty , Find the insertion position according to the nature of binary search tree , Insert new node

 3. Deletion of binary search tree
First, find out whether the element is in the binary search tree , If it doesn't exist , Then return to , Otherwise, the nodes to be deleted may be divided into the following four situations ：
a. The node to be deleted has no children
b. Only the left child node is to be deleted
c. Only the right child node is to be deleted
d. The node to be deleted has left 、 Right child node
It seems that the nodes to be deleted are 4 Medium condition , Physical truth a Can be related to the situation b perhaps c combined , So the real deletion process is as follows ：
situation b： Delete the node and make the parent node of the deleted node point to the left child node of the deleted node
situation c： Delete the node and make the parent node of the deleted node point to the right child node of the deleted node
situation d： Look for the first node under the middle order in its right subtree ( Key minimum ), Fill the deleted node with its value , Then deal with the deletion of this node

2.3 Implementation of binary search tree

template<class T>
struct BSTNode
{
BSTNode(const T& data = T())
: _pLeft(nullptr) , _pRight(nullptr), _data(data)
{}
BSTNode<T>* _pLeft;
BSTNode<T>* _pRight;
T _data;
};
template<class T>
class BSTree
{
typedef BSTNode<T> Node;
typedef Node* PNode;
public:
BSTree(): _pRoot(nullptr)
{}
//  Students realize it by themselves , Similar to the destruction of binary trees 
~BSTree();
//  Search according to the properties of binary search tree ： Find the value for data The position of the node in the binary search tree 
PNode Find(const T& data);
bool Insert(const T& data)
{
//  If the tree is empty , Directly inserted into the 
if (nullptr == _pRoot)
{
_pRoot = new Node(data);
return true;
}
//  Search according to the properties of binary search tree data Insertion position in the tree 
PNode pCur = _pRoot;
//  Record pCur My parents , Because the new element is finally inserted in pCur The position of parents around their children 
PNode pParent = nullptr;
while (pCur)
{
pParent = pCur;
if (data < pCur->_data)
pCur = pCur->_pLeft;
else if (data > pCur->_data)
pCur = pCur->_pRight; //  The element already exists in the tree 
else
return false;
}
//  Insert elements 
pCur = new Node(data);
if (data < pParent->_data)
pParent->_pLeft = pCur;
else
pParent->_pRight = pCur;
return true;
}
bool Erase(const T& data)
{
//  If the tree is empty , Delete failed 
if (nullptr == _pRoot)
return false;
//  Find in data Position in the tree 
PNode pCur = _pRoot;
PNode pParent = nullptr;
while (pCur)
{
if (data == pCur->_data)
break;
else if (data < pCur->_data)
{
pParent = pCur;
pCur = pCur->_pLeft;
}
else
{
pParent = pCur;
pCur = pCur->_pRight;
}
}
// data Not in the binary search tree , Cannot delete 
if (nullptr == pCur)
return false;
//  Delete in the following cases , Students draw and analyze by themselves 
if (nullptr == pCur->_pRight)
{
//  The current node has only the left child or the left child is empty --- It can be deleted directly 
}
else if (nullptr == pCur->_pRight)
{
//  The current node has only right children --- It can be deleted directly 
}
else
{
//  There are children on both sides of the current node , It's not easy to delete directly , You can find an alternative node in its subtree , such as ：
//  Find the largest node in its left subtree , That is, the rightmost node in the left subtree , Or the smallest node in its right subtree , namely 
 The smallest node in the right subtree 
//  After the replacement node is found , Give the value in the substitute node to the node to be deleted , Convert to delete substitute node 
}
return true;
}
// Realize it by yourself 
void InOrder();
private:
PNode _pRoot;