实验目的
通过本次实验，掌握二叉树递归处理算法，并会分析该算法的时间复杂度。
实验内容
删除二叉树的子树:假设二叉树中的结点均不相等，采用二叉链存储，设计递归算法删除根结点值为x的子树。
实验过程
1.算法设计
1.首先递归创建一颗二叉树
根据输入的节点值创建二叉树根据用户输入的节点值（#表示空节点），使用递归的方式创建二叉树。
2.查找要删除的子树的根节点
输入要删除的子树的根节点的值，程序在二叉树中查找值为该值的节点，并返回该节点的指针。
3.递归删除子树
对于当前节点，依次递归删除其左子树和右子树中值为子树根节点值的子树。如果当前节点为空或者当前节点的值不等于子树根节点的值，则直接返回当前节点的指针。如果当前节点的左子树或右子树中存在值为子树根节点的节点，则将该节点的左子树或右子树置为空，并释放该节点的空间。
4.输出删除子树后的二叉树
使用中序遍历的方式遍历二叉树，输出删除子树后的节点值序列。
5.输出删除成功，结束程序
程序清单
#include <stdio.h> #include <stdlib.h> #define TYPE char struct biTree { TYPE data; struct biTree *lchild; struct biTree *rchild; }; /** * 释放节点T函数 * @param T */ void del(struct biTree *T) { if (T) { if (T->lchild)del(T->lchild); if (T->rchild)del(T->rchild); free(T); } } /** 这里设置一个父结点指针 因为free只会释放所在结点里面的内容 并不会置空 **/ void delXsub(struct biTree *T, int x) { struct biTree *p = T; if (p->lchild && p->lchild->data == x) { del(p->lchild); p->lchild = NULL; } if (p->rchild && p->rchild->data == x) { del(p->rchild); p->rchild = NULL; } if (p->lchild)delXsub(p->lchild, x); if (p->rchild)delXsub(p->rchild, x); } /** * 递归先序遍历创建二叉树，返回二叉树 * @param T * @return */ struct biTree *create(struct biTree *T) { TYPE data;//当前结点 printf("data="); scanf("%c", &data); getchar(); if (data != '#') { T = (struct biTree *) malloc(sizeof(struct biTree *)); T->data = data; T->lchild = NULL; T->rchild = NULL; T->lchild = create(T->lchild); T->rchild = create(T->rchild); } return T; } /** * 中序遍历二叉树 * @param T */ void inOrder(struct biTree *T) { if (T != NULL) { inOrder(T->lchild); printf("%c", T->data); inOrder(T->rchild); } } int main() { char x; struct biTree *T = (struct biTree *) malloc(sizeof(struct biTree)); //创建一棵二叉树 T = create(T); printf("中序遍历结果为：\n"); inOrder(T); //换行 printf("\n"); printf("请输入您要删除的x的值:x="); scanf("%c", &x); printf("删除后中序遍历结果为：\n"); if (T->data == x) { //调用函数删除 del(T); } else { //再次查找 delXsub(T, x); } inOrder(T); printf("删除结点及其子树成功！"); return true; }
复杂度分析
(1)时间复杂度
O(n)
(2)空间复杂度
O(log2n)
运行结果
结果一
结果二：
