数据结构课程设计报告 - 二叉排序树（用顺序表结构存储）

淮阴工学院

数据结构课程设计报告

选题名称: 二叉排序树（二叉链表结构存储） 系（院）: 计 算 机 工 程 系 专 业: 计算机科学与技术 班 级: 计算机1091 姓 名: 黄磊 学 号: 1091301108 指导教师: 张亚红 周海岩 学年学期: 2010 ~ 2011 学年 第 1 学期

2010 年 12 月 31 日

设计任务书

课题 名称 二叉排序树：用顺序表结构存储 通过一周的课程设计，用二叉链表存储结构实现对二叉排序树的的创建，中序设计 遍历，并计算其平均查找长度，查找和某个删除结点等基本操作，达到巩固和目的 运用理论知识、锻炼实践能力、构件合理知识结构和提高程序设计能力的目的。 实验 环境 Windows2000 以上操作系统 Visual C++6.0以上编译环境 1、搜集二叉排序树方面的资料； 2、编写代码，实现二叉排序树的创建，中序遍历，计算其平均查找长度，任务 要求 查找和删除某个结点； 3、撰写课程设计报告； 4、参加答辩。 工作进度计划 序号 1 2 3 4 起止日期 2010.12.23~2010.12.27 2010.12.27~2010.12.29 2010.12.30 2010.12.30~2010.12.31 工 作 内 容 搜集二叉排序树方面的资料 编写代码，上机调试 撰写课程设计报告 答辩 指导教师（签章）： 2010 年 12 月 31 日

摘要：

数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。本次课程设计，程序中的数据采用“树形结构”作为其数据结构。而二叉搜索树又是一种特殊的二叉树。本课程设中的二叉排序树是基于二叉链表作存储结构的，一共要实现五项基本的功能。它们分别是二叉搜索树的创建、中序遍历、查找结点、删除结点和计算二叉排序树搜索成功时的平均查找长度。

关键词：二叉排序树；中序遍历；搜索结点；删除结点；平均查找长度

目 录

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

1.1课程设计题目、任务及要求 ························ 1 1.2课程设计思想 ······························ 1

2概要设计 .................................................................................................................... 2

2.1 二叉排序树的定义 ···························· 2 2.2二叉链表的存储结构 ··························· 2 2.3建立二叉排序树 ····························· 2 2.4二叉排序树的生成过程 ·························· 3 2.5中序遍历二叉树 ····························· 3 2.6二叉排序树的查找 ···························· 3 2.7二叉排序树的插入 ···························· 4 2.8平均查找长度 ······························ 4

3详细设计和实现 ........................................................................................................ 4

3.1主要功能模块设计 ···························· 4 3.2主程序设计 ······························· 5

4调试与操作说明 ...................................................................................................... 12

4.1程序调试 ······························· 12 4.2程序操作说明 ····························· 12

总 结 ................................................................................................................. 16 致 谢 ................................................................................................................. 17 参 考 文 献 ............................................................................................................... 18

1需求分析

1.1课程设计题目、任务及要求

二叉排序树。用二叉链表作存储结构

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

(3)计算二叉排序树T查找成功的平均查找长度,输出结果；

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

1.2课程设计思想

建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找成功则不应再插入原树，否则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。

对二叉排序树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。由于二叉排序树自身的性质，左子树小于根结点，而根结点小于右子树，所以中序遍历的结果是递增的。

计算二插排序树的平均查找长度时，仍采用类似中序遍历的递归方式，用s记录总查找长度，j记录每个结点的查找长度，s置初值为0，采用累加的方式最终得到总查找长度s。平均查找长度就等于s/i(i为树中结点的总个数)。

删除结点函数，采用边查找边删除的方式。如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论：

1、该结点左右子树均为空； 2、该结点仅左子树为空； 3、该结点仅右子树为空； 4、该结点左右子树均不为空。

1

2概要设计

2.1 二叉排序树的定义

二叉排序树是一种动态树表。

二叉排序树的定义：二叉排序树或者是一棵空树， 或者是一棵具有如下性质的二叉树：

（1）每个结点都有一个作为搜索依据的关键码（key），所有结点的关键码互不

相同；

（2） 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； （3） 若它的右子树非空，则右子树上所有结点的值均大于根结点的值； （4） 左、右子树本身又各是一棵二叉排序树。

2.2二叉链表的存储结构

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

2.3建立二叉排序树

从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。

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

（1） 若为空树（p=nil），动态生成一个结点，其数据域为当前待插入元素

b，左、右指针域为“空”，p指向该结点。

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

如果b

左、右子树的插入方式与二叉排序树的插入方式相同。 不断调用上述的插入过程，直到所有待排序序列均排入后，就形成一棵二叉排序树。

由此可见，建立二叉排序树就是多次调用二叉排序树的插入算法。

2

2.4二叉排序树的生成过程

二叉排序树的生成，采用递归方式的边查找边插入的方式。如图：

图2.4.1 二叉排序树生成流程图

空树 否 是 插入 插入结点 初始化 在左子树中查找 否 在右子树中查找 是 插入 插入 2.5中序遍历二叉树

中序遍历二叉树算法的框架是： 若二叉树为空，则空操作；否则

（1） 中序遍历左子树（L）； （2） 访问根结点（V）； （3） 中序遍历右子树（R）。

中序遍历二叉树也采用递归函数的方式，先访问左子树,然后访问根结点,最后访问右子树.直至所有的结点都被访问完毕。

2.6二叉排序树的查找

在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设我们想要在二叉排序树中查找关键码为x的元素，查找过程从根结点开始。如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键码进行比较；如果给定值等于根

3

结点的关键码，则查找成功，返回查找成功的信息，并报告查找到的结点地址。如果给定值小于根结点的关键码，则继续递归查找根结点的左子树；否则，递归搜索根结点的右子树。

2.7二叉排序树的插入

为了向二叉排序树中插入一个新元素，必须先检查这个元素是否在树中已经存在。所以在插入之前，先使用查找算法在树中检查要插入的元素有还是没有。如果搜索成功，说明树中已经有这个元素，不再插入；如果搜索不成功，说明树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。

插入过程：若二叉排序树为空，则待插入结点*s作为根结点插入到空树中； 当非空时，将待插结点关键字s->data和树根关键字subtree->data进行比较， 若s->data= subtree-> data,则无须插入，若s-> data data,则插入到根的左子树中，

若s-> data > subtree-> data,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。

2.8平均查找长度

计算二叉排序树的平均查找长度时，采用类似先序遍历的递归方式，用count记录所有结点的总深度，deep记录每个结点的深度，count置初值为0，采用累加的方式最终得到所有结点总深度count。平均查找长度就等于count/i(i为树中结点的总个数)。

3详细设计和实现

3.1主要功能模块设计

程序主要设计了五个功能：首先是创建二叉排序树，完成后出现任务菜单，菜单中设计了四个模块：退出，中序遍历，搜索，删除结点和计算平均查找长度，另外还有一个附加功能计算所有结点的个数，用来计算平均查找长度。

主函数流程如下：

4

创建二叉排序树 Switch(0) 否 Switch(1) 否 Switch(2) 否 Switch(3) 否 Switch(4) 是 平均搜索长度 是 删除结点 是 是 搜索结点 是 是 中序遍历 是 是 Exit(0)退出 是

否 图3.1.1主函数流程图 3.2主程序设计

void main () {

int deep;

cout<<\输入一组数据建立二叉搜索树，以0结束\BinaryTreebr(0);

BinTreeNode*subtree=br.GetRoot (); int choicenumber;

char flag; //判断是否还要继续进行 int number; int number2; while(1) {

show(); //显示主要功能

5

cout<<\请选择你要进行的操作：1~5\cin>>choicenumber; switch(choicenumber) { case 0:

exit(0);break;

case 1:

cout<<\显示树的结点：\br.print ();break;

case 2:

cout<<\结点个数为：\

cout<<\ \

case 3:

cout<<\输入要查找的数：\cin>>number;

if(br.search (number)==NULL)

cout<<\没有找到\

else

cout<<\找到\break;

case 4:

cout<<\输入你要删除的结点:\cin>>number2;

if(br.search (number2)!=NULL) { } else

cout<<\你要删除的结点不存在!\br.remove (number2);

cout<<\删除结点后的二叉搜索树为：\br.print ();

break;

6

if(key==subtree->data)

return subtree;

else if(keydata)return search(key,subtree->leftChild); //若比该结点小，那就向它的左子树继续搜索

else if(key>subtree->data)return search(key,subtree->rightChild); ////若比该结点大，那就向它的右子树继续搜索

else return subtree;

};

// ******* 输出二叉树结点数 ******** template

int BinaryTree::Size (BinTreeNode*subtree) { //计算以*subtree为根的二叉树的结点数 if(subtree==NULL)

return 0; else

return 1+Size(subtree->leftChild)+Size(subtree->rightChild); }; #endif

4调试与操作说明

4.1程序调试

图4.1.1 调试界面

4.2程序操作说明

1）输入一组数列，以结0结束：

12

//左子树的

图4.2.1运行界面一

2）中序遍历：

图4.2.2运行界面二

3）计算搜索成功时的平均查找长度：

13

图4.2.3运行界面三

4）查找结点：

图4.2.4运行界面四

5）查找不存在的结点

图4.2.5运行界面五

6）删除已有结点：

14

图4.2.6运行界面六

7）删除结点后的平均搜索长度：

图4.2.7运行界面七

15

总 结

这次课程设计使我对数据结构认识深刻了许多，其中最深刻的是我理解了用二叉链表结构存储实现二叉排序树，同时也加深了对二叉树的理解。本课程设计实现了二叉排序树的创建、中序遍历、计算二叉排序树的平均查找长度和删除二叉排序树中某个结点,。在进行搜索时，还可以采用更好的搜索结构即动态搜索结构。当没有找到时，可以将其插入，而不是仅仅提示未找到。在进计算查找成功时的平均查找长度，使用递归的方法虽然短小，但很难理解，可以采用层次遍历来统计所有结点的深度之和，这样就更容易理解。在此课题中，我遇到最大的一个问题就是如何求搜索成功时平均搜索长度？最后通过加上deep来记录每一结点的深度给解决啦，可是又出现了另外一个新的问题，当删除结点后再求平均搜索长度却又错啦？最后通过单步调试发现，当进行完一次计算平均搜索长度后，count(用来记录所有结点深度和)会随着下一次计算时同步增长。那就必须要在每进行完一次计算后，给count做清零处理！于是我就在类中加了一个对count 清零处理的函数，int GetCount(){ count=0；return count；} 。从而解决了这个最大的难题。通过一周的课程设计，我已经会用二叉链表存储结构实现对二叉排序树的的创建，中序遍历，并计算其平均查找长度，查找和某个删除结点等基本操作。

但我同时也发现了自己许多不足之处 。

首先，对数据结构的掌握还不够。虽然完成了程序，但是只用到了基本的结点以及链表，在数据结构的选择上避重就轻，覆盖面较小，不能很好的体现各种数据结构的掌握度，同时也缺少了适当的锻炼，在这方面还需要自己主动去提高。

其次，在程序整体的设计上还不够完善，各模块可以适当增加内容，界面还可以更加的人性化些，这样整个程序才具有更强的美观性与实用性。

总而言之，这次课程设计给了我很大启发，我明白了，不管遇到什么问题，只要抓住根源，不气馁，从不同方面去攻破它，终究会成功，生活也是如此。

16

本文来源：https://www.bwwdw.com/article/ah6a.html