二叉排序树的定义及查找

二叉排序树，又称二叉查找树，是一种特殊的二叉树。它具有以下几个特点：

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*搜索算法。