淮阴工学院

Project1课程设计报告

选题名称:二叉排序树：用顺序表结构存储

系（院）:      计算机工程学院        

专    业:        软件工程        

班    级:         软件1092          

姓    名:  单重阳   学  号:1091305206

指导教师:    殷路  张亚红    张勇军  冯万利      

学年学期:      20## ~ 20## 学年 第  1  学期    

      2010        年     12 月   27 日

设计任务书

摘要：

数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。本次课程设计，程序中的数据采用“树形结构”作为其数据结构。具体采用的是“二叉排序树”，并且使用“一维数组”来作为其存储结构。一维数组顺序表存储结构是用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素；本课程设计实现了二叉排序树的创建、中序遍历、计算二叉排序树的平均查找长度和删除二叉排序树中某个结点。

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

目    录

1需求分析... 1

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

1.2课程设计思想·· 1

1.3软硬件运行环境及开发工具·· 1

2概要设计... 2

2.1 二叉排序树的定义·· 2

2.2一维数组的存储结构·· 2

2.3建立二叉排序树·· 2

2.4二叉排序树的生成过程·· 2

2.5中序遍历二叉树·· 3

2.6二叉排序树的查找·· 3

2.7二叉排序树的插入·· 4

2.8平均查找长度·· 4

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

3.1主要功能模块设计·· 5

3.2主程序设计·· 6

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

4.1程序调试·· 7

4.2程序操作说明·· 8

总          结... 10

致          谢... 11

参 考 文 献... 12

1需求分析

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

二叉排序树。用顺序表(一维数组)作存储结构 

(1)以回车('\n')为输入结束标志,输入数列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.3软硬件运行环境及开发工具

Windows2000以上操作系统、Microsoft Visual C++ 6.0

2概要设计

2.1 二叉排序树的定义

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

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

⑴ 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；

⑵ 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；

⑶ 左、右子树本身又各是一棵二叉排序树。

2.2一维数组的存储结构

建立二插排序树，首先用一个一维数组记录下读入的数据，然后再用边查找边插入的方式将数据一一对应放在完全二叉树相应的位置，为空的树结点用“0” 补齐。

2.3建立二叉排序树

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

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

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

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

如果b＜data(p), 将b插入左子树中；

如果b≥data（p），将b插入右子树中；

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

不断调用上述的插入过程，直到所有待排序序列均排入后，就形成一棵二叉排序树。

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

2.4二叉排序树的生成过程

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

 

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

2.5中序遍历二叉树

中序遍历二叉树算法的框架是：

若二叉树为空，则空操作；否则

（1）    中序遍历左子树（L）；

（2）    访问根结点（V）；

（3）    中序遍历右子树（R）。

中序遍历二叉树也采用递归函数的方式，先访问左子树2i,然后访问根结点i,最后访问右子树2i+1.先向左走到底再层层返回，直至所有的结点都被访问完毕。

2.6二叉排序树的查找

在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较叛等的过程。它可以是一个递归的过程。假设我们想要在二叉排序树中查找关键码为x的元素，查找过程从根结点开始。如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键码进行比较；如果给定值等于根结点的关键码，则查找成功，返回查找成功的信息，并报告查找到的结点地址。如果给定值小于根结点的关键码，则继续递归查找根结点的左子树；否则，递归搜索根结点的右子树。

2.7二叉排序树的插入

在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。

为了向二叉排序树中插入一个新元素，必须先检查这个元素是否在树中已经存在。所以在插入之前，先使用查找算法在树中检查要插入的元素有还是没有。如果搜索成功，说明树中已经有这个元素，不再插入；如果搜索不成功，说明树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。
   插入过程：若二叉排序树为空，则待插入结点*S作为根结点插入到空树中；
   当非空时，将待插结点关键字S->key和树根关键字t->key进行比较，
   若s->key = t->key,则无须插入，若s->key< t->key,则插入到根的左子树中，
   若s->key<> t->key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。

2.8平均查找长度

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

    假设在含有n(n>=1)个关键字的序列中，i个关键字小于第一个关键字，n-i-1个关键字大于第一个关键字，则由此构造而得的二叉排序树在n个记录的查找概率相等的情况下，其平均查找长度为：

          ASL(n,i)=[1+i*(P(i)+1)+(n-i-1)(P(n-i-1)+1)]/n

    其中P(i)为含有i个结点的二叉排序树的平均查找长度，则P(i)+1为查找左子树中每个关键字时所用比较次数的平均值，P（n-i-1）+1为查找右子树中每个关键字时所用比较次数的平均值。又假设表中n个关键字的排列是“随机”的，即任一个关键字在序列中将是第1个，或第2个，…，或第n个的概率相同，则可对上式从i等于0至n-1取平均值。最终会推导出：

          当n>=2时，ASL(n)<=2(1＋1/n)ln(n)

由此可见，在随机的情况下，二叉排序树的平均查找长度和log（n）是等数量级的。

另外，含有n个结点的二叉排序树其判定树不是惟一的。对于含有同样一组结点的表，由于结点插入的先后次序不同，所构成的二叉排序树的形态和深度也可能不同。

3详细设计和实现

3.1主要功能模块设计

程序主要设计了五个功能：首先是创建二叉排序树，完成后出现任务菜单，菜单中设计了四个模块：退出，中序遍历，计算平均查找长度和删除结点。

主函数流程如下：

 

图3.1.1主函数流程图

3.2主程序设计

void main()

{

    BST   T;

    int   crew[N];

    int   i=0;

    int   num,ch=0,j;

    cout<<"请输入以数字0为结束标志的一组数列:"<<endl;

    do{

       cin>>num;

        if(!num) cout<<"输入完成!"<<endl;

        else { crew[i]=num; i++;}

    }while(num);

    T=create(crew,i);

    cout<<"\n\n------------主程序菜单------------\n";   /*主程序菜单*/

    cout<<"\n 0:  退出" ;

    cout<<"\n 1:  中序遍历";

    cout<<"\n 2:  计算平均查找长度";

    cout<<"\n 3:  删除结点";      cout<<"\n\n--------------------------------------------\n";

        while(ch==ch)

    {

       cout<<"\n 选择命令:";

        cin>>ch;

        switch(ch)

              {

            case 0:   exit(0);         /*0－退出*/

            case 1:  cout<<"中序遍历为:\n";

                                      cout<<"                            ";

                      inordertraverse(T,1);/*1－中序遍历*/

                      break;

            case 2:   j=0;

                      computeASL(T,1,&j,0); /*2－计算平均查找长度*/

                      cout<<" ASL(平均查找长度)="<<j<<"/"<<i<<"="<<j/i;

                      break;

            case 3:   cout<<"请输入需要删除的结点:";

                      cin>>num;/*3－删除某个结点*/

                      j=search(T,num,1);

                      if(j)

                      {

                          T=remove(T,num);

                          cout<<"\n 删除成功! \n  ";

       cout<<" 新的中序遍历为: \n";

                                               cout<<"                       ";

                          inordertraverse(T,1);

                          i--;

                       }

                       else 

       cout<<"  查找不到"<<num<<"这个结点";

                       break;   

            default:  cout<<" 请重新输入!\n"<<endl<<endl;

                       break; /*输入无效字符*/

        }

    }

}

4调试与操作说明

4.1程序调试

图4.1.1 调试界面

在程序调试过程当中，编译时并没有报错，但是运行时总是出错，在查阅资料和老师的帮助下，发现程序未对数组初始化。添加数组初始化代码：

T.data=(int *)malloc(N*sizeof(int));

4.2程序操作说明

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

图4.2.1运行界面一

2）中序遍历：

图4.2.2运行界面二

3）计算平均查找长度：

图4.2.3运行界面三

3）删除已有结点：

图4.2.4运行界面四

总    结

这次课程设计是我学会了用顺序表结构存储实现二叉排序树，具体采用的是“二叉排序树”，并且使用“一维数组”来作为其存储结构。一维数组顺序表存储结构是用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素；本课程设计实现了二叉排序树的创建、中序遍历、计算二叉排序树的平均查找长度和删除二叉排序树中某个结点,通过一周的课程设计，我已经会用顺序表存储结构实现对二叉排序树的的创建，中序遍历，并计算其平均查找长度，查找和某个删除结点等基本操作。

致    谢

本次数据结构课程设计让我收获很多，我从指导老师身上学到了很多东西。他们认真负责的工作态度，严谨的治学精神和深厚的理论水平都使我收益匪浅。无论在理论上还是在实践中，都给与我很大的帮助，使我得到很大的提高，这对于我以后的工作和学习都有一种巨大的帮助，在此感谢他耐心的辅导。在撰写论文阶段，老师审阅我们的论文，提出了许多宝贵意见，没有他的指导，我们就不能较好的完成课题设计的任务。

另外，我还要感谢在这几年来对我有所教导的老师，他们孜孜不倦的教诲不但让我学到了很多知识，而且让我掌握了学习的方法，更教会了我做人处事的道理，在此表示感谢。同时，在编程过程中还有我班同学也给了我不少帮助，这里一并表示感谢。

参 考 文 献

1.魏雪萍.新编Word2003入门与提高.北京:人民邮电出版社,2005

2.王宏生.数据结构.北京:国防出版社,2006.1

3.潭浩强.程序设计.北京：清华大学出版社，2000

4.严蔚敏，吴伟民.数据结构.北京：清华大学出版,2001

5.殷人昆.数据结构.北京：清华大学出版社，2004

6.王晓东.数据结构与算法设计．电子工业出版社 2002

7.陈慧南．数据结构与算法 C++ 语言描述．高等教育出版社 2005

8.窦延平等.数据结构与算法 C++．上海交通大学出版社 2005

指导教师评语