数据结构课程设计-线索二叉树的应用

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称数据结构课题名称线索二叉树的应用专业计算机科学与技术班级10计本2班学号10012084姓名联系方式指导教师2011年12月25日目录1、数据结构课程设计任务书111、题目112、要求12、总体设计121、数据输入输出122、设计算法测试用例122、流程图23、详细设计231、程序中所采用的数据结构及存储结构的说明432、算法的设计思想54、调试与测试641、调试方法与步骤642、测试结果的分析与讨论66、源程序清单和执行结果97、C程序设计总结178、致谢179、参考文献18第页1、数据结构课程设计任务书11、题目线索二叉树的应用12、要求实现线索树建立、插入、删除、恢复线索的实现。2、总体设计21、数据输入输出原始数据要求输入二叉树的7个结点1234567，输出的是一个二叉树，这就实现了二叉树的建立过程。然后对二叉树进行线索化。对其进行插入在7结点处插入结点8；删除删除结点8恢复线索等功能。进行二叉树的初始化，依次输入，以结束1234567线索二叉树的应用1、进行二叉树线索化2、进行插入操作3、删除4、中序输出5、线索输出0、退出请选择1已经实现二叉树的线索化，可选择5查看线索。22、设计算法测试用例（1）输入结点12345672对输入的二叉树进行线索化；（3）查看二叉树的中序线索输出4251637；（4）在7结点处插入结点8，此时完成线索化恢复，查看二叉树的中序线索输出425163875删除结点8，此时完成线索化恢复，发现结点8，LTAG1,RTAG1,查看二叉树的中序线索输出42516376继续删除结点R，发现无该结点，则输入错误。第页23、流程图开始定义二叉树TCREATTREE1I输入I0输入选择菜单输入II1PRETHREDTI2INSERTTI3DELETENODETI4INORDERT退出3、详细设计（1）、主函数VOIDMAINBITHPTRTINTI/SYSTEM“COLOR1A“TCREATTREEPRINTF“N“第页I1WHILEIPRINTF“T1进行二叉树线索化N“PRINTF“T2进行插入操作N“PRINTF“T3进入删除操作N“PRINTF“T4中序输出N“PRINTF“T5线索输出N“PRINTF“T0退出N“PRINTF“T请选择“SCANF“D“,PRINTF“N“SWITCHICASE1PRETHREADTPRINTF“T已经实现二叉树的线索化N“PRINTF“N“BREAKCASE2INSERTTPRINTF“N“BREAKCASE3TDELETENODETPRINTF“N“BREAKCASE4INORDERTPRINTF“N“BREAKCASE5PRINTINDEXTBREAKCASE0EXIT1DEFAULTPRINTF“ERRORNT请继续选择“（2）、中序线索化算法VOIDPRETHREADBITHPTRROOT/中序线索化算法，函数实现BITHPTRPPROOTIFPPRETHREADPLCHILD/线索化左子树IFPRE/前驱结点后继线索化IFPLCHILDNULLPLTAG1PLCHILDPREIFPRCHILDNULL/后继结点前驱线索化PRTAG1PREPPRETHREADPRCHILD第页31、程序中所采用的数据结构及存储结构的说明二叉树是由N（N0）个结点组成的有限集合，其中（1）当N0时，为空二叉树。（2）当N0时，有且仅有一个特定的结点，称为二叉树的根，不相交的子集，其中每一个子集本身又是一棵二叉树，分别称为左子树和右子树。线索化是将二叉树转换成线索二叉树的过程。按某种遍历将二叉树线索化，只需在遍历过程中将二叉树中每个结点的空的左右孩子指针域分别修改为指向其前驱和后继结点。（1）线索二叉树的结点的结构如下LTAGLCHILDDATARTAGRCHILD约定LTAG0/表示LCHILD域指示该结点的左孩子LTAG1/表示LCHILD域指示该结点的前驱RTAG0/表示RCHILD域指示该结点的右孩子RTAG1/表示RCHILD域指示该结点的后继2线索链表中结点类型说明TYPEDEFCHARDATATYPETYPEDEFSTRUCTNODEINTLTAG,RTAGDATATYPEDATASTRUCTNODELCHILD,RCHILDBITHPTR3线索化算法结点PRE是结点P的前驱，而P是PRE的后继。这样，当遍历到结点P时，可以进行以下三步操作1）若P有空指针域，则将相应的标志置12）若P的左线索标志已经建立（PLTAG1）,则可使其前驱线索化，令PLCHILDPRE3若PRE的右线索标志已经建立（PRERTAG1）,则可使其后继线索化，令PRERCHILDP第页如此，二叉树的线索化可以在二叉树的遍历过程完成，该算法应为相应顺序的遍历算法的一种变化形式。（4）二叉链表的建立其算法描述如下BITREECRT_BT_PREBITREEBTCHARCHCHGETCHARIFCHBTNULLELSEBTBITREEMALLOCSIZEOFBITREEBTDATACBTLCHILDCRT_BT_PREBTLCHILDBTRCHILDCRT_BT_PREBTRCHILDRETURNBT32、算法的设计思想建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需添加虚结点，使其成为完全二叉树。关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。可以设置一个队列，该队列是一个指针类型的数组，保存已输入的结点地址。操作（1）令队头指针FRONT指向其孩子结点当前输入的建立链接的父结点，队尾指针REAR指向当前输入的结点，初始FRONT1,REAR0（2）若REAR为偶数，则该结点为父结点的左孩子；若REAR为奇数，则该结点的右孩子；若父结点和孩子结点为虚结点，则无需链接。（3）若父结点与其两个孩子结点的链接完毕，则令FRONTFRONT1,使FRONT指向下一个等待链接的父结点。二叉树的中序线索化算法与中序遍历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。该算法应附设一个指针PRE始终指向刚刚访问过的结点（PRE的初值应为NULL），而指针P指示当前正在访问的结点。结点PRE是结点P的前趋，而P是PRE的后继。结点插入算法由线索二叉树的定义易知插入的节点定是个叶子节点，需注意线索的修改，可分为两种情况1）插入的节点T是右儿子，T的中序后继是其父亲的中序后继，中序前驱是其父亲。第页2）插入的节点T是左儿子，T的中序前驱是其父亲的中序前驱，中序后继是其父亲。结点删除算法删除的情况与搜索二叉树的删除的类似1）删除的节点P是叶子节点，直接删除，修改其父亲的线索。2）删除的节点P有一个儿子，P有一个左儿子，以P为根的左子树中的具有最大值节点的T中序后继是P的中序后继，中序前驱不变；P有一个右儿子，以P为根的右子中的具有最小值节点T中序前驱是P的中序前驱，中序后继不变。3）删除的节点P有二个儿子，转化为叶子节点或只有一个儿子节点的删除。4、调试与测试41、调试方法与步骤1、当用二叉链表作为二叉树的存储结构时。可以方便地找到某个结点的左右孩子，但一般情况下，无法直接摘到该结点在没中遍历序列中的前驱和后继接待你。为了解决这个问题，所以采用线索二叉树。但是在编写过程中，忽略了线索二叉树的改变，没有改变空的左孩子指针域，而后再看了一遍数据结构的相关指导教材，发现了错误，及时改正，将空的左孩子指针域改为指向其前驱。2、在进行线索化的编写过程中，出现了问题。开始只能对几点进行前驱线索化，而不能进行后继线索化。为此做了相应调整（1）若P有空指针域，则将相应的标志置1。（2）若P的左线索标志已经建立，则可使其前驱线索化，令PLCHILDPRE。（3）若PRE的右线索标志已经建立，则可使其后继线索化，令PRERCHILDP。3、在编写中序线索二叉树中的后继查找算法时，只编写了其中一种情况，应该有两种情况1P的右子树为空，则PRCHILD为右线索，指向P的后继结点。（2）若P的右子树非空，根据中序遍历的顺序，P的后继结点为其右子树中最左下的结点。42、测试结果的分析与讨论如图1所示，初始化输入二叉树，实现线索化，查看线索输出第页图1如图2所示，在7结点处插入结点8，恢复线索化，查看中序线索输出为第页图2如图3所示，删除结点8，恢复线索化，查看中序线索输出为图3如图4所示，删除结点R，发现无该结点，则输出为第页图46、源程序清单和执行结果INCLUDEINCLUDE“MALLOCH“INCLUDE“WINDOWSH“DEFINEMAXSIZE30/规定树中结点的最大数目TYPEDEFSTRUCTNODE/定义数据结构INTLTAG,RTAG/表示CHILD域指示该结点是否孩子CHARDATA/记录结点的数据STRUCTNODELCHILD,RCHILD/记录左右孩子的指针BITHPTRBITHPTRQMAXSIZE/建队，保存已输入的结点的地址BITHPTRCREATTREE/建树函数，返回根指针CHARCHINTFRONT,REARBITHPTRT,STNULLFRONT1REAR0/置空二叉树PRINTF“进行初始化，请依次输入N“CHGETCHAR/输入第一个字符WHILECH/判断是否为结束字符SNULLIFCH/判断是否为虚结点SBITHPTRMALLOCSIZEOFBITHPTRSDATACHSLCHILDNULLSRCHILDNULLSRTAG0SLTAG0第页REARQREARS/将结点地址加入队列中IFREAR1TS/输入为第一个结点为根结点ELSEIFSNULLELSEQFRONTRCHILDSIFREAR21FRONTCHGETCHARRETURNTVOIDINORDERBITHPTRT/中序遍历IFTIFTLTAG1INORDERTLCHILDPRINTF“C“,TDATAIFTRTAG1INORDERTRCHILDBITHPTRPRENULLVOIDPRETHREADBITHPTRROOT/中序线索化算法，函数实现BITHPTRPPROOTIFPPRETHREADPLCHILD/线索化左子树IFPRE/前驱结点后继线索化IFPLCHILDNULLPLTAG1PLCHILDPREIFPRCHILDNULL/后继结点前驱线索化PRTAG1PREPPRETHREADPRCHILDVOIDPRINTINDEXBITHPTRT/输出线索第页BITHPTRFFTIFFIFFLTAG1/如果是第一个结点IFFLTAG1/如果此结点有前驱就输出前驱和此结点IFFLTAG1/如果此结点有前驱也有后继，就输出后继ELSEIFFRTAG1/如果没有前驱，就输出此结点和后继PRINTF“N“IFFLTAG1PRINTINDEXFLCHILDIFFRTAG1PRINTINDEXFRCHILDBITHPTRSEARCHCHILDBITHPTRPOINT,CHARFINDNODE/查找孩子结点函数BITHPTRPOINT1,POINT2IFPOINTNULLIFPOINTDATAFINDNODERETURNPOINTELSEIFPOINTLTAG1POINT1SEARCHCHILDPOINTLCHILD,FINDNODEIFPOINT1NULLRETURNPOINT1IFPOINTRTAG1POINT2SEARCHCHILDPOINTRCHILD,FINDNODEIFPOINT2NULLRETURNPOINT2RETURNNULLELSERETURNNULLBITHPTRSEARCHPREBITHPTRPOINT,BITHPTRCHILD/查找父亲结点函数BITHPTRPOINT1,POINT2IFPOINTNULLIFPOINTLTAG1ELSEIFPOINTLTAG1第页POINT1SEARCHPREPOINTLCHILD,CHILDIFPOINT1NULLRETURNPOINT1IFPOINTRTAG1POINT2SEARCHPREPOINTRCHILD,CHILDIFPOINT2NULLRETURNPOINT2RETURNNULLELSERETURNNULLVOIDINSERTBITHPTRROOTCHARCHCHARCBITHPTRP1,CHILD,P2PRINTF“请输入要插入的结点的信息“SCANF“C“,SCANF“C“,P1BITHPTRMALLOCSIZEOFBITHPTR/插入的结点信息P1DATACP1LCHILDNULLP1RCHILDNULLP1RTAG0P1LTAG0PRINTF“输入查找的结点信息“SCANF“C“,SCANF“C“,CHILDSEARCHCHILDROOT,CH/查孩子结点的地址IFCHILDNULLPRINTF“没有找到结点N“SYSTEM“PAUSE“RETURNELSEPRINTF“发现结点CN“,CHILDDATAIFCHILDLTAG0/当孩子结点有左孩子的时候P2CHILDCHILDCHILDLCHILDWHILECHILDRCHILD第页PRINTF“发现结点CN“,CHILDDATAP1RCHILDCHILDRCHILD/后继化P1RTAG1CHILDRTAG0CHILDRCHILDP1/连接P1LCHILDCHILD/前驱化P1LTAG1ELSE/当孩子结点没有左孩子的时候P1LCHILDCHILDLCHILD/前驱化CHILDLTAG0P1LTAG1CHILDLCHILDP1P1RCHILDCHILDP1RTAG1PRINTF“NT插入结点操作已经完成，并同时完成了线索化的恢复N“BITHPTRDELETENODEBITHPTRTBITHPTRCHILD,PRE,S,QCHARCHPRINTF“输入查找的结点信息“CHGETCHARCHGETCHARCHILDSEARCHCHILDT,CHPRINTF“发现结点CN“,CHILDDATAPRINTF“LTAGD,RTAGDN“,CHILDLTAG,CHILDRTAGPRESEARCHPRET,CHILDPRINTF“发现结点CN“,PREDATAIFNULLCHILDPRINTF“没有找到结点“RETURNTSYSTEM“PAUSE“IFCHILDPRELCHILD|CHILDPRE/是父亲结点的左孩子IF1CHILDLTAGPRELTAG1IFCHILDLCHILDNULL第页IFCHILDLCHILDRTAG1CHILDLCHILDRCHILDPREFREECHILDELSEIF1CHILDLTAGSCHILDLCHILDWHILESRCHILDSSRCHILDSRCHILDCHILDRCHILDFREECHILDELSEIF1CHILDLTAGSCHILDRCHILDWHILESLCHILDSSLCHILDSLCHILDCHILDLCHILDIFCHILDLCHILDNULLIFCHILDLCHILDRTAG1CHILDLCHILDRCHILDPREFREECHILDELSEIF1CHILDLTAGSCHILDRCHILDWHILESLCHILDSSLCHILDSLCHILDCHILDLCHILDRCHILD/把孩子结点的左孩子的右子树接到孩子右子树的最左下结点IFCHILDLCHILDRTAG1SLTAG0QCHILDLCHILDWHILEQRCHILDQQRCHILDQRCHILDSCHILDLCHILDRCHILDCHILDRCHILDCHILDLCHILDRTAG0FREECHILDIFCHILDPRERCHILD/是父亲结点的右孩子IF1CHILDLTAGPRERTAG1第页IFCHILDRCHILDNULLIFCHILDRCHILDLTAG1CHILDRCHILDLCHILDPREFREECHILDELSEIF1CHILDLTAGSCHILDLCHILDWHILESRCHILDSSRCHILDSRCHILDCHILDRCHILDIFCHILDRCHILDNULLIFCHILDRCHILDLTAG1CHILDRCHILDLCHILDPREFREECHILDELSEIF1CHILDLTAGSCHILDRCHILDWHILESLCHILDSSLCHILDSLCHILDCHILDLCHILDFREECHILDELSEIF1CHILDLTAGSCHILDRCHILDWHILESLCHILDSSLCHILDSLCHILDCHILDLCHILDRCHILD/把孩子结点的左孩子的右子树接到孩子右子树的最左下结点IFCHILDLCHILDRTAG1SLTAG0QCHILDLCHILDWHILEQRCHILDQQRCHILDQRCHILDSCHILDLCHILDRCHILDCHILDRCHILDCHILDLCHILDRTAG0/第页PRERCHILDCHILDRCHILDSCHILDLCHILDWHILESRCHILDSSRCHILDSRCHILDCHILDRCHILDLCHILD/把孩子结点的左孩子的右子树接到孩子右子树的最右下结点IFCHILDRCHILDLTAG1SRTAG0QCHILDRCHILDWHILEQLCHILDQQLCHILDQLCHILDSCHILDRCHILDLCHILDCHILDLCHILDCHILDRCHILDLTAG0FREECHILDPRINTF“NT插入结点操作已经完成，并同时完成了线索化的恢复N“PRINTF“FINDC“,CHILDDATARETURNTVOIDMAINBITHPTRTINTI/SYSTEM“COLOR1A“TCREATTREEPRINTF“N“I1WHILEIPRINTF“T1进行二叉树线索化N“PRINTF“T2进行插入操作N“PRINTF“T3进入删除操作N“PRINTF“T4中序输出N“PRINTF“T5线索输出N“PRINTF“T0退出N“PRINTF“T请选择“SCANF“D“,PRINTF“N“SWITCHICASE1PRETHREADTPRINTF“T已经实现二叉树的线索化N“PRINTF“N“BREAK第页CASE2INSERTTPRINTF“N“BREAKCASE3TDELETENODETPRINTF“N“BREAKCASE4INORDERTPRINTF“N“BREAKCASE5PRINTINDEXTBREAKCASE0EXIT1DEFAULTPRINTF“ERRORNT请继续选择“7、C程序设计总结