以二叉链表存储结构存储二叉树,统计分支结点及叶子个数。 (1)从键盘输入扩展的先序结点数据,以二叉链表存储该二叉树。 (2)统计叶子结点个数。 (3)统计分支节点个数。 (4)要求程序通过一个主菜单进行控制,通过选择菜单项序号调用各功能函数。

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

#define ERROR 0
#define OK 1

#define FALSE -1
#define TRUE 1
#define maxSize 100


typedef struct node//二叉树数据结构
{
    char data;
    struct Node *LChild;
    struct Node *RChild;
}BiNode,*BiTree;

int menu_select();	//菜单驱动程序
void DeleteBitree(BiTree root);//先序遍历输出二叉树的结点
void CreateBiTree(BiTree * bt);//先序遍历创建二叉树
int leaf(BiTree root);//后续遍历统计叶子结点数目
void PreOrder(BiTree root);//先序遍历输出二叉树的结点

int menu_select()	//菜单驱动程序
{
	int sn;
	printf("实验三运行系统\n");		//显示菜单
	printf("==============================\n");
	printf("1、二叉树的建立\n");
	printf("2、统计叶子结点个数并输出\n");
	printf("3、统计分支结点的个数并输出\n");
	printf("4、输出二叉树中的结点\n");
	printf("0、退出系统\n");
	printf("==============================\n");
	printf("请选择0--4:");

	for(;;)		//菜单功能选择
	{
		scanf("%d",&sn);
		getchar();
		if(sn<0 || sn>4)
			printf("\n\t输入选择错误,请重新选择0--4:");
		else
			break;
	}
	return sn;
}

/*
TODO:创建二叉树
功能描述:编写代码,使之从键盘输入扩展的先序结点数据,建立二叉树,空节点用“.”表示输入
举例:输入AB..C.. 即可建立以A为父节点,BC为子节点的二叉树
参数:定义*bt BiTree类型的指针
*/
void CreateBiTree(BiTree *bt)
{
   char ch;
   scanf("%c",&ch);
   if(ch=='.') *bt=NULL;
   else{
    *bt=(BiTree)malloc(sizeof(BiNode));
    (*bt)->data=ch;
    CreateBiTree(&((*bt)->LChild));
    CreateBiTree(&((*bt)->RChild));
   }
}


void PreOrder(BiTree root)//输出二叉树
{
	if(root != NULL)
	{
		printf("%c",root->data);
		PreOrder( root->LChild);
		PreOrder( root->RChild);
	}
}
void DeleteBitree(BiTree root)//清空二叉树
{
	if(root != NULL)
		return;
	{
		DeleteBitree( root->LChild);
		DeleteBitree( root->RChild);
		free(root);
	}
	return;
}
/*
TODO:统计叶子节点个数
功能描述:后续遍历统计叶子结点数目
参数:root为指向二叉树根结点的指针
返回值:最终返回叶子节点数LeafCount
*/
int leaf(BiTree root)
{
   int count;
   if(root==NULL) count=0;
   else if(root->LChild==NULL&&root->RChild==NULL) count=1;
   else count=leaf(root->LChild)+leaf(root->RChild);
   return count;
}

/*
TODO:统计分支节点个数
功能描述:计算并统计分支节点个数
参数:root为指向二叉树根结点的指针
返回值:最终返回分支节点个数即可
*/
int BranchCount(BiTree root)
{
   if(root==NULL) return 0;
   else{
    if(root->LChild||root->RChild)
        return BranchCount(root->LChild)+1+BranchCount(root->RChild);
    else return 0;
   }
}


void main()
{
	BiTree root,bt;
	int leafcount;
	int branchcount;

	for(;;)	 // 无限循环,选择0 退出
	{
		switch(menu_select())	 // 调用菜单函数,按返回值选择功能函数
		{
			case 1:
				printf("二叉树的建立\n");
                DeleteBitree(&bt);//先序遍历输出二叉树的结点
				CreateBiTree(&bt);//先序遍历创建二叉树
				break;
			case 2:
				printf("统计叶子结点个数并输出\n");
				leafcount=leaf(bt);//后续遍历统计叶子结点数目
		        printf("叶子结点的数目为%d\n",leafcount);
				break;
			case 3:
				printf("统计分支结点个数并输出\n");
				branchcount=BranchCount(bt);
		        printf("分支结点的数目为%d\n",branchcount);
				break;
			case 4:
				printf("输出二叉树中的结点\n");		//输出通讯者信息的函数调用
				PreOrder(bt);//先序遍历输出二叉树的结点
				break;
			case 0:
				printf("再见!\n");				//退出系统
				return;
		} // switch语句结束
	} // for循环结束
} // main()函数结束