#include
#include
typedef struct BiTNode
{
char data;//节点数据
struct BiTNode * lchild;//左孩子
struct BiTNode * rchild;//右孩子
}BiTNode, * BiTree;
int CreateBiTree(BiTree T)/*先序构造二叉树*/
{
char ch;
scanf("%c",&ch);
if(ch=='#')
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
if(T==NULL)
{
printf("节点动态分配失败");
return 0;
}
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return 1;
}
int InOrderTraveler( BiTree T )
{
if( NULL!= T )
{
printf( "%c", T -> data );
InOrderTraveler( T -> lchild );
InOrderTraveler( T -> rchild );
}
return 1;
}
int leafcount(BiTree T)/*叶子结点个数*/
{
static int LeafCount= 0;
if(T!=NULL)
{
leafcount(T->lchild);
leafcount(T->rchild);
if(T->lchild==NULL&&T->rchild==NULL)
LeafCount++;
}
return LeafCount;
}
int PostTreeDepth(BiTree T)
{
int hl,hr,max,depth;
if(T!=NULL)
{
hl=PostTreeDepth(T->lchild);/*求左子树深度*/
hr=PostTreeDepth(T->rchild);/*求右子树深度*/
max=hl>hr?hl:hr;/*得到左,右子树深度较大者*/
depth=max+1;
return(depth);/*返回树的深度*/
}
else return 0;/*如果是空树,则返回0*/
}
int BinTreeNodeCount(BiTNode T )/统计结点个数*/
{
int N, num1, num2;
if( T==NULL )
{
return 0;
}
else
{
num1 = BinTreeNodeCount( T->lchild );/*统计左子树节点个数*/
num2 = BinTreeNodeCount( T->rchild );/*统计右子树节点个数*/
N = num1 + num2 + 1;
printf("%d",N);
return N;
}
}
int countDegreeTwo(BiTNode T)/统计度为2的结点个数*/
{
if (T == NULL)
return 0;
if (T->lchild != NULL&& T->rchild != NULL)
return 1 + countDegreeTwo(T->lchild) + countDegreeTwo(T->rchild);
return countDegreeTwo(T->lchild) + countDegreeTwo(T->rchild);
}
int main()
{
BiTree T=NULL;
printf("按先序顺序输入第一个二叉树:");
CreateBiTree(T);
printf("%d",leafcount(T));
printf("%d",BinTreeNodeCount(T));
printf("%d",countDegreeTwo(T));
InOrderTraveler(T);
return 1;
}