委内瑞拉官方语言：实验报告二叉树求叶子结点数目(内容清晰)

2020年11月22日发(作者：卫闻远)

实验 叶子结点的计算
姓名：xxx 班级：xxx）
学号：16130xxxxx 时间2017.10.22
1 问题描述

二叉树叶子节点的计算
1.二叉树的创建
2.二叉树的图形显示
3.二叉树叶子节点的计算
2 结构设计
二叉树叶子结点的计算主要是二叉树的创建，在这里选择的存储结构是一个链式存
储结构
Data lchild rchild
建立结构体
struct BTNode{
int data;
BTNode*lchild;
BTNode*rchild;
};
3 算法设计
在程序正式编写之前我定义了几个功能函数
（1） 指针清空函数，预定义一个指针bt 使lchild和rchild的值分别赋予bt并且
使其为空
static int clear(BTNode *bt)
{
if (bt)
{
clear(bt->lchild );
clear(bt->rchild );
cout<<释放了指针所指向的空间
delete bt;
}
return 0;
};
(2)叶子结点计数算法
叶子结点的特点是左孩子 和右孩子均为空，利用这个特点可以轻松的判断出是否
是叶子节点，利用递归算法解决这个问题，预先定 义一个计数器count 当所遇结点满足
叶子结点的条件时，count+1
static int Leaf(BTNode *p,int&count)
{

if(p)
甲类研制# 1

{
if(p->lchild==NULL&&p->rchild==NULL)count++;
Leaf(p->lchild,count);
Leaf(p->rchild,count);
}
return count;
}
（2） 二叉树的创建
同样是利用递归的方式，输入参数包括指针，左右判断，以及判空条件
static int create(BTNode *p,int k ,int end)
{
BTNode *q;
int x;
cin>>x;
if(x!=end)
{
q=new BTNode;
q->data =x;
q->lchild=NULL;
q->rchild=NULL;
if(k==1)p->lchild=q;
if(k==2)p->rchild=q;
create(q,1,end);
create(q,2,end);
}
return 0;
};
（3） 类的构造函数创建树并且输入各结点数值
在这里，采用的时先序遍历法依次输入树中的各结点数值
Step 1:定义新的结构体指针，
Step 2:申请动态存储空间；
Step 3:输入节点元素，并且指针后移到输入结点的后继结点，end作为结点
结束标志；
Step 4:重复步骤3，直到输入结束；
void BinaryTree::CreateBiTree (int end)
{
cout<<请按照先序序列的顺序输入二叉树，-1为空指针域标志：

BTNode *p;
int x;
cin >>x;
if(x==end)return;
p=new BTNode;
甲类研制# 2



if(!p)
{
cout<<申请内存失败
exit(-1);
}
p->data =x;
p->lchild =NULL;
p->rchild =NULL;
BT=p;
create(p,1,end);
create(p,2,end);
}
（4） 按树形图输出树
Step 1:定义结点bt 计数器level
Step 2:当bt存在 bt指向左孩子，level+1换行，输出结点值
Step 3:bt 指向右孩子level+1输出数值，依次递归
void BinaryTree::DisplayBTreeShape (BTNode*bt, int level)
{
if(bt)
{
DisplayBTreeShape(bt->rchild,level+1);
cout< for(int i=0;i cout<<
cout<data;
DisplayBTreeShape(bt->lchild,level+1);
}
}



1
2
5
4程序运行测试

输入该树的先序遍历
1，2，3，（-1，-1），4（-1，-1），5，6（-1.-1）（-1）
3
甲类研制#
4
6
3




甲类研制# 4


5调试记录及收获
调试记录：
（1）在开始编译过程中，，程序编译不通过在case选择中创建被直接跳过，仔细
检查过程中，，发 现在类的调用过程中缺少了类的主体，在后期其余练习中同样碰到了
kidding错误，在后期的解决 方法中在论坛上找到了解决方法及出错原因
initialization of 'XXX' is skipped by 'case' label 原因及解决办法
原创 2013年08月12日 18:34:05 1461
出错代码段：
switch (t)
{
case 0:
int a = 0;
break;
default:
break;
}
编译时提示：“error C2361: initialization of 'a' is skipped by 'default'
label”。这怎么可能？

出错原因：
C+ +约定，在块语句中，对象的作用域从对象的声明语句开始直到块语句的结束，
也就是说default 标号后的语句是可以使用对象a的。如果程序执行时从switch处跳
到default处，就会导致 对象a没有被正确地初始化。确保对象的初始化可是C++的重
要设计哲学，所以编译器会很严格地检查 这种违例情况，像上述的示例代码中default
语句后面并没有使用a，但考虑到以后代码的改动可 能无意中使用，所以一样被封杀。
明白了原因，解决起来就很容易了。只要明确地限制对象a的作用域就行了。
switch (t)
{
case 0:
甲类研制# 5