用二叉链表作为二叉排序树的存储结构,实现以下功能: (1)输入一个整数数列,生成一颗二叉排序树。 (2)在二叉排序树中查找元素。 (3)在二叉排序树种插入元素。 (4)在二叉排序树中删除元素。 (5)对二叉排序树进行中序遍历,输出结果。
时间: 2024-01-06 22:25:56 浏览: 136
使用链表存储二叉排序树并实现遍历算法(完全可用版)
要实现以上功能,可以按照以下步骤进行:
(1)输入一个整数数列,生成一颗二叉排序树:
首先,定义一个二叉树的结构体,包含一个整数数据和左右子树指针。然后,遍历整数数列,依次将每个整数插入到二叉排序树中。
(2)在二叉排序树中查找元素:
从根节点开始,比较要查找的元素与当前节点的值。如果相等,则找到了;如果要查找的元素小于当前节点的值,则在左子树中继续查找;如果要查找的元素大于当前节点的值,则在右子树中继续查找。直到找到要查找的元素或者遍历到叶子节点为止。
(3)在二叉排序树中插入元素:
从根节点开始,比较要插入的元素与当前节点的值。如果要插入的元素小于当前节点的值,并且当前节点的左子树为空,则将要插入的元素作为当前节点的左子树;如果要插入的元素大于当前节点的值,并且当前节点的右子树为空,则将要插入的元素作为当前节点的右子树。如果要插入的元素与当前节点的值相等,则不进行插入操作。如果要插入的元素与当前节点的值不相等,并且左子树或右子树不为空,则继续在左子树或右子树中进行插入操作。
(4)在二叉排序树中删除元素:
首先,找到要删除的元素所在的节点。如果要删除的元素小于当前节点的值,则在左子树中继续查找;如果要删除的元素大于当前节点的值,则在右子树中继续查找。如果找到了要删除的元素所在的节点,则根据节点的情况进行删除操作:
- 如果要删除的节点是叶子节点,则直接删除该节点。
- 如果要删除的节点只有左子树或右子树,则将该节点的左子树或右子树连接到其父节点上。
- 如果要删除的节点既有左子树又有右子树,则找到该节点的右子树中的最小节点(即右子树中的最左节点),将其值替换到要删除的节点上,然后删除该最小节点。
(5)对二叉排序树进行中序遍历,输出结果:
中序遍历二叉排序树的顺序是先遍历左子树,然后访问根节点,最后遍历右子树。可以使用递归或者栈来实现中序遍历。
下面是一个示例代码,实现了以上功能:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 插入元素到二叉排序树
void insert(TreeNode** root, int value) {
if (*root == NULL) {
*root = (TreeNode*)malloc(sizeof(TreeNode));
(*root)->data = value;
(*root)->left = NULL;
(*root)->right = NULL;
} else {
if (value < (*root)->data) {
insert(&((*root)->left), value);
} else if (value > (*root)->data) {
insert(&((*root)->right), value);
}
}
}
// 查找元素在二叉排序树中的位置
TreeNode* search(TreeNode* root, int value) {
if (root == NULL || root->data == value) {
return root;
}
if (value < root->data) {
return search(root->left, value);
} else {
return search(root->right, value);
}
}
// 删除二叉排序树中的节点
TreeNode* delete(TreeNode* 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) {
TreeNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
TreeNode* temp = root->left;
free(root);
return temp;
}
TreeNode* temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->data = temp->data;
root->right = delete(root->right, temp->data);
}
return root;
}
// 中序遍历二叉排序树
void inorderTraversal(TreeNode* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main() {
TreeNode* root = NULL;
// 输入一个整数数列,生成一颗二叉排序树
int nums[] = {5, 3, 8, 2, 4, 7, 9};
int size = sizeof(nums) / sizeof(nums[0]);
for (int i = 0; i < size; i++) {
insert(&root, nums[i]);
}
// 在二叉排序树中查找元素
int target = 4;
TreeNode* result = search(root, target);
if (result != NULL) {
printf("找到了元素 %d\n", target);
} else {
printf("未找到元素 %d\n", target);
}
// 在二叉排序树中插入元素
int insertValue = 6;
insert(&root, insertValue);
// 在二叉排序树中删除元素
int deleteValue = 3;
root = delete(root, deleteValue);
// 对二叉排序树进行中序遍历,输出结果
printf("中序遍历结果:");
inorderTraversal(root);
printf("\n");
return 0;
}
```
希望对你有帮助!如果有任何疑问,请随时提问。
阅读全文