编辑代码

/****************   第6.3.4节 遍历算法的应用（135页） ****/
/*********** 算法6.8 计算一棵二叉树的叶子结点数目（135页）**********
		            利用中序遍历算法计算叶子结点数目
************************************************************/
#include <stdlib.h>
#include <stdio.h>
#define maxsize  100
typedef char datatype;

//二叉树的二叉链表存储表示
typedef struct node {
	datatype data;						//结点数据域
	struct node *lchild, *rchild;	//左右孩子指针
} bitree;

//用先序遍历的顺序建立二叉链表
bitree *CreateBiTree( ) {
//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
	bitree *T = NULL;
	char ch;
	ch = getchar( );
	if (ch != '@') {
		T = (bitree *)malloc(sizeof(bitree));
		T->data = ch;					//生成根结点
		T->lchild = CreateBiTree();	//递归创建左子树
		T->rchild = CreateBiTree();	//递归创建右子树
	} else {
		T = NULL;			//递归结束，建空树
	}
	return T;
}

int count = 0;  // 通过全局量传递叶子结点的数目


/****** 算法6.8 计算一棵二叉树的叶子结点数目（135页）**********
***************************************************************/
int countleaf(bitree *p) {
	if (p != NULL) {
		count =	countleaf(p->lchild); //对左子树上的叶子结点计数
		if (p->lchild == NULL && p->rchild == NULL) {
			count = count + 1;
			printf("%c", p->data);
		}
		count = countleaf(p->rchild);//对右子树上的叶子结点计数
	}
	return count;
}

int main() {
	bitree *p;
	printf("建立树，按先序遍历序列输入结点\n");
	printf("空结点为@，结束按回车\n");
	p = CreateBiTree( );
	printf("叶子结点为: ");
	countleaf(p);
	printf("\n叶子结点数目为:%d\n ", count);

	return 0;
}

//测试样例1 (教材第131页图6.10中的二叉树，先序遍历输入结点)
// 输入结点  ABD@@E@G@@C@FH@@@

//测试样例2 (教材第134页图6.11，先序遍历输入结点))
// 输入结点  ABH@@FD@@@E@CK@@G@@