[宝典]二叉树叶子结点个数计算[宝典]二叉树叶子结点个数计算
二叉树叶子结点个数计算
姓名,许严 班级,计122 学号,1213023050 1. 问题描述
已知一棵二叉树,求该二叉树中叶子结点的个数。 2. 基本要求
,1, 设计二叉树的二叉链表存储结构。 ,2, 设计求叶子结点个数的递归算法。 ,3, 输入,一棵二叉树。
,4, 输出,二叉树中叶子结点的个数。 3. 实验提示
,1, 存储设计
二叉树采用二叉链表为存储结构。 typedef struct BiTNode{
TElemType data;
Struct BiTNode *...
[宝典]二叉树叶子结点个数计算
二叉树叶子结点个数计算
姓名,许严 班级,计122 学号,1213023050 1. 问题描述
已知一棵二叉树,求该二叉树中叶子结点的个数。 2. 基本要求
,1,
二叉树的二叉链表存储结构。 ,2, 设计求叶子结点个数的递归算法。 ,3, 输入,一棵二叉树。
,4, 输出,二叉树中叶子结点的个数。 3. 实验提示
,1, 存储设计
二叉树采用二叉链表为存储结构。 typedef struct BiTNode{
TElemType data;
Struct BiTNode *lchild,*rchild;//左右孩子指针 }
BiTNode,*BiTree;
,2, 算法设计
求二叉树中叶子结点个数,即求二叉树的所有结点中左右字数均为空的结点个数之和。可以将此问题转化为遍历问题,在遍历中“访问一个结点”时判断该结点是不是叶子,若是则将计数器累加。算法如下,
Void CountLeaf(BiNode
*root,int &count) //前序遍历根指针为root的二叉树以计算叶子树count,假定count 的初值为0
{ if(root!=NULL){
If(root->lchild==NULL&&root->rchild==NULL) Count++;
CountLeaf(root->lchild,count); //累计在左子树上的叶子数 CountLeaf(root->rchild,count); //累计右子树上的叶子数 }
}
(3)程序如下
#include
#include
using namespace std;
struct BiNode //二叉树的结点结构
{
char data;
BiNode *lchild, *rchild;
};
class BiTree
{
public:
BiTree( ); //构造函数,初始化一棵二叉树,其前序序列由键盘输入
~BiTree(void); //析构函数,释放二叉链表中各结点的存储空间
BiNode* Getroot(); //获得指向根结点的指针
void PreOrder(BiNode *root); //前序遍历二叉树
void BiTree::yezi(BiNode *root,int &n); private:
BiNode *root; //指向根结点的头指针
BiNode *Creat( ); //有参构造函数调用
void Release(BiNode *root); //析构函数调用 };
BiTree::BiTree( )
{
root = Creat( );
}
BiTree::~BiTree(void)
{
Release(root);
}
BiNode* BiTree::Getroot( )
{
return root;
}
void BiTree::PreOrder(BiNode *root) {
if(root==NULL)
return;
else{
cout<data<<" ";
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}
void BiTree::yezi(BiNode *root,int &n) {
if(root)
{
if(root->lchild==NULL&&root->rchild==NULL)
n++;
yezi(root->lchild,n);
yezi(root->rchild,n);
}
}
BiNode* BiTree::Creat( )
{
BiNode *root;
char ch;
cin>>ch;
if (ch=='#') root = NULL;
else{
root = new BiNode; //生成一个结
root->data=ch;
root->lchild = Creat( ); //递归建立左子树
root->rchild = Creat( ); //递归建立右子树
}
return root;
}
void BiTree::Release(BiNode *root) {
if (root!= NULL){
Release(root->lchild); //释放左子树
Release(root->rchild); //释放右子树
delete root;
}
}
void main()
{
cout<<"请输入二叉树的结点数据,";
BiTree bt; //创建一棵树
BiNode *root = bt.Getroot( ); //获取指向根结点的指针
int n=0;
cout<<"------前序遍历------ "<
本文档为【[宝典]二叉树叶子结点个数计算】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。