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

设二叉树采用链式存储结构,试设计一个算法计算一棵给定二叉树中叶子结点的数目include include define max 10 typedef struct node char data node lchildrchild Bitree Bitree Bmax Bitree Creatree /建立二叉树 Bitree TS char ch int frontrearsign sign0 front0 rear-1 TNULL printf建立二叉树:n chgetchar whilech ifch /输入结点不是虚结点 SBitree mallocsizeofBitree S-datach S-lchildS-rchildNULL rear BrearS ifrearfront TS sign else ifsign21 /寻找父结点 Bfront-lchildS ifsign20 Bfront-rchildS front sign else /输入结点为虚结点 ifsign20 front sign chgetchar return T int SearchleafBitree T /计算叶子数 ifTNULL return 0 else ifT-lchildNULLT-rchildNULL return 1 else returnSearchleafT-lchildSearchleafT-rchild void visitBitree T printfcnT-data void InorderBitree T /中序遍历二叉树 ifTNULL InorderT-lchild visitT InorderT-rchild void main Bitree T TCreatree printf中序遍历:n InorderT printf叶子数dnSearchleafT 题目设二叉树采用链式存储结构试设计一个算法计算一棵给定二叉树中叶子结点的数目。 问题分析 本程序要求在一棵二叉树中实现计算叶子结点数目的功能为完成上述功能需要解决的关键问题是建立二叉树过程及查找叶子结点过程。 概要设计 建立一个以二叉链表方式存储的二叉树输入结点信息时按照完全二叉树的结点顺序输入。 先序遍历二叉树并判断遍历的根是否是叶子结点若是并记录叶子结点个数。叶子结点判断条件为左孩子域和右孩子域都为空。 详细设计 建立二叉树时按照完全二叉树的结点顺序输入表示虚结点表示输入结束。 若不是虚结点时则建立一个新结点并且将其作为左孩子或右孩子结点连接到它的父结点上第一个结点无父结点若是虚结点则将空结点NULL作为左孩子或右孩子结点连接到它的父节点上。 查找叶子结点利用递归先序遍历二叉树方法来查找叶子结点当遍历一个根结点时判断其左孩子域和右孩子域是否都为空若都为空则该结点是叶子结点并用记录叶子个数否则不是叶子结点。 调试分析及小结 错误及分析当按照完全二叉树的结点顺序输入ABCDE后程序无法运行。经测试发现在建立二叉树时出现问题。 当扫描到B时执行else ifsign21 Bfront-lchildS Sign ifsign20 Bfront-rchildS front sign 注执行上述程序前sign1Bfront指向关键字为A的结点。 当一个if语句段执行完后关键字为A的结点的左孩子为关键字为B的结点sign2。此时本应结束else语句段但由于sign2则第二个if语句条件为真继续执行因此导致程序执行出错。 改正在if语句