编写递归算法,计算二叉树中叶子结点的数目。

《编写递归算法,计算二叉树中叶子结点的数目。》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学院名称专业班级实验成绩学生姓名学号实验日期课程名称数据结构实验题目2树一、实验目的与要求熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。二、主要仪器设备Cfree三、实验内容和原理[问题描述]编写递归算法，计算二叉树中叶子结点的数目。[输入]一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照前序序列的顺序输入该结点的内容。对例题中的树，其输入序列ABD..EH...CF.I..G..。[输出]若为空二叉树，则输出：THISISAEMPTYBINARYTREE。若二叉树不空，输出叶子结点的个数。[存储结构]采用二叉链表存储[算法

2、的基本思想]采用递归方法建立和遍历二叉树。首先建立二叉树的根结点，然后建立其左右子树，直到空子树为止。遍历二叉树，若某一结点的左右孩子均为NULL，则该结点为叶子结点。[参考源程序]#include#includestructnode{charinfo;structnode*llink,*rlink;};typedefstructnodeNODE;NODE*create(){//构造二叉树charx;NODE*p;scanf("%c",&x);printf("%c",x);//打印出已输入的二叉树if(x!='.'){p=(NODE*)malloc(s

3、izeof(NODE));p->info=x;p->llink=create();p->rlink=create();}elsep=NULL;returnp;}intrun(NODE*t){staticintcount=0;if(t){run(t->llink);//递归遍历左子树，直到叶子处run(t->rlink);//递归遍历右子树，直到叶子处if(t->llink==NULL&&t->rlink==NULL){count++;}}returncount;}main(){NODE*T;intleft_number;printf("请输入一棵树:");T=create();prin

4、tf("");if(!T)printf("Thisisaemptybinarytree.");else{left_number=run(T);printf("这棵树共有%d个子叶.",left_number);}printf("");}四、实验结果与分析（2）习题1：注意叶子结点是指该结点既没有左孩子又没有右孩子，采用递归算法就很容易计算出其数目。实验结果如图：五、实验心得及体会本次实验加深了我对树的各种遍历方法。尤其是先序遍历。在建立树的过程中更是采取了递归的方法。有的算法用递归表示要比用循环表示简洁精练[如二叉树的遍历]，代码更简洁清晰，可读性更好有的算法递归能实现循环

5、不一定能实现，递归的内部实现要消耗额外的空间和时间。所以说循环的效率更高。