青岛理工数据结构课程设计线索二叉树.docVIP

青岛理工大学 数据结构课程设计报告 题目： 线索二叉树的应用 院（系）： 计算机工程学院 学生姓名: 班级： 学号: 起迄日期: 2015.07.13-2015.07.24 指导教师: 李传斌 杨鑫 任务书 一、《数据结构课程设计》的目标达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，培养基本的良好的程序设计技能能力为整个专业的学习以及软件设计水平的提高打下良好的基础二、内容 线索二叉树的应用 实现线索树建立、插入、删除、。 三设计要求1、学生必须仔细阅读《数据结构课程设计，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。 2、学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时向教师汇报。 3、课程设计按照教学要求需要两周时间完成，学院安排上机时间学生不得缺席。? 　、设计语言 一、需求分析 1.问题描述 题目需要完成如下要求：实现线索树建立、插入、删除、 2.基本功能 实现本程序需要实现以下几个功能： 建立线索二叉树。 实现线索二叉树的插入。 实现线索二叉树的删除。 实现线索二叉树的中序遍历输出。 二、 概要设计 1.设计思路： 在这个题目中，要解决的任务是：实现线索树建立、插入、删除、的实现 线索链表的结点结构 线索链表中的结点结构为： 建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需添加虚结点，使其成为完全二叉树。 关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。可以设置一个队列，该队列是一个指针类型的数组，保存已输入的结点地址。 操作：（1）令队头指针front指向其孩子结点当前输入的建立链接的父结点，队尾指针rear指向当前输入的结点，初始：front=1,rear=0; （2）若rear为偶数，则该结点为父结点的左孩子；若rear为奇数，则该结点的右孩子；若父结点和孩子结点为虚结点，则无需链接。 （3）若父结点与其两个孩子结点的链接完毕，则令front=front+1,使front指向下一个等待链接的父结点。 二叉树的中序线索化算法与中序遍历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL），而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋，而*p是*pre的后继。 3.软件结构设计： 建立二叉树 Bithptr *CreatTree() 线索化二叉树 PreThread(Bithptr *r) 线索二叉树的插入 Insert(Bithptr *root) 线索二叉树的删除 Bithptr * DeleteNode(Bithptr *t) 中序遍历二叉树 Inorder(Bithptr *T) 三、 详细设计 1. 定义程序中所有用到的数据及其数据结构，基本操作 typedef struct node{ //定义数据结构 int ltag,rtag; //表示child域指示该结点是否孩子 char data; //记录结点的数据 struct node *lchild,*rchild; //记录左右孩子的指针 }Bithptr; 2．主函数和其他函数的算法； 主函数： void main() { Bithptr *T; int i; T=CreatTree(); i=1; while(i) { system(cls); printf(**********************************************************\n); printf(\n); printf(\t\t\t 线索二叉树的应用\n); printf(\n); printf(********************************************************\n); printf(\t\t\t1 中序线索化二叉树\n); printf(\t\t\t2 进行插入操作