用顺序和二叉链表作存储结构实现二叉排序树全代码

安徽新华学院

数据结构课程设计报告

题目：用顺序和二叉树存储结构实现二叉树排序 学院：信息工程 专业：信息与计算科学 班级：12信科本一班 姓名：李智 学号：1242155110 指导教师：李明 设计时间： 2013-12-16至2013-12-30

数据结构课程设计

课程设计任务书

一．设计任务

研究关于如何创建二叉排序树并对树进行遍历，查找和删除等操作，同时关注用顺序和二叉链表作存储结构带来的区别。

二．设计要求

（1）. 利用顺序存储和链式存储两种算法计算实现二叉搜索树的创建。

（2）. 利用顺序存储和链式存储两种算法计算实现中序遍历。

（3）. 利用顺序存储和链式存储两种算法计算实现查找结点。

（4）. 利用顺序存储和链式存储两种算法计算实现删除结点。

三．设计期限

2013-12-16至2013-12-30

数据结构课程设计

前言

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。本课程设计中的二叉排序树，可以用顺序存储和链式存储两种算法计算。本课程设中的二叉排序树，一共要实现四项基本的功能。它们分别是二叉搜索树的创建、中序遍历、查找结点和删除结点。

二叉树是树形结构的一个重要的类型，二叉树是n（n>=0）个结点的有限集，它或者是空集（n=0），或者由个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。 二叉树的存储结构和算法比较简单，特别适合计算机处理。即使一般形式的树也可简单的转换为二叉树。二叉树的顺序存储结构是把二叉树的所有结点，按照一定的次序顺序，存储到一片连续的存储单元中。遍历二叉树就是沿某有前序遍历、中条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。在遍历方案中主要序遍历、后序遍历。 现实中有许多应用到二叉树的例子，所以我们要把理论与现实结合起来。在学习中主要掌握怎么求二叉树的高度、叶子结点个数、总结点个数以及熟练三种遍历的方法。

数据结构课程设计

目 录

1 需求分析 ................................................................................................................................ 1 1.1 问题的提出 ..................................................................................................................... 1 1.2任务与分析 ...................................................................................................................... 1 2 总体设计 ................................................................................................................................ 1 2.1二叉排序树的建立 .......................................................................................................... 1 2.2二叉排序树的中序遍历 .................................................................................................. 2 2.3二叉排序树中元素的查找 .............................................................................................. 2 2.4二叉排序树中元素的删除 .......................................................................................................... 2 2. 5 总体设计流程图

3 详细设计 .............................................................................................. 错误！未定义书签。 3.1 中序遍历模块 ................................................................................................................. 7 3.2 删除模块 ......................................................................................................................... 7 4编码与调试 ............................................................................................................................. 9 4.1 顺序存储 ....................................................................................................................... 10 4.2 二叉链表存储 ............................................................................................................... 14 5 总结 ...................................................................................................................................... 17 总 结 ................................................................................................... 错误！未定义书签。 心得体会 ............................................................................................................................... 18 参考文献 .................................................................................................................................. 19 全部代码 .................................................................................................................................. 20 二叉链表结构C.................................................................................................................... 20 二叉链表结构C++ ............................................................................................................... 24 顺序存储结构C.................................................................................................................... 27

1 需求分析

1.1 问题的提出

研究关于如何创建二叉排序树并对树进行遍历，查找和删除等操作，同时关注用顺序和二叉链表作存储结构带来的区别。

1.2任务与分析

用顺序和二叉链表作存储结构实现二叉排序树：

（1）以回车('\\n')为输入结束标志,输入数列L，生成一棵二叉排序树T； （2）对二叉排序树T作中序遍历，输出结果；

（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。

2 总体设计

2.1二叉排序树的建立

建二叉树的结点至少应当包含三个域，分别存放结点的数据data，左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针，它指向二叉树的根结点，其作用是当作树的访问点

从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。 根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点指针，b为当前待插入元素，其过程可以描述为：

若为空树（p=nil），动态生成一个结点，其数据域为当前待插入元素b，左、右指针域为“空”，p指向该结点。

若非空树，比较b与根结点数据data（p） 如果b

左、右子树的插入方式与二叉排序树的插入方式相同。

不断调用上述的插入过程，直到所有待排序序列均排入后，就形成一棵二叉排序树。 由此可见，建立二叉排序树就是多次调用二叉排序树的插入算法。

-1-