用C语言首先编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-13 14:29:19 浏览: 88
好的,下面是用C语言实现二叉排序树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
Node* createNode(int data) {
Node* node = (Node*) malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
void insert(Node** root, int value) {
if (*root == NULL) {
*root = createNode(value);
return;
}
if (value < (*root)->data) {
insert(&(*root)->left, value);
} else {
insert(&(*root)->right, value);
}
}
Node* search(Node* root, int value) {
if (root == NULL || root->data == value) {
return root;
}
if (value < root->data) {
return search(root->left, value);
}
return search(root->right, value);
}
Node* findMin(Node* root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}
Node* delete(Node* root, int value) {
if (root == NULL) {
return root;
}
if (value < root->data) {
root->left = delete(root->left, value);
} else if (value > root->data) {
root->right = delete(root->right, value);
} else {
if (root->left == NULL) {
Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
Node* temp = root->left;
free(root);
return temp;
}
Node* temp = findMin(root->right);
root->data = temp->data;
root->right = delete(root->right, temp->data);
}
return root;
}
void inorderTraversal(Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main() {
Node* root = NULL;
int n, value;
printf("Enter the number of nodes: ");
scanf("%d", &n);
printf("Enter the values of the nodes: ");
for (int i = 0; i < n; i++) {
scanf("%d", &value);
insert(&root, value);
}
printf("Inorder traversal of the tree: ");
inorderTraversal(root);
printf("\n");
printf("Enter the value to search: ");
scanf("%d", &value);
Node* found = search(root, value);
if (found != NULL) {
printf("%d found in the tree\n", value);
} else {
printf("%d not found in the tree\n", value);
}
printf("Enter the value to insert: ");
scanf("%d", &value);
insert(&root, value);
printf("Inorder traversal of the tree after insertion: ");
inorderTraversal(root);
printf("\n");
printf("Enter the value to delete: ");
scanf("%d", &value);
root = delete(root, value);
printf("Inorder traversal of the tree after deletion: ");
inorderTraversal(root);
printf("\n");
return 0;
}
```
这个程序中,我们使用了 `Node` 结构体来表示二叉排序树中的节点,其中包括了节点的数据、左子节点和右子节点。`createNode` 函数用来创建新的节点。`insert` 函数用来将新的值插入到二叉排序树中。`search` 函数用来查找给定的值是否在二叉排序树中。`findMin` 函数用来找到以某个节点为根的子树中的最小值节点。`delete` 函数用来删除二叉排序树中的某个节点。最后,`inorderTraversal` 函数用来对二叉排序树进行中序遍历,以输出其中所有的节点值。在 `main` 函数中,我们通过接收用户输入的方式来创建二叉排序树,并对其进行查找、插入和删除操作。
阅读全文
相关推荐
![-](https://img-home.csdnimg.cn/images/20241231044930.png)
![-](https://img-home.csdnimg.cn/images/20241231044833.png)
![-](https://img-home.csdnimg.cn/images/20241231045021.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![-](https://img-home.csdnimg.cn/images/20241231045021.png)
![-](https://img-home.csdnimg.cn/images/20241231045021.png)