设二叉树采用链式存储结构,试设计一个算法计算一棵给定二叉树中叶子结点的数目

《设二叉树采用链式存储结构,试设计一个算法计算一棵给定二叉树中叶子结点的数目》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、设二叉树采用链式存储结构,试设计一个算法计算一棵给定二叉树中叶子结点的数目includeincludedefinemax10typedefstructnodechardatanodelchildrchildBitreeBitreeBmaxBitreeCreatree//建立二叉树BitreeTScharchintfrontrearsignsign0front0rear-1TNULLprintf建立二叉树:nchgetcharwhilechifch//输入结点不是虚结点SBitreemallocsizeofBitreeS-datachS-lchildS-rchildNULLrearBrearS

2、ifrearfrontTSsignelseifsign21//寻找父结点Bfront-lchildSifsign20Bfront-rchildSfrontsignelse//输入结点为虚结点ifsign20frontsignchgetcharreturnTintSearchleafBitreeT//计算叶子数ifTNULLreturn0elseifT-lchildNULLT-rchildNULLreturn1elsereturnSearchleafT-lchildSearchleafT-rchildvoidvisitBitreeTprintfcnT-datavoidInorderBitree

3、T//中序遍历二叉树ifTNULLInorderT-lchildvisitTInorderT-rchildvoidmainBitreeTTCreatreeprintf中序遍历:nInorderTprintf叶子数dnSearchleafT题目 设二叉树采用链式存储结构试设计一个算法计算一棵给定二叉树中叶子结点的数目。问题分析本程序要求在一棵二叉树中实现计算叶子结点数目的功能为完成上述功能需要解决的关键问题是建立二叉树过程及查找叶子结点过程。概要设计①建立一个以二叉链表方式存储的二叉树输入结点信息时按照完全二叉树的结点顺序输入。②先序遍历二叉树并判断遍历的根是否是叶子结点若是并记录叶子结点个数

4、。叶子结点判断条件为左孩子域和右孩子域都为空。详细设计①建立二叉树时按照完全二叉树的结点顺序输入表示虚结点表示输入结束。若不是虚结点时则建立一个新结点并且将其作为左孩子或右孩子结点连接到它的父结点上第一个结点无父结点若是虚结点则将空结点NULL作为左孩子或右孩子结点连接到它的父节点上。②查找叶子结点利用递归先序遍历二叉树方法来查找叶子结点当遍历一个根结点时判断其左孩子域和右孩子域是否都为空若都为空则该结点是叶子结点并用记录叶子个数否则不是叶子结点。调试分析及小结错误及分析当按照完全二叉树的结点顺序输入ABCDE后程序无法运行。经测试发现在建立二叉树时出现问题。当扫描到B时执行elseifsi

5、gn21Bfront-lchildSSignifsign20Bfront-rchildSfrontsign注执行上述程序前sign1Bfront指向关键字为A的结点。当一个if语句段执行完后关键字为A的结点的左孩子为关键字为B的结点sign2。此时本应结束else语句段但由于sign2则第二个if语句条件为真继续执行因此导致程序执行出错。改正在if语句外置sign改正后代码如下elseifsign21Bfront-lchildSifsign20Bfront-rchildSfrontsign