编写C语言代码,使代码实现采用二叉链表结构存储一棵二叉树,编写一个算法删除该二叉树中数据值为x的结点及其子树,并且输出被删除的子树的功能。
时间: 2024-12-23 11:24:25 浏览: 2
在C语言中,我们可以创建一个二叉链表节点结构体,并提供插入、查找以及删除节点的方法。下面是一个简单的例子,展示了如何实现这个功能:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉链表节点结构
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} TreeNode;
// 创建新节点
TreeNode* newNode(int data) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入节点
TreeNode* insert(TreeNode* root, int data) {
if (root == NULL) {
return newNode(data);
} else if (data < root->data) {
root->left = insert(root->left, data);
} else {
root->right = insert(root->right, data);
}
return root;
}
// 查找节点
TreeNode* search(TreeNode* root, int data) {
if (root == NULL || root->data == data) {
return root;
} else if (data < root->data) {
return search(root->left, data);
} else {
return search(root->right, data);
}
}
// 删除节点
TreeNode* deleteNode(TreeNode* root, int data) {
if (root == NULL) {
return root;
} else if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
// 情况1: 只有一个子节点
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;
}
// 情况2: 有两个子节点
TreeNode* temp = findMin(root->right); // 找到右子树最小元素
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
// 打印前序遍历
void printPreOrder(TreeNode* node) {
if (node == NULL) {
return;
}
printf("%d ", node->data);
printPreOrder(node->left);
printPreOrder(node->right);
}
// 辅助函数,找到右子树中最小的节点
TreeNode* findMin(TreeNode* node) {
while (node->left != NULL) {
node = node->left;
}
return node;
}
int main() {
TreeNode* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
int key = 30;
root = deleteNode(root, key);
printf("删除了%d节点后的前序遍历结果:\n", key);
printPreOrder(root);
printf("\n");
return 0;
}
```
这个程序首先创建一个二叉搜索树,然后删除指定值(在这个例子中是30),最后打印出删除节点后的前序遍历结果。`deleteNode`函数负责删除节点及其子树。注意,在实际应用中,你可能需要处理更多边界情况,例如删除的是根节点等。
阅读全文