#include //输入根据根左右建立的二叉树的序列，就可求出，前中后序列，及高度，叶叶子结点及单孩子结点的个数//

//*输入[ab d e ],空白处为空格,即可求出前中后序的遍历，二叉树的高度，叶子结点的个数，及单孩子结点的个数 *//

typedef char DataType;

typedef struct Node /*二叉链表定义结构体*/

{ DataType data;

struct Node *ichild,*rchild;

}Bitree;

void Preorder (Bitree *T)/*前序遍历*/

{ if (T)

{ printf("%c",T->data);

Preorder(T->ichild);

Preorder(T->rchild);

}

}

void Inorder (Bitree *T)/*中序遍历*/

{ if(T)

{ Inorder(T->ichild);

printf("%c",T->data);

Inorder(T->rchild);

}

}

void Postorder(Bitree *T)/*后续遍历*/

{ if(T)

{ Postorder(T->ichild);

Postorder(T->rchild);

printf("%c",T->data);

}

}

Bitree *GreateBitree()/*根左右建立二叉链表*/

{ char ch;

Bitree *t;

ch=getchar();

if(ch==' ') t=NULL;//注意ch=的是单引号//

else

{t=(Bitree*)malloc(sizeof(Bitree));

t->data=ch;

t->ichild=GreateBitree();

t->rchild=GreateBitree();

}

return t;

}

int height(Bitree*T)/*求树的高度*/

{int i,j;

if (!T) return 0;

i=height(T->ichild);

j=height(T->rchild);

return i>j?i+1:j+1;

}

int Degree(Bitree*T) /*叶子节点个数*/

{char i,j;

int n;

if(!T)return 0;

else

{if (T->ichild==NULL&&T->rchild==NULL) return 1;

i=Degree(T->ichild);

j=Degree(T->rchild);

n=i+j;

return n;

}

printf("%d",n);

}

int onechild(Bitree*T)/*度为一的节点数*/

{int num=0,num1,num2;

if(T==NULL) return 0;

else

{if(T->ichild==NULL&&T->rchild!=NULL||T->ichild!=NULL&&T->rchild==NULL) num=1;/*!后的等号是一个等号*/

num1=onechild(T->ichild);

num2=onechild(T->rchild);

return num+num1+num2;

}

}

main()

{

Bitree *T;

printf("\n");

T=GreateBitree();

Inorder(T);

printf("\n");

Postorder(T);

printf("\n");

Preorder(T);

printf("\n");

printf("height is %d\n",height(T));

printf("Degree is %d\n",Degree(T));

printf("onechild is %d\n",onechild(T));

}

基于数据结构 二叉树的建立遍历，树的高度叶子结点数目及单孩子个数-递归求解