实验报告二叉树求叶子结点数目.docx

实验报告二叉树求叶子结点数目.docx

《实验报告二叉树求叶子结点数目.docx》由会员分享，可在线阅读，更多相关《实验报告二叉树求叶子结点数目.docx（9页珍藏版）》请在冰点文库上搜索。

实验报告二叉树求叶子结点数目

实验叶子结点的计算

：

xxx班级：

xxx〕

学号：

16130xxxxx时间2021.10.22

1问题描述

二叉树叶子节点的计算

1.二叉树的创立

2.二叉树的图形显示

3.二叉树叶子节点的计算

2构造设计

二叉树叶子结点的计算主要是二叉树的创立，在这里选择的存储构造是一个链式存储构造

Data

lchild

rchild

建立构造体

structBTNode{

intdata;

BTNode*lchild;

BTNode*rchild;

};

3算法设计

在程序正式编写之前我定义了几个功能函数

（1）指针清空函数，预定义一个指针bt使lchild和rchild的值分别赋予bt并且使其为空

staticintclear（BTNode*bt）

{

if（bt）

{

clear（bt->lchild）;

clear（bt->rchild）;

cout<<"释放了指针"<

deletebt;

}

return0;

};

（2）叶子结点计数算法

叶子结点的特点是左孩子和右孩子均为空，利用这个特点可以轻松的判断出是否是叶子节点，利用递归算法解决这个问题，预先定义一个计数器count当所遇结点满足叶子结点的条件时，count+1

staticintLeaf（BTNode*p,int&count）

{

if（p）

{

if（p->lchild==NULL&&p->rchild==NULL）count++;

Leaf（p->lchild,count）;

Leaf（p->rchild,count）;

}

returncount;

}

（2）二叉树的创立

同样是利用递归的方式，输入参数包括指针，左右判断，以及判空条件

staticintcreate（BTNode*p,intk,intend）

{

BTNode*q;

intx;

cin>>x;

if（x!

=end）

{

q=newBTNode;

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）;

}

return0;

};

（3）类的构造函数创立树并且输入各结点数值

在这里，采用的时先序遍历法依次输入树中的各结点数值

Step1:

定义新的构造体指针，

Step2:

申请动态存储空间；

Step3:

输入节点元素，并且指针后移到输入结点的后继结点，end作为结点完毕标志；

Step4:

重复步骤3，直到输入完毕；

voidBinaryTree:

:

CreateBiTree（intend）

{

cout<<"请按照先序序列的顺序输入二叉树，-1为空指针域标志：

"<

BTNode*p;

intx;

cin>>x;

if（x==end）return;

p=newBTNode;

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）按树形图输出树

Step1:

定义结点bt计数器level

Step2:

当bt存在bt指向左孩子，level+1换行，输出结点值

Step3:

bt指向右孩子level+1输出数值，依次递归

voidBinaryTree:

:

DisplayBTreeShape（BTNode*bt,intlevel）

{

if（bt）

{

DisplayBTreeShape（bt->rchild,level+1）;

cout<

for（inti=0;i

cout<<"";

cout<data;

DisplayBTreeShape（bt->lchild,level+1）;

}

}

4程序运行测试

输入该树的先序遍历

1，2，3，〔-1，-1〕，4〔-1，-1〕，5，6〔-1.-1〕〔-1〕

5调试记录及收获

调试记录：

〔1〕在开场编译过程中，，程序编译不通过在case选择中创立被直接跳过，仔细检查过程中，，发现在类的调用过程中缺少了类的主体，在后期其余练习中同样碰到了kidding错误，在后期的解决方法中在论坛上找到了解决方法及出错原因

initializationof'XXX'isskippedby'case'label原因及解决方法

原创2021年08月12日18:

34:

051461

出错代码段：

switch（t）

{

case0:

inta=0;

break;

default:

break;

}

编译时提示：

“errorC2361:

initializationof'a'isskippedby'default'label〞。

这怎么可能？

出错原因：

C++约定，在块语句中，对象的作用域从对象的声明语句开场直到块语句的完毕，也就是说default标号后的语句是可以使用对象a的。

如果程序执行时从switch处跳到default处，就会导致对象a没有被正确地初始化。

确保对象的初始化可是C++的重要设计哲学，所以编译器会很严格地检查这种违例情况，像上述的例如代码中default语句后面并没有使用a，但考虑到以后代码的改动可能无意中使用，所以一样被封杀。

明白了原因，解决起来就很容易了。

只要明确地限制对象a的作用域就行了。

switch（t）

{

case0:

{//addedforfixproblem

inta=0;

break;

}//addedforfixproblem

default:

break;

}

解决方案

在switch...case...构造中不能在case中定义新变量，for（inti=0;...）

除非将定义新变量的case用块{}包住，或者选择将你的新变量在switch之前。

例如可以将

……

case:

for（inti=0;i

{

……

}

break;

……

修改成如下即可：

……

case:

｛

for（inti=0;i

{

……

}

break;

｝

……

〔2〕在调试过程中发现在二叉树的从创立过程中无常创立二叉树，原因是输入方式用的是先序遍历序列，在二叉树中一种遍历序列是无法确定一个二叉树的，在算法执行过程中违反了算法确实定性，所以，在执行过程中出现严重错误，

其解决方法就是，引入完毕终止符，当后继结点为空时，输入终止符〔如-1〕这样，就解除了算法的二义性问题

教育之通病是教用脑的人不用手，不教用手的人用脑，所以一无所能。

教育革命的对策是手脑联盟，结果是手与脑的力量都可以大到不可思议。