88.png

    1. /*
    2.     已知二叉树以二叉链表存储，编写算法完成：对于树中每一个元素值为x的结点，删除以它为根的子树，并释放相应的空间
    3.     分析：
    4.         因为我们要删除以寻找到的元素为根的子树，所以我们删除时应采用递归后序遍历进行删除释放，寻找x采用先序遍历
    5. */
    6. struct biTree {
    7.     char data;
    8.     struct biTree *lchild;
    9.     struct biTree *rchild;
    10. };
    11. #define _CRT_SECURE_NO_WARNINGS
    12. #include <stdio.h>
    13. #include <stdlib.h>
    14. void del(biTree *T) {//释放结点函数
    15.     if (T) {
    16.         if (T->lchild)del(T->lchild);
    17.         if (T->rchild)del(T->rchild);
    18.         free(T);
    19.     }
    21. }
    22. void delXsub(biTree *T, int x) {//这里设置一个父节点指针，因为free只会释放所在节点里面的内容，并不会置空
    23.     struct biTree *p = T;
    24.     if (p->lchild && p->lchild->data == x) {
    25.         del(p->lchild);
    26.         p->lchild = NULL;
    27.     }
    28.     if (p->rchild && p->rchild->data == x) {
    29.         del(p->rchild);
    30.         p->rchild = NULL;
    31.     }
    32.     if (p->lchild) delXsub(p->lchild, x);
    33.     if (p->rchild) delXsub(p->rchild, x);
    36. }
    37. int main() {
    38.     char x;
    39.     struct biTree *T = (struct biTree*)malloc(sizeof(struct biTree));
    40.     biTree *create(biTree *);
    41.     void inOrder(biTree *);
    42.     T = create(T);//创建一颗二叉树
    43.     printf("请输入要寻找的x值：x=");
    44.     scanf("%c", &x);
    45.     if (T->data == x) {
    46.         del(T);
    47.     }
    48.     else {
    49.         delXsub(T, x);
    50.     }
    51.     inOrder(T);
    52.     return 0;
    53. }