二叉树叶子结点个数计算

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

1、数据结构实验报告二叉树叶子结点个数计算姓名：许严班级：计122学号：12130230501.问题描述已知一棵二叉树，求该二叉树中叶子结点的个数。2.基本要求（1）设计二叉树的二叉链表存储结构。（2）设计求叶子结点个数的递归算法。（3）输入：一棵二叉树。（4）输出：二叉树中叶子结点的个数。3.实验提示（1）存储设计二叉树采用二叉链表为存储结构。typedefstructBiTNode{TElemTypedata;StructBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;（2）算

2、法设计求二叉树中叶子结点个数，即求二叉树的所有结点中左右字数均为空的结点个数之和。可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。算法如下：VoidCountLeaf(BiNode*root,int&count)//前序遍历根指针为root的二叉树以计算叶子树count,假定count的初值为0{if(root!=NULL){If(root->lchild==NULL&&root->rchild==NULL)Count++;CountLeaf(root->lchild,c

3、ount);//累计在左子树上的叶子数CountLeaf(root->rchild,count);//累计右子树上的叶子数}}(3)程序如下#include#includeusingnamespacestd;structBiNode//二叉树的结点结构{chardata;BiNode*lchild,*rchild;};classBiTree{public:BiTree();//构造函数，初始化一棵二叉树，其前序序列由键盘输入4数据结构实验报告~BiTree(void);//析构函数，释放二

4、叉链表中各结点的存储空间BiNode*Getroot();//获得指向根结点的指针voidPreOrder(BiNode*root);//前序遍历二叉树voidBiTree::yezi(BiNode*root,int&n);private:BiNode*root;//指向根结点的头指针BiNode*Creat();//有参构造函数调用voidRelease(BiNode*root);//析构函数调用};BiTree::BiTree(){root=Creat();}BiTree::~BiTree(void){Release(r

5、oot);}BiNode*BiTree::Getroot(){returnroot;}voidBiTree::PreOrder(BiNode*root){if(root==NULL)return;else{cout<data<<"";PreOrder(root->lchild);PreOrder(root->rchild);}}voidBiTree::yezi(BiNode*root,int&n){if(root){if(root->lchild==NULL&&root->rchild==NULL)n++;ye

6、zi(root->lchild,n);yezi(root->rchild,n);}}BiNode*BiTree::Creat(){BiNode*root;4数据结构实验报告charch;cin>>ch;if(ch=='#')root=NULL;else{root=newBiNode;//生成一个结root->data=ch;root->lchild=Creat();//递归建立左子树root->rchild=Creat();//递归建立右子树}returnroot;}voidBiTree::Release(BiNode*ro

7、ot){if(root!=NULL){Release(root->lchild);//释放左子树Release(root->rchild);//释放右子树deleteroot;}}voidmain(){cout<<"请输入二叉树的结点数据：";BiTreebt;//创建一棵树BiNode*root=bt.Getroot();//获取指向根结点的指针intn=0;cout<<"------前序遍历------"<

8、叶子节叶子节点数："<