二叉树采用链表存储结构，实现建立、遍历（先序、中序、后序）、求结点总数、叶子数、度为1.2的结点数。

前几天写的，输入二叉树的广义表形式，建立二叉树的链式存储。输出的是中序。有注释。例如输入：a(b,c(d,e(f)),g,h(i))
#include
#include
int n=0; //全局变量
struct tree //二叉树结构体
{
char data;
struct tree *lc;
struct tree *rc;
};
tree *creat(char a[]) //创建树的二叉树
{
tree *h;
h=(tree *)malloc(sizeof(tree));
h->lc=NULL;
h->rc=NULL;
if(a[n]!=')'&&a[n]!='('&&a[n]!=',') //当a[n]为字母存入a[]
{
h->data=a[n];
n++;
}
if(a[n]=='(') //a[n]为左括弧对h->lc递归操作
{
n++;
h->lc=creat(a);
}
if(a[n]==',') //a[n]为逗号对h->rc递归操作
{
n++;
h->rc=creat(a);
return h;
}
if(a[n]==')') //a[n]为右括弧返回h
{
n++;
return h;
}
else
return h;

}
void print(tree *h) //二叉树中序输出
{
if(h!=NULL)
{
print(h->lc);
printf("%c",h->data);
print(h->rc);
}

}

int high(char a[]) //判断树的高度
{
int i=0,max=0,p=0;
while(a[i]!=0)
{
if(a[i]=='(')
{
p++;
if(maxmax=p;
}
if(a[i]==')')
p--;
i++;
}
if(p!=0)
{
printf("左右括弧数不等,输入错误\n"); //判断左右括弧数是否相等
exit(1);
}
return max+1;
}
void main() //主函数
{
int i=0;
tree *h;
char a[50]={0};
gets(a);
while(a[i]!=0) //判断各种可能出现的输入错误
{

if(i==0&&(a[i]=='('||a[i]==')'||a[i]==',')) //判断数组首元素是否为字母
{
printf("首节点错误\n");
exit(1);
}
if(a[i]=='(') //左括弧之前一定是字母
{
if(a[i-1]=='('||a[i-1]==')'||a[i-1]==',')
{
printf("输入错误\n");
exit(1);
}
}
if(a[i]!='('&&a[i]!=')'&&a[i]!=',') //两个字母不能在一起
{
if(a[i+1]!='('&&a[i+1]!=')'&&a[i+1]!=',')
{
printf("输入错误,两个字母不能在一起\n");
exit(1);
}
}
i++;
}
h=creat(a); //创建树
printf("该树的高度为:%d\n",high(a));
printf("该二叉树的中序输出为:");
print(h);
printf("\n");
}