#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxsize 100;
#define maxwidth 40;
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *lchild,*rchild;
}bitreenode,*bitree;
//bitree *root;
bitree Create(bitree p) //建立二叉树
{
char ch;
ch=getchar();
if(ch=='#')
p=NULL;
else
{
if(!(p=(bitreenode *)malloc(sizeof(bitreenode))))
printf("Error!");
p->data=ch;
p->lchild=Create(p->lchild);
p->rchild=Create(p->rchild);
}
return p;
}
void preorder(bitree p) //先序遍历
{
if(p!=NULL)
{
printf("%c",p->data);
preorder(p->lchild);
preorder(p->rchild);
}
}
void inorder(bitree p) //中序遍历
{
if(p!=NULL)
{
inorder(p->lchild);
printf("%c",p->data);
inorder(p->rchild);
}
}
void postorder(bitree p) //后序遍历
{
if(p!=NULL)
{
postorder(p->lchild);
postorder(p->rchild);
printf("%c",p->data);
}
}
void printree(bitree p) //输出
{
if(p!=NULL)
{
printf("%c",p->data);
if(p->lchild!=NULL || p->rchild!=NULL)
{
printf("(");
printree(p->lchild);
if(p->rchild!=NULL)
printf(",");
printree(p->rchild);
printf(")");
}
}
}
int Depth(bitree p) //计算深度
{
int depl,depr;
if(p=NULL)
return(0);
else
{
depl=Depth(p->lchild);
depr=Depth(p->rchild);
if(depl>depr)
return (depl+1);
else
return (depr+1);
}
}
int jd(bitree p) //计算结点数
{
if(p==NULL)
return (0);
else
return (jd(p->lchild)+jd(p->rchild)+1);
}
int yzjd(bitree p) //计算叶子节点数
{
if(p==NULL)
return (0);
else if(p->lchild==NULL && p->rchild==NULL)
return (0);
else
return(yzjd(p->lchild)+yzjd(p->rchild));
}
int fyzjd(bitree p) //计算非叶子结点数
{
if(p==NULL)
return (0);
else if(p->lchild==NULL && p->rchild==NULL)
return (0);
else
return(fyzjd(p->lchild)+fyzjd(p->rchild)+1);
}
int onechild(bitree p) //计算单孩子数
{
if(p==NULL)
return(0);
else if ((p->lchild==NULL && p->rchild!=NULL) || (p->lchild!=NULL && p->rchild==NULL))
return (onechild(p->lchild)+onechild(p->rchild)+1);
else
return (onechild(p->lchild)+onechild(p->rchild));
}
int twochild(bitree p) //计算双孩子数
{
if(p==NULL)
return(0);
else if ( p->lchild==NULL || p->rchild==NULL)
return(twochild(p->lchild)+twochild(p->rchild));
else if(p->lchild!=NULL && p->rchild!=NULL)
return(twochild(p->lchild)+twochild(p->rchild)+1);
return 0;
}
void main() //主函数
{
bitree p;
p="A(B(D(F,G),E(H)),C)";
p=Create(p);
printf("\n先序遍历:");
preorder(p);
printf("\n中序遍历:");
inorder(p);
printf("\n后序遍历:");
postorder(p);
printf("\n");
printf("二叉树括号表示:");
printree(p);
printf("\n二叉树深度:%d\n",Depth(p));
printf("总结点个数:%d\n",jd(p));
printf("叶子结点数:%d\n",yzjd(p));
printf("非叶子结点数:%d\n",fyzjd(p));
printf("双孩子结点个数:%d\n",twochild(p));
printf("单孩子结点个数:%d\n",onechild(p));
}
warning C4133: '=' : incompatible types - from 'char [20]' to 'struct node *'