线索叉树课程设计.docVIP

专业基础综合课程设计 设计说明书 线索二叉树的实现 学生姓名 xxx 学号 班级 成绩 指导教师 数学与计算机科学学院 2012 年 6月 29日 专业基础综合课程设计评阅书 题 目 线索二叉树的实现 学生姓名 学号 指导教师评语及成绩 成绩： 教师签名： 年 月 日 答辩教师评语及成绩 成绩： 教师签名： 年 月 日 教研室意见 总成绩： 室主任签名： 年 月 日 注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。 课程设计任务书 2011—2012学年第2学期 专业：计算机应用技术 学号： 姓名： 课程设计名称： 专业基础综合课程设计 设 计 题 目： 线索二叉树的实现 完 成 期 限：自 2012 年 6 月 18 日至 2012 年 6月 29 日共 2 周 设计内容： n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为线索）。这种加上了线索的二叉树称为线索二叉树(Threaded??BinaryTree)。二叉树以某种次序遍历使其变为一棵线索二叉树的过程称为二叉树的线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。前序线索二叉树、中序线索二叉树和后序线索二叉树二叉树前序二叉树编写课程设计报告1课题描述. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2需求分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3概要设计. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 4详细设计. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 5程序编码. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9 6程序调试与结果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 7算法分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18 8总结. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19 参考文献. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20  1 课题描述 本次试验通过对二叉树进行线索化后三种遍历的实现，三种遍历的过程必须找到序列中的第一个结点，然后依次找出结点后继直至其后继为空时为结束。 构建二叉树的过程中，通过先序构建，在构建初，对于线索的初值都赋值0，然