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

《实验报告二叉树求叶子结点数目》由会员分享，可在线阅读，更多相关《实验报告二叉树求叶子结点数目（6页珍藏版）》请在装配图网上搜索。

1、实验 叶子结点的计算姓名：XXX 班级：XXX)学号：16130XXXXX 时间 2017.10.221问题描述二叉树叶子节点的计算1. 二叉树的创建2. 二叉树的图形显示3. 二叉树叶子节点的计算2结构设计 二叉树叶子结点的计算主要是二叉树的创建，在这里选择的存储结构是一个链式 存储结构Datalchildrchild建立结构体 struct BTNodeint data;BTNode*lchild;BTNode*rchild;3算法设计 在程序正式编写之前我定义了几个功能函数(1) 指针清空函数，预定义一个指针bt使Ichild和rchild的值分别赋予bt并 且使其为空static in

2、t clear(BTNode *bt)if (bt)clear(bt-lchild ); clear(bt-rchild ); cout释放了指针bt所指向的空间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; cinx; if(x!=end)q=new BTNode

3、; 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:申请动态存储空间；St ep 3:输入节点元素，并且指针后移到输入结点的后继结点，end作为结点 结束标志；Step 4:重复步骤3，直到输入结束；void BinaryTree:CreateBiTree (i

4、nt end) cout请按照先序序列的顺序输入二叉树，-1为空指针域标志： x; if(x=end)return; p=new BTNode;if(!p)cout申请内存失败data =x;p-lchild =NULL;p-rchild =NULL;BT=p;create(p,1,end); create(p,2,end);4) 按树形图输出树St ep 1:定义结点bt 计数器levelStep 2:当bt存在bt指向左孩子，level+1换行，输出结点值Step 3:bt指向右孩子level+1输出数值，依次递归void BinaryTree:DisplayBTreeShape (BTN

5、ode*bt, int level) if(bt) DisplayBTreeShape(bt-rchild,level+1);coutendl;for(int i=0;ilevel-1;i+)cout ;coutdata; DisplayBTreeShape(bt-lchild,level+1);4程序运行测试输入该树的先序遍历1，2，3，（-1，-1），4（-1，-1），5，6（-1.-1）（-1）时Istt出 二二点 MJS结 创辎于一-一示一一显一（照先于子利的顺序爭人二克拥，-1两空帝片培标志: 3 - -1 4 -1 - 5 6 -1 - -1.13无滾仲炸业卿慣商極晦屍&迄CM九1

6、昭叶子廿虑计JlghugUg屮M轲te出 二二占二 建出结 fir输子 TTBK一一示一-丘-牍 锂3意2 厳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

7、;default:break;编译时提示：“error C2361: initialization of a is skipped by default label”。这怎么可能？出错原因：C+约定，在块语句中，对象的作用域从对象的声明语句开始直到块语句的结束， 也就是说default标号后的语句是可以使用对象a的。如果程序执行时从switch处跳 到default处，就会导致对象a没有被正确地初始化。确保对象的初始化可是C+的重 要设计哲学，所以编译器会很严格地检查这种违例情况，像上述的示例代码中default 语句后面并没有使用a,但考虑到以后代码的改动可能无意中使用，所以一样被封杀。明白

8、了原因，解决起来就很容易了。只要明确地限制对象a的作用域就行了。 switch (t)case 0: /added for fix problemint a = 0;break; /added for fix problemdefault:break;解决方案在switch.case.结构中不能在case中定义新变量，for（int i二0;.） 除非将定义新变量的case用块包住，或者选择将你的新变量在switch之前。 例如可以将case :for(int i = 0 ; i n ; i+) break;修改成如下即可：case :for(int i = 0 ; i n ; i+) break;（2）在调试过程中发现在二叉树的从创建过程中无法正常创建二叉树，原因是输 入方式用的是先序遍历序列，在二叉树中一种遍历序列是无法确定一个二叉树的，在 算法执行过程中违反了算法的确定性，所以，在执行过程中出现严重错误，其解决办法就是，引入结束终止符，当后继结点为空时，输入终止符（如-1）这 样，就解除了算法的二义性问题