数据结构与算法课程设计说明书

线索二叉树的基本操作

数学与计算机学院 课程设计说明书

课 程 名 称: 数据结构与算法课程设计 课 程 代 码: 6014389

题 目: 线索二叉树的基本操作 年级/专业/班:

学 生 姓 名: 学 号:

开 始 时 间: 2013 年 12 月 18 日 完 成 时 间: 2013 年 12 月 28 日 课程设计成绩：

学习技术完成情况(20) 创新（5） 态度及平水平与实时成绩（20） 际能力（20） 说明书（计算书、图纸、分析报告）撰写质量（35） 总 分（100） 指导教师签名： 年 月 日

线索二叉树的基本操作

目 录

1 需求分析 ............................................................................................................ 1

1.1任务与分析 .............................................................................................. 1 1.2测试数据 .................................................................................................. 2 2 概要设计 ............................................................................................................ 3

2.1 模块划分 ................................................................................................. 3 2.2模块中的层次图 ...................................................................................... 3 3 详细设计 .......................................................................................................... 4

3.1结构体设计 .............................................................................................. 4 3.2创建二叉树 .............................................................................................. 4 3.3二叉树线索化 .......................................................................................... 5 3.4二叉树中插入结点 .................................................................................. 6 3.5删除结点函数 .......................................................................................... 8 3.6查找前驱后继函数 ................................................................................ 11 4 调试分析 .......................................................................................................... 12 5 用户使用说明 ................................................................................................ 12 6 测试结果 ........................................................................................................ 12

6.1新建二叉树 ............................................................................................ 12 6.2中序遍历 ................................................................................................ 13 6.3查找前驱 ................................................................................................ 13 6.4查找后继 ................................................................................................ 14 6.5删除结点 ................................................................................................ 14 6.6插入左孩子 ............................................................................................ 15 6.7插入右孩子 ............................................................................................ 15 6.8退出 ........................................................................................................ 16 结 论 .................................................................................................................. 17 致 谢 .................................................................................................................. 18 参考文献 .............................................................................................................. 19

线索二叉树的基本操作

摘 要

首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。其次是概要设计，说明模块的划分以及模块间的层次关系，然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。

关键词：线索化,中序遍历,插入，删除，查找

线索二叉树的基本操作

引 言

数据结构是计算机专业重要的专业基础课程与核心课程之一，在计算机领域应用广泛，计算机离不开数据结构。数据结构课程设计为了能使我们掌握所学习的知识并有应用到实际的设计中的能力，对于掌握这门课程的学习方法有极大的意义。本课程设计的题目为“线索二叉树的基本操作”，完成将二叉树转化成线索二叉树，采用中序线索二叉树的操作。本课程设计采用的编程环境为Microsoft Visual Studio 2008。

1 需求分析

当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右儿子结点的指针，所以从任一结点出发只能直接找到该结点的左、右儿子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。如果在每个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率。

我们可以证明：在n个结点的二叉链表中含有n+1个空指针。因为含n个结点的二叉链表中含有2n个指针，除了根结点，每个结点都有一个从父结点指向该结点的指针，因此一共使用了n-1个指针，所以在n个结点的二叉链表中含有n+1个空指针。

因此可以利用这些空指针，存放指向结点在某种遍历次序下的前驱和后继结点的指针。这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded Binary Tree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

1.1任务与分析

任务：

建立一棵二叉树（用户自行输入二叉树，用“#”表示空格，按回车键结束），将其线索化，并实现以下功能：

1)遍历二叉树（本程序使用中序遍历方法） 2)在二叉树中插入一个结点

1