二叉搜索树又称二叉排序树(Binary Search Tree)，简称BST。主要用于查找搜索。
如果理解起来有些抽象，可以尝试这个网站，可视化演示操作过程：visualgo
定义
二叉搜索树或者为空树或者满足如下条件：
- 若左子树非空，左子树全部节点小于根节点
- 若右子树非空，右子树全部节点大于根节点
- 左右子树均满足以上两点（递归定义的）
二叉搜索树是没有重复元素的。
优势在于查找和插入，时间复杂度可以达到O(logn)。
如上图即为一颗BST树。
查找
如图为查找50的过程
从根节点开始，若节点为NULL，否则比较根节点与搜索值的大小关系，如果相等则查找成功，如果小于根节点值则转到左子树上继续查找，同理若大于节点值则转到右节点上继续查找。
BSTNode *BSTNode::findNode(int val)
{
if (val == value)
return this;
else if (val < value)
{
if (left == NULL)
return NULL;
return left->findNode(val);
}
else if (val > value)
{
if (right == NULL)
return NULL;
return right->findNode(val);
}
return NULL;
}插入
如图为插入8的过程：
插入的关键是找到插入的位置, 可以在查找的基础上改装成插入，即若查找成功代表插入值已存在于BST中无需再次插入，查找失败（找到了NULL），则该位置即为需要插入的位置。
void BSTNode::insertNode(int val)
{
if (val < value)
{
if (left == NULL)
{
left = new BSTNode(val);
left->parent = this;
}
else
left->insertNode(val);
}
else if (val > value)
{
if (right == NULL)
{
right = new BSTNode(val);
right->parent = this;
}
else
right->insertNode(val);
}
}删除
首先定义两个概念：
前驱结点：节点val值小于该节点val值并且值最大的节点
后继节点：节点val值大于该节点val值并且值最小的节点
相比较而言删除操作较为复杂，需要考虑多种情况：
假设待删除节点为d
- 若d为叶节点，则直接删除即可。
- 若节点只有左子树，则将左子树改为d父节点的子树。（右节点同理）
- 若d有两棵子树,则让d的后继（或者前驱）节点x取代d的位置，并将原位置的x删除掉（此时会转换成1或2的情况）
由于前两者情况较为简单，这里演示第三种情况：
删除如图BST中值为7的节点：
首先查找到6：
然后发现6的左右子树均非空，这里选择右子树，查找到后继节点8
用8替代7的位置
由于8节点为叶节点，因此直接删除。
void BSTNode::delNode()
{
if (left != NULL && right != NULL)
{
BSTNode *temp = left->findMax();
value = temp->value;
temp->delNode();
}
else
{
if (left == NULL)
{
if (this == parent->left)
{
parent->left = right;
}
else
{
parent->right = right;
}
if (right != NULL)
{
right->parent = parent;
}
}
else
{
if (this == parent->left)
{
parent->left = left;
}
else
{
parent->right = left;
}
left->parent = parent;
}
}
}完整代码
#include <bits/stdc++.h>
using namespace std;
class BSTNode
{
public:
int value;
BSTNode *left;
BSTNode *right;
BSTNode *parent;
public:
BSTNode(int val);
BSTNode *findNode(int val);
void insertNode(int val);
void delNode();
BSTNode *findMin();
BSTNode *findMax();
};
BSTNode *BSTNode::findMin()
{
BSTNode *tmp = this;
while (tmp->left != NULL)
tmp = tmp->left;
return tmp;
}
BSTNode *BSTNode::findMax()
{
BSTNode *tmp = this;
while (tmp->right != NULL)
tmp = tmp->right;
return tmp;
}
void BSTNode::delNode()
{
if (left != NULL && right != NULL)
{
BSTNode *temp = left->findMax();
value = temp->value;
temp->delNode();
}
else
{
if (left == NULL)
{
if (this == parent->left)
{
parent->left = right;
}
else
{
parent->right = right;
}
if (right != NULL)
{
right->parent = parent;
}
}
else
{
if (this == parent->left)
{
parent->left = left;
}
else
{
parent->right = left;
}
left->parent = parent;
}
}
}
BSTNode::BSTNode(int val)
{
value = val;
left = right = parent = NULL;
}
BSTNode *BSTNode::findNode(int val)
{
if (val == value)
return this;
else if (val < value)
{
if (left == NULL)
return NULL;
return left->findNode(val);
}
else if (val > value)
{
if (right == NULL)
return NULL;
return right->findNode(val);
}
return NULL;
}
void BSTNode::insertNode(int val)
{
if (val < value)
{
if (left == NULL)
{
left = new BSTNode(val);
left->parent = this;
}
else
left->insertNode(val);
}
else if (val > value)
{
if (right == NULL)
{
right = new BSTNode(val);
right->parent = this;
}
else
right->insertNode(val);
}
}
/**
* @brief
*
*/
class BST
{
public:
BST();
BST(vector<int> v);
BSTNode *find(int val);
BSTNode *root;
bool del(int val);
void insert(int val);
};
BST::BST()
{
root = NULL;
}
BST::BST(vector<int> v)
{
root = NULL;
for (int i = 0; i < v.size(); i++)
{
root->insertNode(v[i]);
}
}
BSTNode *BST::find(int val)
{
if (root == NULL)
return NULL;
else
return root->findNode(val);
}
void BST::insert(int val)
{
if (root == NULL)
root = new BSTNode(val);
else
{
root->insertNode(val);
}
}
bool BST::del(int val)
{
BSTNode *findNode = find(val);
if (findNode == NULL)
return false;
if (findNode == root)
{
if (root->left == NULL && root->right == NULL)
{
root = NULL;
delete findNode;
}
else if (root->left == NULL)
{
root = root->right;
root->parent = NULL;
delete findNode;
}
else if (root->right == NULL)
{
root = root->left;
root->parent = NULL;
delete findNode;
}
else
{
root->delNode();
}
}
else
{
root->delNode();
}
return true;
}创建
创建就是按顺序的插入过程