文档介绍：中北大学
数据结构
课程设计说明书
 
 
学生姓名:
学号:
学院:
电子与计算机科学技术学院
专业:
软件工程
题目:
线索二叉树的应用
成绩
 
指导教师:
秦品乐粱志剑
 
 
 
2009 年 6 月 25 日
通过设计掌握数据结构课程中学到的基本理论和算法并综合运用于理论实际问题中,,并采用恰当的设计方法和算法解决问题,同时训练学生进行复杂程序设计的技能和培养良好的程序设计习惯.
对于本实验,设计一个能够进行插入、删除、恢复操作的线索二叉树。主要目的是熟悉二叉树的二叉链表存储结构,以及线索的建立,在线索二叉树中进行插入、删除、恢复操作的相关算法的理解。特别是本程序中使用了一些递归的算法,要求对递归算法有更加深入的理解。
设计内容和要求
设计内容:
在TC环境下写一个程序,能够提供简单的DOS用户界面,启动程序后进入该界面,用户可以根据相应的提示进行功能上的选择。
程序中具体要实现的功能包括:1、二叉树的建立、中序遍历、线索化以及将其显示输出的功能模块;2、对建立好的线索二叉树实现删除结点操作模块(要求:在提示下输入一个结点的信息,在线索树中找到该结点并将其删除,同时要保证树的结构和线索)最后利用线索化的中序遍历将删除后的结果输出;3、对线索二叉树进行插入操作模块(要求:在提示下用户可以选择前插、后插操作,然后输入一个结点的信息,在线索树中找到该结点后,再输入要插入的结点信息,完成插入操作,同样要保证树的结构和线索)最后利用线索中序遍历,对插入后的结果进行输出;4、退出模块。
设计要求:
(1)最终的程序可运行。
(2)程序提供简单的DOS 界面,即建立、插入、删除、恢复等可以让操作人员选择进行。
本程序中涉及到了二叉树的建立、线索化、遍历、线索二叉树中插入、删除操等作。这些操作均基于二叉树的二叉链表的存储结构。结点中一共包含五个域,分别为:data,Ltag,Rtag,lchild,rchild ,含义分别为:树中结点值域(采用了char 型);左孩子标记域,用于标记左孩子是否为线索(规定:Ltag=Thread时左孩子表示为线索,Ltag=link时为左孩子存在);右孩子域,用于标记右孩子是否为线索(规定:Rtag=Thread时表示右孩子为线索,LRag=link时右孩子存在);左指针域,用于指向结点的左孩子或其前驱线索;右指针域,用于指向其右孩子或其后继线索。
RTag
rchild
Lchild
LTag
dataa
详细设计思想
功能模块结构图
线索二叉树的应用
Create模块
Delect模块
Insert模块
Quiet模块
在线索树中查找要删除的结点
删除查到的结点并中序输出结果
用户选择前插后插操作
在指定结点前插入输入的结点
在指定结点后插入输入的结点
退出系统
线索树中查询某结点
线索树中插入某结点
线索树中删除某结点
图:线索二叉树的应用功能模块结构图
用户界面图示
**********************************************************************
* e to use the system of Tree trail *
**********************************************************************
-----------------------------------you can choose the operation----------------------------------
| 1: bitree tree display and travel: |
| 2: bitree tree delect opearation: |
| 3: bitree tree insert operation: |
| 4: quit... |
------------------------------------------------------------------------------------------------------
please choose a operation:
如图:主菜单界面
**********************************************************