二叉树叶子结点个数计算

二叉树叶子结点个数计算

姓名：许严 班级：计122 学号：1213023050

1. 问题描述

已知一棵二叉树，求该二叉树中叶子结点的个数。

2. 基本要求

（1） 设计二叉树的二叉链表存储结构。

（2） 设计求叶子结点个数的递归算法。

（3） 输入：一棵二叉树。

（4） 输出：二叉树中叶子结点的个数。

3. 实验提示

（1） 存储设计

二叉树采用二叉链表为存储结构。

typedef struct BiTNode{

1

数据结构实验报告

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); //累计在左子树上的叶子数

2

数据结构实验报告

CountLeaf(root->rchild,count); //累计右子树上的叶子数

}

}

(3)程序如下

#include

#include

using namespace std;

struct BiNode //二叉树的结点结构

{

char data;

BiNode *lchild, *rchild;

};

class BiTree

3

数据结构实验报告

{

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( )

4

数据结构实验报告

{

root = Creat( );

}

BiTree::~BiTree(void)

{

Release(root);

}

BiNode* BiTree::Getroot( )

{

return root;

}

void BiTree::PreOrder(BiNode *root) {

5

数据结构实验报告

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) 6

数据结构实验报告

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; //生成一个结

7

数据结构实验报告

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;

}

8

数据结构实验报告

}

void main()

{

cout<<\"请输入二叉树的结点数据：\";

BiTree bt; //创建一棵树

BiNode *root = bt.Getroot( ); //获取指向根结点的指针

int n=0;

cout<<\"------前序遍历------ \"<bt.PreOrder(root);

bt.yezi(root,n);

cout<cout<<\"叶子节叶子节点数：\"<cout<9

数据结构实验报告

}

4.运行结果

输入二叉树：ab#c##d##

二叉树叶子结点的个数：2

5.实验心得

让我自己一个人写个完整的程序，觉得是不可能的，老是要参考或是搜集资料的。不参考吧，自己写的又一塌糊涂，自己也不明白。所以一直都很困扰，该怎么学，是个问题，皮毛干不了什么。看书看不下去，没动力。说实话，学了什么我也不知道，迷迷糊糊的。不管怎样，还是要学点，学一些是一些嘛，总会有好处的，至少考试要能通过。加油吧，努力总会有回报，不努力什么也没有。

10