首先用C语言编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-13 15:12:01 浏览: 50
好的,下面是对应的C语言代码实现。
首先,我们需要定义二叉排序树的结构体:
```c
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
```
接着,我们可以实现创建一棵二叉排序树的函数:
```c
TreeNode* createBST(int data) {
TreeNode* root = (TreeNode*) malloc(sizeof(TreeNode));
root->data = data;
root->left = NULL;
root->right = NULL;
return root;
}
void insert(TreeNode** root, int data) {
if (*root == NULL) {
*root = createBST(data);
} else if (data < (*root)->data) {
insert(&(*root)->left, data);
} else {
insert(&(*root)->right, data);
}
}
```
以上代码中,我们首先定义了一个createBST函数来创建一个节点,并返回该节点的指针。接着,我们定义了一个insert函数,用于向二叉排序树中插入一个节点。
接下来,我们实现二叉排序树的查找:
```c
TreeNode* search(TreeNode* root, int data) {
if (root == NULL || root->data == data) {
return root;
} else if (data < root->data) {
return search(root->left, data);
} else {
return search(root->right, data);
}
}
```
以上代码中,我们定义了一个search函数,用于在二叉排序树中查找指定的数据。如果找到了该数据,则返回该节点的指针;否则返回NULL。
最后,我们实现二叉排序树的删除:
```c
TreeNode* delete(TreeNode* root, int data) {
if (root == NULL) {
return root;
}
if (data < root->data) {
root->left = delete(root->left, data);
} else if (data > root->data) {
root->right = delete(root->right, data);
} else {
if (root->left == NULL) {
TreeNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
TreeNode* temp = root->left;
free(root);
return temp;
}
TreeNode* temp = minVal(root->right);
root->data = temp->data;
root->right = delete(root->right, temp->data);
}
return root;
}
TreeNode* minVal(TreeNode* node) {
TreeNode* current = node;
while (current->left != NULL) {
current = current->left;
}
return current;
}
```
以上代码中,我们定义了一个delete函数,用于删除二叉排序树中指定的节点。如果找到了该节点,则分为三种情况:
1. 被删除节点没有子节点,直接删除该节点;
2. 被删除节点只有一个子节点,将该子节点替换被删除节点;
3. 被删除节点有两个子节点,找到被删除节点右子树的最小值节点,将其替换被删除节点。
最后,我们定义了一个minVal函数,用于查找节点右子树的最小值节点。
完整代码如下: