设T是一棵给定的数,试用C语言编写一个在数T中删除结点值为a的子树的程序,这里假设树T中的结点采用二叉链表存储结构
时间: 2023-07-15 07:13:22 浏览: 76
c++实现在二叉检索树中删除一个结点的算法
5星 · 资源好评率100%
以下是一个基于二叉链表存储结构的删除子树的C语言程序:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
Node* deleteSubtree(Node* root, int a) {
if (root == NULL) {
return NULL;
}
if (root->data == a) {
free(root);
return NULL;
}
root->left = deleteSubtree(root->left, a);
root->right = deleteSubtree(root->right, a);
return root;
}
int main() {
Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
printf("Original tree:\n");
printf("%d\n", root->data);
printf("%d %d\n", root->left->data, root->right->data);
printf("%d %d %d %d\n", root->left->left->data, root->left->right->data, root->right->left->data, root->right->right->data);
int a = 2;
root = deleteSubtree(root, a);
printf("Tree after deleting subtree rooted at %d:\n", a);
printf("%d\n", root->data);
printf("%d %d\n", root->left->data, root->right->data);
printf("NULL %d %d %d\n", root->left->right->data, root->right->left->data, root->right->right->data);
return 0;
}
```
在这个程序中,首先定义了一个Node结构体,用于表示树中的节点。然后定义了一个createNode函数,用于创建一个包含指定数据的节点。接下来,定义了一个deleteSubtree函数,它使用递归算法从根节点开始遍历整个树。如果当前节点的值等于a,则将该节点释放并返回NULL,表示删除了该节点及其子树。否则,递归地调用deleteSubtree函数来删除当前节点的左子树和右子树中值为a的子树。最后,程序通过调用deleteSubtree函数来删除树中值为2的子树。运行程序后,输出如下:
```
Original tree:
1
2 3
4 5 6 7
Tree after deleting subtree rooted at 2:
1
NULL 3
NULL 5 6 7
```
可以看到,程序成功地删除了树中以2为根节点的子树。
阅读全文