C语言 (链式存储) 建立二叉树 求二叉树的(单双总)结点个数 按前序遍历打印叶子结点 删除以值X为根结点的子树 找到以值X为结点求二叉树中结点X的双亲

C语言// (链式存储) 建立二叉树// 求二叉树的(单/双/总)结点个数// 按前序遍历打印叶子结点// 删除以值X为根结点的子树// 找到以值X为结点//求二叉树中结点X的双亲

//日常记录 C语言  （二叉树 链式存储） 
// 建立二叉树 
// 求二叉树的(单/双/总)结点个数 
// 按前序遍历打印二叉树的叶子结点 
// 在二叉树中删除以值X为根结点的子树 
// 在二叉树中找到以值X为结点 
// 求二叉树中结点X的双亲 
#include
#include
#include
typedef int DataType; 
typedef struct BiNode             
{
	struct BiNode * lchild , * rchild;   
	DataType  data;
 } BiNOde ; 
BiNode * Creat()                                        //建立二叉树 
{
	char ch;
	BiNode * S;
	scanf("%c",&ch);     
	int temp = getchar();
	if(ch == '0' )       //无孩子用0插入 
	{
		return NULL;
	}
	else 
	{
		S = (BiNode *)malloc(sizeof(BiNode));
		S->data = ch;
		printf("请输出%c节点的左孩子n",ch); 
		S->lchild = Creat();
		printf("请输出%c节点的右孩子n",ch); 
		S->rchild = Creat();
		return S; 
	}
}

int All(BiNode * S)                                     //求总结点个数 
{
	if(S == NULL)
	{
		return 0;
	}
	else 
	{
		return All(S->lchild) + All(S -> rchild) +1 ; 
	}
}

int Single( BiNode * S)                                 //求单结点个数 
{
	if(S==NULL)
	{
		return 0;
	}
	else if((S->lchild!=NULL&&S->rchild==NULL)||(S->lchild==NULL&&S->rchild!=NULL))
	{
		return Single(S->lchild)+Single(S->rchild)+1;
	}
	else 
	{
		return Single(S->lchild)+Single(S->rchild);
	}
}

int  Twin(BiNode * S)                                    //求双结点个数 
{
	if(S == NULL)
	{
		return 0;
	}
	else if((S->lchild!=NULL&&S->rchild!=NULL))
	{
		return Twin(S->lchild)+Twin(S->rchild)+1;
	}
	else 
	{
		return Twin(S->lchild)+Twin(S->rchild);
	}
}

int  PreOrder(BiNode * S)                                //前序遍历打印二叉树的叶子结点 
{
	if(S == NULL)
	{
		return 0; 
	}
	else 
	{
		if(S->lchild==NULL&&S->rchild==NULL)
		{
			printf("%c ",S->data);
		}
		PreOrder(S->lchild);
		PreOrder(S->rchild);
	}
 } 
char DeleteX(BiNode * S, char X)                       //删除以值x为根结点的子树(假设只有一个) 
{
	if(S==NULL)
	{
		return 0;
	}
	else
	{
		if( S->lchild!=NULL)
		{
			if(S->lchild->data==X) 
			{
				S->lchild =NULL;
			}
		}
		if( S->rchild!=NULL)
		{
			if(S->rchild->data==X) 
			{
				S->rchild=NULL;
			}
		}
		DeleteX(S->lchild,X);
		DeleteX(S->rchild,X);
	}
}
//char DeleteX(BiNode * S, int X)                     //此算法把根节点值置为NULL 以NULL可以做判断其他                     
//{
//	if(S==NULL )
//	{
//		return 0;
//	} 
//	 else 
//	 {
//	 	if(S->data == X)
//	 	{
//	 		printf("删除成功n");
//	 		S->lchild = NULL;
//			S->rchild = NULL;
//			S->data = NULL;
//			return 1;
//		 }
//		 else 
//		 {
//		 	DeleteX(S->lchild,X);
//			DeleteX(S->rchild,X); 
//		 }
//	 }
//}
int flag = 0;
char Validation(BiNode *S ,char X)                         //验证删除X算法的正确性(通过查找，非遍历) 
{
	 if(S == NULL)
	 {
		return 0; 
	 }
 	else
	 {
	 	if(S->data == X )
	 	{
 			printf("删除失败%c结点还存在n",S->data);
 			flag =1;
 		}
	 	Validation(S->lchild,X);
		Validation(S->rchild,X);
		return 1;
	 }
} 
 
char FindParent(BiNode * S, char X)
{
	if(S==NULL)
	{
		return 0;
	}
	else
	{
		if( S->lchild!=NULL)
		{
			if(S->lchild->data==X) 
			{
			printf("该节点的双亲结点为:%c",S->data);
			exit(1);
			}
		}
		if( S->rchild!=NULL)
		{
			if(S->rchild->data==X) 
			{
			printf("该节点的双亲结点为:%c",S->data);
			exit(1);
			}
		}
		FindParent(S->lchild,X);
		FindParent(S->rchild,X);
	}
}
int  Pre(BiNode * S)                                //前序遍历
{
	if(S == NULL)
	{
		return 0; 
	}
	else 
	{
		printf("%c ",S->data);
		Pre(S->lchild);
		Pre(S->rchild);
	}
 } 	
int main ()
{
	BiNode * S;
	printf("现在开始建立二叉树，所有算法皆基于此结构，请输入第一个结点：n");
//建立二叉树 
	S = Creat();
//求二叉树的(单/双/总)结点个数 
	int ALL = All(S);
	int DAN = Single(S);
	int SHUANG = Twin(S);
	printf("总结点数目为%d n",ALL);
	printf("单结点数目为%d n",DAN);
	printf("双结点数目为%d n",SHUANG);
	printf("前序遍历叶子节点：");
按前序遍历打印二叉树的叶子结点 
	PreOrder(S);
//在二叉树中删除以值X为根结点的子树 
	while(getchar()!='n')   continue; 
	printf("现在请输入需要删除的根节点n");
	char ch1;
	scanf("%c",&ch1);
	DeleteX(S,ch1);
//判断在二叉树中是否可以找到以值X为根结点 输出 0/1(验证上算法的正确性）	
	while(getchar()!='n')   continue; 	
	printf("请输入想要查找的结点已验证是否删除n");
	char ch2;
	scanf("%c",&ch2);
	Validation(S,ch2);
	if(flag==0)  printf("已删除") ; 
//求二叉树中结点X的双亲	
	while(getchar()!='n')   continue; 
	printf("n现在请输入需要查找双亲节点的结点n可以输入的结点有：");
	Pre(S);
	printf("n") ;
	char ch3;
	scanf("%c",&ch3);
	FindParent(S,ch3) ;	
}

//测试
//树的结构         a
//			    b   c
//			       d e
// 
//输入  a b 0 0 c d 0 0 e 0 0  
//输出： 
//现在开始建立二叉树，所有算法皆基于此结构，请输入第一个结点：
//a
//请输出a节点的左孩子
//b
//请输出b节点的左孩子
//0
//请输出b节点的右孩子
//0
//请输出a节点的右孩子
//c
//请输出c节点的左孩子
//d
//请输出d节点的左孩子
//0
//请输出d节点的右孩子
//0
//请输出c节点的右孩子
//e
//请输出e节点的左孩子
//0
//请输出e节点的右孩子
//0
//总结点数目为5
//单结点数目为0
//双结点数目为2
//前序遍历叶子节点：b d e
//现在请输入需要删除的根节点
//c
//请输入想要查找的结点已验证是否删除
//c
//已删除
//现在请输入需要查找双亲节点的结点
//可以输入的结点有：a b
//b
//该节点的双亲结点为:a
//--------------------------------