#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
typedef struct node{
char data; /*此例中二叉树的结点采用字符类型*/
struct node *lchild,*rchild;
}NODE;
/*按先序遍历序列创建二叉树的二叉链表*/
NODE *crt_bt_pre(){
NODE *bt;
char ch;
flushall();
scanf("%c",&ch);
if(ch == '0')
bt = NULL;
else{
bt = new NODE;
bt -> data = ch;
printf("\n\t请输入%c结点的左孩子：",bt -> data);
bt -> lchild = crt_bt_pre();
printf("\n\t请输入%c结点的右孩子:",bt -> data);
bt -> rchild = crt_bt_pre();
}
return bt;
}
/*先序遍历二叉树*/
void Preorder(NODE *bt){
if (bt != NULL){
printf("%c",bt -> data);
Preorder(bt -> lchild);
Preorder(bt -> rchild);
}
}
/*中序遍历二叉树*/
void Inorder(NODE *bt){
if (bt != NULL){
Inorder(bt -> lchild);
printf("%c",bt -> data);
Inorder(bt -> rchild);
}
}
//后序遍历二叉树
void Postorder(NODE *bt){
if (bt != NULL){
Postorder(bt -> lchild);
Postorder(bt -> rchild);
printf("%c",bt -> data);
}
}
/*统计二叉树中叶子结点的个数*/
int CountLeaf(NODE *bt){
static int count;
if(bt == NULL)
return 0;
else{
if(bt -> lchild == NULL && bt -> rchild == NULL)
count++;
else{
CountLeaf(bt -> lchild);
CountLeaf(bt -> rchild);
}
return(count);
}
}
/*统计二叉树中根结点的总数*/
int CountNode(NODE *bt){
static int count;
if(bt == NULL)
return 0;
else{
count++;
CountNode(bt -> lchild);
CountNode(bt -> rchild);
return(count);
}
}
/*求二叉树的深度*/
int TreeDepth(NODE *bt){
int ldep,rdep;
if(bt == NULL)
return 0;
else{
ldep = TreeDepth(bt -> lchild);
rdep = TreeDepth(bt -> rchild);
if(ldep > rdep)
return(ldep+1);
else
return(rdep+1); //有错误
}
}
//求二叉树的宽度
int TreeWidth(NODE *b)
{
struct
{
int lno;
NODE*p; //节点指针
}Qu[MaxSize]; //定义顺序非循环队列
int front,rear;
int lnum,max,i,n;
front=rear=0; //置队列为空队
if (b!=NULL)
{
rear++;
Qu[rear].p=b; //根节点指针入队
Qu[rear].lno=1; //根节点的层次编号为1
while (rear!=front) //次循环通过层次遍历求每个节点的层次
{
front++;
b=Qu[front].p; //对头出对
lnum=Qu[front].lno;
if (b->lchild!=NULL) //左孩子入队
{
rear++;
Qu[rear].p=b->lchild;
Qu[rear].lno=lnum+1;
}
if (b->rchild!=NULL) //右孩子入队
{
rear++;
Qu[rear].p=b->rchild;
Qu[rear].lno=lnum+1;
}
}
max=0;lnum=1;i=1; //lnum从第一层开始
while (i<=rear) //通过比较相同层次的结点数求树的宽度
{
n=0;
while (i<=rear&&Qu[i].lno==lnum)
{
n++;
i++;
}
lnum=Qu[i].lno;
if (n>max)
{
max=n;
}
}
return max;
}
else
return 0;
}
//int system(const char *string); //自动清屏代码
//char Check()
//{
// printf("是否清屏：Y|N");
// char a;
// scanf("%c",&a);
// if (a=='y'||a=='Y')
// {
// return a;
// }
// else
// return 'N';
//}
//void clear()
//{
// printf("是否清屏（Y|N）:");
// char a;
// scanf("%c",&a);
// if (a=='y'||a=='Y')
// {
// system("pause");
// system("cls");
// }
//}
//菜单函数
void shoumenu(){
printf("\n\n\n");
printf(" --二叉树的基本运算--\n");
printf("*****************************************\n");
printf("* 1------建二叉树 *\n");
printf("* 2------先序遍历 *\n");
printf("* 3------中序遍历 *\n");
printf("* 4------后序遍历 *\n");
printf("* 5------统计叶子数 *\n");
printf("* 6------统计结点数 *\n");
printf("* 7------求二叉树深度 *\n");
printf("* 8------求二叉树宽度 *\n");
printf("* *\n");
printf("* 0------退出 *\n");
printf("*****************************************\n");
printf("请选择菜单号(0--8):");
}
//选择功能函数
void binaryOP(){
NODE *bt = NULL;
int count = 0;
char choice = 'N';
int x;
while(choice != '0'){
shoumenu();
flushall();
scanf("%c",&choice);
switch(choice){
case '1':
printf("\n\t请输入按先序建立二叉树的结点序列：");
printf("\n\t 说明：逐个输入，'0'代表后继结点为空，按回车输入下一个结点");
printf("\n\t请输入根结点：");
bt = crt_bt_pre();/*调用创建二叉树的函数*/
printf("\n\t二叉树成功建立！\n");
//clear();
break;
case '2':
if (bt == NULL){
printf("\n\t空树");
}
else{
printf("\n\t该二叉树的先序遍历的序列为：");
Preorder(bt);/*调用先序遍历函数*/
}
printf("\n");
//clear();
break;
case '3':
if (bt == NULL){
printf("\n\t空树");
}
else{
printf("\n\t该二叉树的中序遍历序列：");
Inorder(bt);/*调用中序遍历函数*/
}
printf("\n");
//clear();
break;
case '4':
if (bt == NULL){
printf("\n\t空树");
}
else{
printf("\n\t该二叉树的后序遍历序列为：");
Postorder(bt);/*调用后序遍历函数*/
}
printf("\n");
//clear();
break;
case '5':
count = CountLeaf(bt);/*调用统计叶子结点个数的函数*/
printf("\n\t该二叉树有%d个叶子结点。\n",count);
printf("\n");
//clear();
break;
case '6':
count = CountNode(bt);/*调用统计结点总数的函数*/
printf("\n\t该二叉树共有%d个结点 \n",count);
printf("\n");
//clear();
break;
case '7':
x = TreeDepth(bt);/*调用求二叉树深度的函数*/
printf("\n\t 该二叉树的深度为%d",x);
printf("\n");
//clear();
break;
case'8':
int n;
n=TreeWidth(bt);
printf("\n\t 该二叉树的宽度为%d\n",n);
//clear();
break;
case '0':
printf("\n\t 程序结束!\n");
printf("\n");
//clear();
break;
default :
printf("\n\t输入有误，请重新输入!\n");
printf("\n");
//clear();
}
}
}
void main()
{
binaryOP();
}