叶子与结点.cpp

以二叉链表为存储结构,分别写出求二叉树结点和叶子总数的算法

#define max 30
#define NULL 0
#include<stdio.h>
#include<stdlib.h>

typedef struct btnode
{
	char data;
	struct btnode *lchild,*rchild;
}bttree;
bttree *cre_tree(char *str,int i,int m)
{
	bttree *p;
	if(i>=m)
		return NULL;
	p=(bttree *)malloc (sizeof(bttree));
	p->data=str[i];
	p->lchild=cre_tree(str,2*i+1,m);
    p->rchild=cre_tree(str,2*i+1,m);
	return p;
}
void preorder(bttree *t)  //先序
{
	if(t)
	{
		printf("%c",t->data);
		if(t->lchild)
		{
			printf("->");
			preorder(t->lchild);
		}
			if(t->rchild)
		{
			printf("->");
			preorder(t->rchild);
		}
	}
}
//求结点数与叶子数
void inordercount(bttree *p)
{
	int countnode=0;
    int countleaf=0;
	if(p)
	{
		countnode++;
		inordercount(p->lchild);
		printf("%d",p->data);
		 
		if(p->lchild==NULL&&p->rchild==NULL)
			countleaf++;
            inordercount(p->rchild);
	}
}

void main()
{  	int countnode=0;
    int countleaf=0;
	int i,n;
	char str[max];
	bttree *root;
	printf("请输入一颗树的结点长度:\n");
	scanf("%d",&n);
	getchar();
	printf("请输入字符串,长度为:%d\n",n);
	for(i=0;i<n;i++)
		str[i]=getchar();
	printf("\n");
	root=cre_tree(str,0,n);
	printf("树正被建立\n");
	printf("先序后的遍历是:\n");
	preorder(root);
	printf("\n");
    inordercount(root);
	printf("\n 结点数为：%d叶子点数为:%d",countnode,countleaf);
}