#include<stdio.h>
#include<stdlib.h>
typedef struct tnode
{
char data;
struct tnode *parent;
struct tnode *lchild;
struct tnode *rchild;
}tnode,*bintree;
int NodeNum,leaf;
bintree Tree_creat(bintree t)
{
char ch;
ch=getchar();
if(ch==' ')
t=NULL;
else
{
if(!(t=(bintree)malloc(sizeof(tnode))))
printf("Error!");
t->data=ch;
t->lchild=Tree_creat(t->lchild);
t->rchild=Tree_creat(t->rchild);
}
return t;
}
bintree zTree_creat(bintree t)
{
char ch;
ch=getchar();
if(ch==' ')
t=NULL;
else
{
if(!(t=(bintree)malloc(sizeof(tnode))))
printf("Error!");
t->data=ch;
t->parent=Tree_creat(t->parent);
t->parent->rchild=Tree_creat(t->parent->rchild);
}
return t;
}
bintree hTree_creat(bintree t)
{
char ch;
ch=getchar();
if(ch==' ')
t=NULL;
else
{
if(!(t=(bintree)malloc(sizeof(tnode))))
printf("Error!");
t->lchild=Tree_creat(t->lchild);
t->rchild=Tree_creat(t->rchild);
t->data=ch;
}
return t;
}
void preorder(bintree t)
{
if(t!=NULL)
{
printf("%c ",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
void Inorder(bintree T)
{
if (T) {
Inorder(T->lchild );
printf("%c ",T->data );
Inorder(T->rchild );
}
}
void Postorder(bintree T)
{
if (T) {
Postorder(T->lchild );
Postorder(T->rchild );
printf("%c ",T->data );
}
}
int TreeDepth(bintree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild);
hr=TreeDepth(T->rchild);
max=hl>hr? hl:hr;
NodeNum=NodeNum+1;
if(hl==0&&hr==0) leaf=leaf+1;
return(max+1);
}
else return(0);
}
int BTWidth(bintree T)
{ struct
{ int lno;
bintree p;
}Qu[1000];
int front=0,rear=0;
int lnum,max,i,n;
bintree b;
if(b!=NULL)
{ rear++;
Qu[rear].p=b;
Qu[rear].lno=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;
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;
}
void main()
{
int depth;
bintree t=NULL;
printf("先序建立二叉树:");
//t=Tree_creat(t);
t=zTree_creat(t);
printf("先序遍历序列为:");
preorder(t);
printf("\n中序遍历序列为:");
Inorder(t);
printf("\n后序遍历序列为:");
Postorder(t);
printf("\n树的深度为:");
depth=TreeDepth(t);
printf("%d",depth);
printf("\n结点数为:%d",NodeNum);
printf("\n叶子结点数为:%d",leaf);
printf("\n");
}