二叉排序树的定义及查找
二叉排序树，又称二叉查找树，是一种特殊的二叉树。它具有以下几个特点：
1.所有节点都比它的左子树上的节点大，比它的右子树上的节点小；
2.任意一个节点左子树和右子树都是二叉排序树；
3.没有键值相等的节点。
因此，二叉排序树可以帮助我们高效地查找数据，同时也可以对数据进行排序。在此文章中，我们将从定义、插入、删除、查找和应用方面来详细分析二叉排序树。
定义
根据上述特点，我们可以得到一个节点的定义：
```C++
struct node
{
int data; //节点中存储的数据
struct node *left; //指向左子节点的指针
struct node *right; //指向右子节点的指针
};
```
插入
向二叉排序树中插入一个节点，需要遵循以下基本步骤：
1.若根节点为空，当前节点为根节点；
2.若插入节点的数据小于根节点的数据，在左子树中插入节点；
3.若插入节点的数据大于根节点的数据，在右子树中插入节点。
代码实现如下：
```C++
struct node *insert(struct node *node, int data)
{
if(node == nullptr) //如果根节点为空
{
struct node *temp = (struct node*)malloc(sizeof(struct node)); //创建新节点
temp->data = data; //存储数据
temp->left = nullptr;
temp->right = nullptr;
return temp; //返回该节点
}
if(data < node->data) //如果数据小于根节点
{
node->left = insert(node->left, data); //在左子树中插入节点
}
else if(data > node->data) //如果数据大于根节点
{
node->right = insert(node->right, data); //在右子树中插入节点
}
return node; //返回该节点
}
```
删除
在二叉排序树中删除一个节点，同样需要遵循以下基本步骤：
1.搜索要删除的节点；
2.如果节点是一片叶子，则直接删除；
3.如果节点有一个子节点，将该节点的子节点代替该节点；
4.如果节点有两个子节点，找到该节点右子树中的最小节点，将其数据复制到该节点中，然后删除该最小节点。
代码实现如下：
```C++
struct node *deleteNode(struct node *root, int key)
{
if(root == nullptr) //如果根节点为空
{
return root;
}
if(key < root->data) //如果查找节点的数据小于根节点
{
root->left = deleteNode(root->left, key); //在左子树中删除节点
}
else if(key > root->data) //如果查找节点的数据大于根节点
{
root->right = deleteNode(root->right, key); //在右子树中删除节点
}
else //如果查找节点的数据等于根节点
{
if(root->left == nullptr && root->right == nullptr) //叶节点
{
free(root); //直接删除
root = nullptr;
return root;
}
else if(root->left == nullptr) //只有右子节点
{
struct node *temp = root;
root = root->right;
free(temp);
return root;
}
else if(root->right == nullptr) //只有左子节点
{
struct node *temp = root;
root = root->left;
free(temp);
return root;
}
else //有两个子节点
{
struct node *temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
return root;
}
```
查找
在二叉排序树中查找一个节点，同样需要遵循以下基本步骤：
1.从根节点开始遍历；
2.比较查找节点的数据与当前节点的数据，如果相等则返回该节点，否则继续遍历它的左子树或右子树。
代码实现如下：
```C++
struct node *search(struct node *root, int key)
{
if(root == nullptr || root->data == key) //如果根节点为空或者根节点的数据等于查找节点的数据
{
return root;
}
if(root->data < key) //如果根节点的数据小于查找节点的数据
{
return search(root->right, key); //在右子树中查找
}
return search(root->left, key); //在左子树中查找
}
```
应用
二叉排序树在实际应用中有很多用处。例如，它可以帮助我们快速查找某个数据是否存在、进行数据的排序、单词的集合（如英文单词）等。此外，二叉排序树还可以用来实现高效率的图搜索算法，如A*搜索算法。
