编辑代码

#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
#include<string.h>

#define maxsize 100

//二叉树的基本操作
typedef struct Tree
{
	char data;
	struct tree* lchild;
	struct tree* rchild;
}tree;

//建立二叉数初始化
void inittree(tree* root)
{
	root->data = "";
	root->rchild = NULL;
	root->lchild = NULL;
}

//二叉数的创建
tree* create(tree* root)
{
	char value;
	scanf_s("%c", &value);
	if (value == '#')
	{
		root = NULL;
	}
	else
	{
		root = (tree*)malloc(sizeof(tree));
		root->data = value;
		root->lchild = create(root->lchild);
		root->rchild = create(root->rchild);
	}
	return root;
}

//创建二叉树的结点(二级指针写法)
void createnode(tree** node)
{
	char p_data;
	scanf_s("%c", &p_data);
	if (p_data == '#')
	{
		*node = NULL;
	}
	else
	{
		*node = (tree*)malloc(sizeof(tree));
		(*node)->data = p_data;
		createnode(&((*node)->lchild));
		createnode(&((*node)->rchild));
	}
}

//判断二叉树是否为空
int tempty(tree* root)
{
	if (root->data == "")
	{
		printf("二叉树为空\n");
		return 0;
	}
	else
	{
		printf("二叉树不为空\n");
		return 1;
	}
}

//先序遍历（递归）
void porder(tree* root)
{
	if (root != NULL)
	{
		printf("%c\t", root->data);
		porder(root->lchild);
		porder(root->rchild);
	}
}

//中序遍历（递归）
void morder(tree* root)
{
	if (root != NULL)
	{
		morder(root->lchild);
		printf("%c\t", root->data);
		morder(root->rchild);
	}
}

//后序遍历（递归）
void torder(tree* root)
{
	if (root != NULL)
	{
		torder(root->lchild);
		torder(root->rchild);
		printf("%c\t", root->data);
	}
}

void insertBinarySortTreeNode(Tree *dataNode, Tree **root) //二叉排序树插入节点，因为根节点可能改变，所以传二级指针
{
    if (*root == NULL || dataNode == NULL)
    {
        *root = dataNode;
        return;
    }
    if (dataNode->data > (*root)->data)//如果插入节点大于原节点的data，插入节点需要放在root的右子树
    {
        if ((*root)->right == NULL)//找到插入位置
        {
            (*root)->right = dataNode;
            return;
        }
        if ((*root)->right)
            insertBinarySortTreeNode(dataNode, &(*root)->right);//递归找dataNode的插入位置
    }
    if (dataNode->data <= (*root)->data)//如果去掉等于号，表示不插入相同data的节点
    {
        if ((*root)->left == NULL)//找到插入位置
        {
            (*root)->left = dataNode;
            return;
        }
        if ((*root)->left)
            insertBinarySortTreeNode(dataNode, &(*root)->left); //递归找dataNode的插入位置
    }
}

void Deleteer(tree* root,int key)
{
	Tree *L,*LL;    //在删除左右子树都有的结点时使用；
	Tree *p=root;
	Tree *parent=root;
	int child=0;  //0表示左子树，1表示右子树；
	if(!root)    //如果排序树为空，则退出；
		return ;
	while(p)  //二叉排序树有效；
	{
		if(p->data==key)
		{
			if(!p->lchild&&!p->rchild)  //叶结点(左右子树都为空)；
			{
				if(p==root)  //被删除的结点只有根结点；
					free(p);
				else if(child==0)
				{
					parent->lchild=NULL;  //设置父结点左子树为空；
					free(p);   //释放结点空间；
				}
				else   //父结点为右子树；
				{
					parent->rchild=NULL;  //设置父结点右子树为空；
					free(p);  //释放结点空间；
				}
			}
 
			else if(!p->lchild)  //左子树为空，右子树不为空；
			{
				if(child==0)    //是父结点的左子树；
					parent->lchild=p->rchild;
				else      //是父结点的右子树；
					parent->rchild=p->rchild;
				free(p);  //释放被删除的结点；
			}
 
			else if(!p->rchild)  //右子树为空，左子树不为空；
			{
				if(child==0)  //是父结点的左子树；
					parent->lchild=p->lchild;
				else      //是父结点的右子树；
					parent->rchild=p->lchild;
				free(p);  //释放被删除的结点；
			}
 
			else
			{
				LL=p;  //保存左子树的结点；
				L=p->rchild;  //从当前结点的右子树进行查找；
				if(L->lchild)  //左子树不为空；
				{
					LL=L;
					L=L->lchild;   //查找左子树；
					p->data=L->data;  //将左子树的数据保存到被删除结点；
					LL->lchild=L->lchild;  //设置父结点的左子树指针为空；
					for(;L->lchild;L=L->lchild);
					L->lchild=p->lchild;
					p->lchild=NULL;
				}
				else
				{
					p->data=L->data;
					LL->rchild=L->rchild;
				}
			}
			p=NULL;
		}
 
		else if(key<p->data)  //需删除记录的关键字小于结点的数据；
		{
			//要删除的结点p是parent的左子树；
			child=0;  //标记在当前结点左子树；
			parent=p;//保存当前结点作为父结点；
			p=p->lchild;  //查找左子树；
		}
 
		else  //需删除记录的关键字大于结点的数据；
		{
			//要删除的结点p是parent的右子树；
			child=1;  //标记在当前结点右子树查找；
			parent=p;  //保存当前结点作为父结点；
			p=p->rchild;  //查找右子树；
		}
	}
}


int main()
{
	tree* root = (tree*)malloc(sizeof(tree));
	inittree(root);
	printf("请按先序遍历的次序输入二叉树：\n");
	root = create(root);
	printf("二叉树先序遍历\n");
    porder(root);
    printf("二叉树中序遍历\n");
    morder(root);
	printf("二叉树后序遍历\n");
    torder(root);
    int n;      //插入
    printf("请输入待插入的数据\n");
    scanf("%d",&n);
    dataNode = (tree*)malloc(sizeof(tree));
    inittree(dataNode);
    dataNode->data=n;
    insertBinarySortTreeNode(dataNode, &root);
    printf("插入后的二叉树为：\n");
    porder(root);
    printf("     **将数据5从二叉树中删除**\n\n"); //删除
	printf("删除后的二叉树为:\n");
	Deleteer(root,5);   //删除拥有左右子树的结点有问题；
	porder(root);
	printf("\n");
	return 0;