//创建二叉树，先序遍历，删除树中结点为x的子树

include <stdio.h>

include <stdlib.h>

define maxsize 100

typedef struct BTNode
{
char data;
struct BTNode *lchild, rchild;
} BTNode, BTree;
void CreateBTNode(BTree T)
{
char ch;
scanf("%c", &ch);
if (ch == '#')
{
T = NULL;
}
else
{
T = (BTNode )malloc(sizeof(BTNode));
(T)->data = ch;
(T)->lchild = NULL;
(T)->rchild = NULL;
printf("\n建立左子树\n");
CreateBTNode(&(T)->lchild);
printf("\n建立右子树\n");
CreateBTNode(&(T)->rchild);
}
}
void PreOrder_Traverase(BTree T) //先序遍历
{
if (T == NULL)
{
return;
}
else
{
printf(" %c ", T->data);
PreOrder_Traverase(T->lchild);
PreOrder_Traverase(T->rchild);
}
}
BTNode *postDel(BTree T)
{
if (T != NULL)
{
postDel(T->lchild);
postDel(T->rchild);
free(T);
}
return NULL;
}
BTNode *del(BTree T, char x)
{
BTNode *p = NULL;
if (T != NULL)
{
if (T->lchild != NULL && T->lchild->data == x)
{
p = T->lchild;
T->lchild = NULL;
postDel(p);
}
if (T->rchild != NULL && T->rchild->data == x)
{
p = T->rchild;
T->rchild = NULL;
postDel(p);
}
del(T->lchild, x);
del(T->rchild, x);
}
return T;
}
int main()
{
BTree T;
char x;
printf("创建二叉树："); //输入ABC##DE#G##F###
CreateBTNode(&T);
printf("\n先序遍历\n");
PreOrder_Traverase(T);
printf("\n要删除的子树的根节点为：");
scanf(" %c", &x);
del(T, x);
printf("\n删除后：\n");
if (x == T->data)
{
printf("NULL");
}
else
{
PreOrder_Traverase(T);
}
printf("\n");
return 0;
}