c语言编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-13 10:26:40 浏览: 89
二叉排序树的操作(C语言实现)
好的,我可以为您提供实现思路和代码示例。
首先,我们需要定义一个二叉排序树的结构体,包含节点值、左子树、右子树三个属性。
```c
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
```
接下来,我们可以通过递归的方式构建一棵二叉排序树。具体实现如下:
```c
void insert(struct TreeNode** root, int val) {
if (*root == NULL) {
struct TreeNode* new_node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
new_node->val = val;
new_node->left = NULL;
new_node->right = NULL;
*root = new_node;
} else if (val < (*root)->val) {
insert(&((*root)->left), val);
} else {
insert(&((*root)->right), val);
}
}
```
在插入节点时,我们需要分别判断当前节点是否为空和待插入节点应该插在当前节点的左子树还是右子树中。如果当前节点为空,则直接将待插入节点插入到当前位置;否则递归地查找待插入节点的位置并插入。
接着,我们可以实现二叉排序树的查找操作。具体实现如下:
```c
struct TreeNode* search(struct TreeNode* root, int val) {
if (root == NULL || root->val == val) {
return root;
} else if (val < root->val) {
return search(root->left, val);
} else {
return search(root->right, val);
}
}
```
在查找节点时,我们需要分别判断当前节点是否为空和待查找节点与当前节点的大小关系。如果当前节点为空,则说明待查找节点不存在于二叉排序树中;否则递归地查找待查找节点的位置并返回。
最后,我们可以实现二叉排序树的删除操作。具体实现如下:
```c
struct TreeNode* delete(struct TreeNode* root, int val) {
if (root == NULL) {
return root;
} else if (val < root->val) {
root->left = delete(root->left, val);
} else if (val > root->val) {
root->right = delete(root->right, val);
} 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;
} else {
struct TreeNode* temp = minValueNode(root->right);
root->val = temp->val;
root->right = delete(root->right, temp->val);
}
}
return root;
}
struct TreeNode* minValueNode(struct TreeNode* node) {
struct TreeNode* current = node;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}
```
在删除节点时,我们需要分别判断当前节点是否为空和待删除节点与当前节点的大小关系。如果当前节点为空,则说明待删除节点不存在于二叉排序树中;否则递归地查找待删除节点的位置并删除。当待删除节点的左右子树都非空时,我们需要找到其右子树中最小的节点,并将其值赋给待删除节点,然后递归地删除右子树中的这个最小节点。
至此,我们已经完成了二叉排序树的创建、查找、插入和删除操作的实现。完整代码如下:
阅读全文