#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct node
{
int data;
struct node *lchild, *rchild;
}*Tree, Tnode;

static void CreateTree(Tree *T, int data);
static void DeleteKey(Tree *T, int key);
static void SearchDeleteNode(Tree T, int key, Tree *parPtr, Tree *delPtr);
static void PrintTree(Tree T);

int main(void)
{
Tree T = NULL;

int key;

printf("请输入数列L(输入0结束):\n ");
while (1)
{
scanf("%d", &key);
if (key==0)
{
break;
}

CreateTree(&T, key);
}
printf("中序遍历此二叉排序树为：\n");
PrintTree(T);
putchar('\n');
printf("请输入你要删除的数: ");
scanf("%d", &key);
DeleteKey(&T, key);
PrintTree(T);
putchar('\n');

return 0;
}
static void CreateTree(Tree *T, int key)
{
if (*T == NULL)
{
if (((*T) = (Tree)malloc(sizeof(Tnode))) == NULL)
{
exit(1);
}
(*T) -> data = key;
(*T) -> lchild = (*T) -> rchild = NULL;
}
else
{
if ((*T) -> data > key)
{
CreateTree(&(*T) -> lchild, key);
}
else if ((*T) -> data < key)
{
CreateTree(&(*T) -> rchild, key);
}
}
}
static void PrintTree(Tree T)
{

if (T)
{
PrintTree(T -> lchild);
printf("%d ", T -> data);
PrintTree(T -> rchild);
}
}

static void DeleteKey(Tree *T, int key)
{

Tree parPtr = NULL, delPtr = NULL, tempPtr = NULL;

SearchDeleteNode(*T, key, &parPtr, &delPtr);

if (delPtr == NULL)
{
printf("你输入的结点不存在：无X: \n");
getch();
exit(1);
}

if (parPtr == NULL)
{
if (delPtr -> lchild == NULL)
{
*T = delPtr -> rchild;
}
else
{
*T = delPtr -> lchild;
tempPtr = delPtr -> lchild;
while (tempPtr -> rchild != NULL)
{
tempPtr = tempPtr -> rchild;
}
tempPtr -> rchild = delPtr -> rchild;
}
}
else if (delPtr -> lchild == NULL)
{
if (delPtr == parPtr -> lchild)
{
parPtr -> lchild = delPtr -> rchild;
}
else
{
parPtr -> rchild = delPtr -> rchild;
}
}
else
{
tempPtr = delPtr -> lchild;
while (tempPtr -> rchild != NULL)
{
tempPtr = tempPtr -> rchild;
}
tempPtr -> rchild = delPtr -> rchild;

if (delPtr == parPtr -> lchild)
{
parPtr -> lchild = delPtr -> lchild;
}
else
{
parPtr -> rchild = delPtr -> lchild;
}
}

free(delPtr);
printf("删除该结点之后的二叉树为:\n ");
}

static void SearchDeleteNode(Tree T, int key, Tree *parPtr, Tree *delPtr)
{
*delPtr = T;

if (T -> data == key)
{
return ;
}

while (*delPtr)
{
*parPtr = *delPtr;

if ((*delPtr) -> data > key)
{
*delPtr = (*delPtr) -> lchild;
}
else if ((*delPtr) -> data < key)
{
*delPtr = (*delPtr) -> rchild;
}

if (*delPtr != NULL && (*delPtr) -> data == key)
{
return ;
}
}
}

//修改的别人的程序 没有语法错误了 希望对那些象我这样的初学的人一些帮助