用顺序和二叉链表作存储结构 1) 以回车('\n')为输入结束标志,输入数列L,生成一棵二叉排序树T; 2) 对二叉排序树T作中序遍历,输出结果; 3) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息“无x”;
时间: 2024-03-17 20:47:39 浏览: 107
好的,我可以帮您解答这个问题。这是一个关于二叉排序树的问题。下面是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct BSTNode {
int data;
struct BSTNode *left;
struct BSTNode *right;
} BSTNode;
// 初始化二叉树
BSTNode* initBST() {
return NULL;
}
// 插入二叉树结点
BSTNode* insertBST(BSTNode *root, int data) {
if (root == NULL) {
root = (BSTNode*)malloc(sizeof(BSTNode));
root->data = data;
root->left = root->right = NULL;
} else {
if (data < root->data)
root->left = insertBST(root->left, data);
else if (data > root->data)
root->right = insertBST(root->right, data);
}
return root;
}
// 中序遍历二叉树
void inorderBST(BSTNode *root) {
if (root != NULL) {
inorderBST(root->left);
printf("%d ", root->data);
inorderBST(root->right);
}
}
// 查找二叉树结点
BSTNode* searchBST(BSTNode *root, int x) {
if (root == NULL || root->data == x)
return root;
else if (x < root->data)
return searchBST(root->left, x);
else
return searchBST(root->right, x);
}
// 删除二叉树结点
BSTNode* deleteBST(BSTNode *root, int x) {
if (root == NULL) {
printf("无%d\n", x);
return NULL;
} else if (x < root->data) {
root->left = deleteBST(root->left, x);
} else if (x > root->data) {
root->right = deleteBST(root->right, x);
} else {
if (root->left == NULL && root->right == NULL) {
free(root);
root = NULL;
} else if (root->left == NULL) {
BSTNode *temp = root;
root = root->right;
free(temp);
} else if (root->right == NULL) {
BSTNode *temp = root;
root = root->left;
free(temp);
} else {
BSTNode *temp = root->right;
while (temp->left != NULL)
temp = temp->left;
root->data = temp->data;
root->right = deleteBST(root->right, temp->data);
}
}
return root;
}
int main() {
BSTNode *root = initBST();
int data;
printf("请输入数列L(以回车为结束标志):\n");
while (scanf("%d", &data) != EOF) {
root = insertBST(root, data);
}
printf("中序遍历结果为:");
inorderBST(root);
printf("\n请输入要删除的元素x:");
scanf("%d", &data);
root = deleteBST(root, data);
printf("删除%d后的中序遍历结果为:", data);
inorderBST(root);
printf("\n");
return 0;
}
```
这段代码实现了输入数列L,生成一棵二叉排序树T,然后对T进行中序遍历,接着输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历。
阅读全文