欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

7-3 求二叉树的叶子结点个数 (20分)

程序员文章站 2024-01-17 18:20:46
...

7-3 求二叉树的叶子结点个数 (20分)
分析:
题目关键在于怎样创建一棵树,具体的思路就是和先序遍历一样,先根结点,再左孩子,最后右孩子,无非就是遍历的时候是Pretravelse(BinTree T),而创建树的时候是Create(BinTree T)
(这是递归的抽象思维,你就把它抽象的总结出来,具体的遍历步骤,等代码写出来再去具体一条条走)
创建树:由于是先序序列输入,那么第一个输入的肯定为根结点,然后一直向左延伸,当输入碰到 # 时,左边(即左分支)搞定了,然后向右向右延伸,直到碰到 # 时,右边(即右分支)搞定。
至于叶子结点可通过先序遍历,当碰到左右孩子都为NULL时,count++来统计。或者用层序遍历来统计,层序遍历的话要用队列,第一个结点(根结点)先入队,然后设一个循环(当队列为空时结束),循环内语句为如果结点左孩子不为NULL则入队,否则为NULL的话设置标记flag为1(flag原先为0),如果右孩子不为NULL则入队,否则为NULL的话,如果flag为1的话则count++,flag等于0。(在这里只给出先序递归的代码,层序只提供思路,抱歉!)
具体代码:

# include <stdio.h>
# include <stdlib.h>
struct Node{
	char data;
	struct Node* left;
	struct Node* right;
};
typedef struct Node* BinTree;
BinTree Create()
{
	BinTree T;
	char x;
	scanf("%c",&x);
	if(x=='#') return NULL;
	else {
		T=(BinTree)malloc(sizeof(struct Node));
		T->data=x;
		T->left=Create();
		T->right=Create();
		return T;
	}
}
void InOrderTraverse(BinTree T)
{
	if(!T) return;
	else{
		InOrderTraverse(T->left);
		printf("%c",T->data);
		InOrderTraverse(T->right);
	}
}
int Count(BinTree T,int count)
{
	if(T){
		if(T->left==NULL&&T->right==NULL) count++;
		count=Count(T->left,count);
		count=Count(T->right,count);
	}
	return count;
}
int main()
{
	BinTree T=Create();
	int count=0;
	InOrderTraverse(T);
	printf("\n");
	count=Count(T,count);
	printf("%d",count);
	return 0;
}
相关标签: 笔记 数据结构