请用C语言编写一个算法,删除二叉树中所有以值x为根的子树,并释放相应的空间。二叉树采用二叉链表方式存储。二叉树的存储采用biTree.c中的结构完成,运行结果可随机
时间: 2024-01-24 11:16:51 浏览: 112
以下是用C语言编写的算法,删除二叉树中所有以值x为根的子树,并释放相应的空间:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct BiNode {
int data;
struct BiNode *left;
struct BiNode *right;
} BiNode, *BiTree;
void createBiTree(BiTree *T) {
int data;
scanf("%d", &data);
if (data == -1) {
*T = NULL;
} else {
*T = (BiNode*)malloc(sizeof(BiNode));
(*T)->data = data;
createBiTree(&((*T)->left));
createBiTree(&((*T)->right));
}
}
void deleteSubTree(BiTree *T, int x) {
if (*T == NULL) {
return;
}
if ((*T)->data == x) {
free(*T);
*T = NULL;
return;
}
deleteSubTree(&((*T)->left), x);
deleteSubTree(&((*T)->right), x);
if ((*T)->left == NULL && (*T)->right == NULL) {
free(*T);
*T = NULL;
}
}
void inorderTraversal(BiTree T) {
if (T == NULL) {
return;
}
inorderTraversal(T->left);
printf("%d ", T->data);
inorderTraversal(T->right);
}
int main() {
BiTree T;
int x;
printf("请输入二叉树的先序遍历序列:\n");
createBiTree(&T);
printf("请输入要删除的子树的根节点值:\n");
scanf("%d", &x);
deleteSubTree(&T, x);
printf("删除后的二叉树中序遍历序列为:\n");
inorderTraversal(T);
return 0;
}
```
其中,`createBiTree`函数用于创建二叉树,`deleteSubTree`函数用于删除以值x为根的子树,`inorderTraversal`函数用于中序遍历二叉树。运行程序后,先输入二叉树的先序遍历序列,然后输入要删除的子树的根节点值,最后输出删除后的二叉树中序遍历序列。
阅读全文