C语言编程首先编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-13 10:24:14 浏览: 117
好的,我可以为您提供一些 C 语言代码示例来实现这些功能。首先是创建二叉排序树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
struct Node* insertNode(struct Node* root, int data) {
if(root == NULL) {
return createNode(data);
}
if(data < root->data) {
root->left = insertNode(root->left, data);
}
else if(data > root->data) {
root->right = insertNode(root->right, data);
}
return root;
}
struct Node* createBST(char* str) {
struct Node* root = NULL;
char* token = strtok(str, " ");
while(token != NULL) {
int data = atoi(token);
root = insertNode(root, data);
token = strtok(NULL, " ");
}
return root;
}
```
这里我们定义了一个结构体 `Node` 来表示二叉排序树的节点,包含节点的数据、左子树和右子树。`createNode` 函数用于创建一个新的节点,`insertNode` 函数用于在二叉排序树中插入一个新的节点,`createBST` 函数用于从输入字符串中创建一棵二叉排序树。
接下来是二叉排序树的查找、插入和删除操作的代码:
```c
struct Node* searchNode(struct Node* root, int data) {
if(root == NULL || root->data == data) {
return root;
}
if(data < root->data) {
return searchNode(root->left, data);
}
else {
return searchNode(root->right, data);
}
}
struct Node* findMinNode(struct Node* node) {
struct Node* current = node;
while(current && current->left != NULL) {
current = current->left;
}
return current;
}
struct Node* deleteNode(struct Node* root, int data) {
if(root == NULL) {
return root;
}
if(data < root->data) {
root->left = deleteNode(root->left, data);
}
else if(data > root->data) {
root->right = deleteNode(root->right, data);
}
else {
if(root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
}
else if(root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}
struct Node* temp = findMinNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
```
`searchNode` 函数用于在二叉排序树中查找指定数据的节点,`findMinNode` 函数用于查找指定节点的子树中最小的节点,`deleteNode` 函数用于在二叉排序树中删除指定数据的节点。
以上是 C 语言实现二叉排序树及其相关操作的代码示例,希望对您有所帮助。
阅读全文