线索二叉树课程设计说明书格式.doc

中 北 大 学 课程设计说明书 学 院、系： 软件学院 专 业： 软件工程 班 级： 15140X04 学 生 姓 名： 张航 学 号： 1514040423 设 计 题 目： 线索二叉树的应用 起 迄 日 期: 2016年12月16日~2016年12月29日 指 导 教 师: 付东来 日期: 2016年12月29日 1 设计目的 《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 2 任务概述 设计内容： （1）建立线索二叉树，实现插入、删除操作。 （2）线索二叉树的遍历（本程序中使用中序遍历方法） 设计要求： 实现线索树建立、插入、删除、恢复线索 任务分析： 该任务是关于线索二叉树的运算，其中的基本运算应基于二叉树，但又有所不同，首先应了解问题有： （1）线索二叉树如何建立：是通过二叉树来实现线索化，还是直接进行线索化的输入。若由二叉树建立而来，该二叉树应如何输入，对具体的二叉树应该使初次使用者明白使用的格式。 （2）该程序重点内容是有关二叉树的插入、删除和查找前驱后继，在进行具体操作时，该如何实现查找到相应结点，线索应该如何改变才能不破坏线索二叉树的结构。重点在于插入删除是分清楚插入删除位置的双亲结点与被插入删除的结点的孩子关系。 3 模块划分 （1）定义数据结构模块： typedef struct BiThrNode{ ElemType data; struct BiThrNode *lchild,*rchild; int LTag,RTag; }BiThrNode,*BiThrTree; （2）功能函数： 二叉树的建立函数：void CreateBiTree(BiThrTree T) 询二叉树深度函数：int Depth(BiThrTree T) 带头结点的二叉树中序线索化函数：void InOrderThreading(BiThrTree Thrt,BiThrTree T) 以结点T为根的子树中序线索化：void InThreading(BiThrTree T) 中序遍历函数：void InOrderTraverse_Thr(BiThrTree Thrt) 查找某结点函数：BiThrTree Search(BiThrTree T,ElemType key) 查找某结点函数：BiThrTree SearchPre(BiThrTree point,BiThrTree child) 插入函数：Status InsertTree(BiThrTree T) 删除函数：Status DeleteTree(BiThrTree T) 主函数：main() 整体结构图： 开 始 开 始 创建二叉树 线索化二叉树 Main( ) 打印二叉树 插入结点 删除结点 4 主要函数说明及其N-S图 4.1详细设计思想 建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需添加虚结点，使其成为完全二叉树。 二叉树的中序线索化算法与中序遍历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。该算法应附设一个指针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）