//关于二叉树的相关操作
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
typedef struct _tree
{
char data;
struct _tree *lchild;
struct _tree *rchild;
int ltag;//用于二叉树的线索化;
int rtag;//用于二叉树的线索化;
}*ptree,treenode;
static int t=0;
int Insert(ptree *bt,char k)//二叉排序树中的插入算法
{
ptree f,p=(*bt);//p指针是用于遍历二叉树中的结点,f用于指向当前结点的前驱结点
while(p!=NULL)
{
if(p->data==k)
{
return 0;
}
f=p;
if(p->data>k)
{
p=p->lchild;
}
else
{
p=p->rchild;
}
}
p=(ptree)malloc(sizeof(treenode));
p->data=k;
p->lchild=p->rchild=NULL;
p->ltag=p->rtag=0;
if((*bt)==NULL)
{
(*bt)=p;//若原来的二叉树为空树,则根结点bt就指向当前的新加入的结点
}
else if(k<f->data)
f->lchild=p;
else
f->rchild=p;
return 1;
}
void create(ptree *bt,char *tm)//创建二叉排序树
{
(*bt)=NULL;//一开始让二叉树的根结点指针指向NULL
char tmp;
int i=0;
tmp=tm[i];//取首个结点
while(tmp)
{
Insert(bt,tmp);//插入新结点
tmp=tm[++i];//去下一个结点
}
}
//先序遍历
void preorder(ptree bt)
{
if(bt)
{
printf("%c ",bt->data);
preorder(bt->lchild);
preorder(bt->rchild);
}
}
//中序遍历
void inorder(ptree bt)
{
if(bt)
{
inorder(bt->lchild);
printf("%c ",bt->data);
inorder(bt->rchild);
}
}
//后序遍历
void postorder(ptree bt)
{
if(bt)
{
postorder(bt->lchild);
postorder(bt->rchild);
printf("%c ",bt->data);
}
}
//计算二叉树中的所有结点个数(其实这个功能先序，中序，后序遍历均可做到)
int NodeCount(ptree bt)
{
int num1=0,num2=0;//这一块不初始化也是可以的，最终num1,num2的零值是由return 0赋予的
if(bt==NULL)
return 0;
else
{
num1=NodeCount(bt->lchild);//计算左子树的结点个数
num2=NodeCount(bt->rchild);//计算右子树的结点个数
return num1+num2+1;//加的一是指加上根结点
}
}
//求二叉树中的叶子个数
int leafcount(ptree bt)
{
int num1=0,num2=0;
if(bt==NULL)
{
return 0;
}
else if(!bt->lchild&&!bt->rchild)
{
return 1;//是叶子结点则返回1
}
else
{
num1=leafcount(bt->lchild);
num2=leafcount(bt->rchild);
return num1+num2;
}
}
//中序求度为2的结点个数，求出的值加一即是叶子结点的个数(先序，后序也都可以)
void leafcount1(ptree bt)
{
int num1=0,num2=0;
if(bt==NULL)
return ;
else
{
leafcount1(bt->lchild);
if(bt->lchild&&bt->rchild)//左右孩子都存在，表明结点的度是二
{
t++;
}
leafcount1(bt->rchild);
}
}
//求二叉树高度的算法
int highcount(ptree bt)
{
int num1=0,num2=0;
if(bt==NULL)
return 0;
else
{
num1=highcount(bt->lchild);
num2=highcount(bt->rchild);
return (num1>num2)? (num1+1):(num2+1);//比较左右子树的高度值，取最大的并加一(加一是因为根结点的缘故)
}
}
//括号输出法
void disptree(ptree bt)
{
if(bt)
{
printf("%c",bt->data);
if(bt->lchild!=NULL||bt->rchild!=NULL)
{
printf("(");//如果当前结点存在左孩子或右孩子，则输出左括号
disptree(bt->lchild);//递归处理左子树
if(bt->rchild!=NULL)
printf(",");//如果右孩子结点存在，则输出","
disptree(bt->rchild);//递归处理右子树
printf(")");
}
}
}
//求二叉树的宽度
void levelnum(ptree bt,int *a,int h)//用于求出每一层的宽度
{
if(bt==NULL)
return;
else
{
a[h]+=1;//a[h]用于记录每一层的高度
levelnum(bt->lchild,a,h+1);
levelnum(bt->rchild,a,h+1);
}
}
int treewidth(ptree bt)
{
int h=1,wid=0;
int tmp=highcount(bt);//得出层数，也就是高度
int *a=(int *)malloc(sizeof(int)*(tmp+1));
for(int i=0;i<tmp+1;i++)
a[i]=0;
levelnum(bt,a,h);
for(int j=1;j<tmp+1;j++)
{
if(a[j]>wid)//比较出最大的宽度
wid=a[j];
}
return wid;
}
int main()
{
ptree *bt;
bt=(ptree *)malloc(sizeof(ptree));//这一句千万不要忘了,二级指针指向存储一级指针变量的空间
printf("请输入长度不超过1000的字符串!\n");
char tm[1001];//字符串的长度不超过1000
gets(tm);//接收自控制台输入的字符串
create(bt,tm);
printf("输出先序遍历序列:\n");
preorder(*bt);
printf("\n");
printf("输出中序遍历序列:\n");
inorder(*bt);
printf("\n");
printf("输出后序遍历序列:\n");
postorder(*bt);
printf("\n");
printf("括号输入序列:\n");
disptree(*bt);
printf("\n");
printf("总结点的个数是:%d\n",NodeCount(*bt));
printf("二叉树中的叶子个数:%d\n",leafcount(*bt));
leafcount1(*bt);
printf("二叉树中度为2的结点个数:%d\n",t);
printf("二叉树的高度为:%d\n",highcount(*bt));
printf("二叉树的最大宽度为:%d\n",treewidth(*bt));
return 0;
}