二叉树叶子结点个数计算

1、南通大学数据结构实践课实验报告册姓名：耿智班级：软件工程092学号：0913063042实验名称：计算二叉树叶子结点指导老师：丁卫平南通大学杏林学院2011年6月8日程序设计简介已知一棵二叉树，求该二叉树中叶子结点的个数。基本要求（1）设计二叉树的二叉链表为存储结构（2）设计求叶子结点个数的递归算法（3）输入：一颗二叉树（4）输出：二叉树中叶子结点的个数实现提示（1）存储设计二叉树采用二叉链表为存储结构（2）算法设计求二叉树中叶子结点个数，即求二叉树的所有结点中左、右子树均为空的结点个数之和。可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。源程序

2、#include#includeusingnamespacestd;structBiNode/二叉树的结点结构chardata;BiNode*lchild,*rchild;classBiTreepublic:BiTree();/构造函数，初始化一棵二叉树，其前序序列由键盘输入BiTree(void);/析构函数，释放二叉链表中各结点的存储空间BiNode*Getroot();/获得指向根结点的指针voidPreOrder(BiNode*root);/前序遍历二叉树voidBiTree:yezi(BiNode*root,int&n);private:BiNode*root;/指向根结点的头指针B

3、iNode*Creat();/有参构造函数调用voidRelease(BiNode*root);/析构函数调用;BiTree:BiTree()root=Creat();BiTree:BiTree(void)Release(root);BiNode*BiTree:Getroot()returnroot;voidBiTree:PreOrder(BiNode*root)if(root=NULL)return;elsecoutdatalchild);PreOrder(root-rchild);voidBiTree:yezi(BiNode*root,int&n)if(root)if(root-lchil

4、d=NULL&root-rchild=NULL)n+;yezi(root-lchild,n);yezi(root-rchild,n);BiNode*BiTree:Creat()BiNode*root;charch;cinch;if(ch=#)root=NULL;elseroot=newBiNode;/生成一个结点root-data=ch;root-lchild=Creat();/递归建立左子树root-rchild=Creat();/递归建立右子树returnroot;voidBiTree:Release(BiNode*root)if(root!=NULL)Release(root-lchil

5、d);/释放左子树Release(root-rchild);/释放右子树deleteroot;voidmain()cout请输入二叉树的结点数据：；BiTreebt;/创建一棵树BiNode*root=bt.Getroot()；/获取指向根结点的指针intn=0；cout前序遍历endl；bt.PreOrder(root)；bt.yezi(root,n)；coutendl；cout叶子节点数：n;coutendl；运行与测试请输入二叉树的结点数据；123itit#45#itfc789ttttititItIt前序遍历123456789叶子节点数；3Piessanykeytocon;inLie调试

6、感想非递归算法求叶子结点的个数#include#includeusingnamespacestd;structnode;intdata;node*lchild;node*rchild;node*root二NULL;voidmid(node*root,intkey=500)intsum=0;stacks;while(NULL!二root|!s.empty()if(NULL!=root)s.push(root);root=root-lchild;elseroot=s.top();/coutdatalchild&NULL=root-rchild)+sum;s.pop();root=root-rchild;coutsumdata=100;node*a=newnode;node*b=newnode;node*a1=newnode;node*a2=newnode;node*b1=newnode;node*b2=newnode;a-data=200;b-data=300;a1-data=400;a2-data=500;b1-data=600;b2-data=700;root-lchild=a;root-rchild=b;a-lchild=a1;a-rchild=a2;b-lchild=b1;b-rchild=b2;a1-lchild=NULL;a1-rchild=NULL