用C语言编写算法实现对依次输入的关键字序列建立二叉排序树,并能实现二叉排序树的查找、插入和删除运算。
时间: 2024-03-09 22:49:11 浏览: 82
好的,我可以为您解答这个问题。
首先,我们需要了解二叉排序树的概念。二叉排序树是一种特殊的二叉树,它的左子树中所有节点的关键字都小于根节点的关键字,而右子树中所有节点的关键字都大于根节点的关键字。因此,二叉排序树的中序遍历是一个递增的序列。
接下来,我们需要实现三个运算:查找、插入和删除。具体实现如下:
1. 查找
查找操作很简单,只需要从根节点开始,比较要查找的关键字和当前节点的关键字的大小关系,如果相等则返回该节点,否则递归地在左子树或右子树中查找。
```c
struct TreeNode* search(struct TreeNode* root, int key) {
if (root == NULL || root->key == key) {
return root;
}
if (key < root->key) {
return search(root->left, key);
} else {
return search(root->right, key);
}
}
```
2. 插入
插入操作需要先查找要插入的位置,然后在该位置插入一个新节点。如果要插入的关键字已经存在,则不需要插入。
```c
struct TreeNode* insert(struct TreeNode* root, int key) {
if (root == NULL) {
return createNode(key);
}
if (key < root->key) {
root->left = insert(root->left, key);
} else if (key > root->key) {
root->right = insert(root->right, key);
}
return root;
}
```
3. 删除
删除操作比较复杂,需要考虑删除节点的子树情况。如果要删除的节点没有子树,直接删除即可。如果要删除的节点只有一个子树,将该子树连接到删除节点的父节点上即可。如果要删除的节点有两个子树,需要找到该节点的中序遍历的后继节点,将后继节点的值复制到要删除的节点上,然后删除后继节点。
```c
struct TreeNode* delete(struct TreeNode* root, int key) {
if (root == NULL) {
return root;
}
if (key < root->key) {
root->left = delete(root->left, key);
} else if (key > root->key) {
root->right = delete(root->right, key);
} else {
if (root->left == NULL) {
struct TreeNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct TreeNode* temp = root->left;
free(root);
return temp;
}
struct TreeNode* temp = minValueNode(root->right);
root->key = temp->key;
root->right = delete(root->right, temp->key);
}
return root;
}
```
这样,我们就完成了二叉排序树的建立、查找、插入和删除操作的实现。完整代码如下:
阅读全文