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

(完整word版)用顺序和二叉链表作存储结构实现二叉排序树
河南城建学院
课程设计报告书

专 业：计算机科学与技术
课程设计名称：用顺序和二叉链表作存储结构实现二叉排序树
题 目：
班 级：
学　　　　号：
姓　　　　名：
同 组 人 员:
指 导 老 师：
完 成 时 间：

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

目录
目录 2
第一章 课程设计题目及要求 3
1.1 C语言简介 3
1.2 课程设计题目 3
1.3 课程设计要求 3
第二章 算法思想 4
2.1 二叉排序树的定义 4
2.2 二叉排序树的实现 4
2.2.1 建立二叉排序树 5
2.2.2 二叉排序树的中序遍历 5
2.2.3 二叉排序树中元素的查找 5
2.2.4 二叉排序树中元素的删除..........................................................................5
第三章 算法实现 7
3.1 程序设计思想 7
3.2 程序模块 7
3.3 流程图 10
3.4 源程序代码 11
第四章 测试与分析 17
4.1 程序调试 17
4.2 调试结果分析 19
总 结 20
心得体会 21
参考文献 22

第一章 课程设计题目及要求
1.1 C/ C ++语言简介
C语言是一种结构化语言。它层次清晰，便于按模块化方式组织程序，易于调试和维护。Ｃ语言的表现能力和处理能力极强。它不仅具有丰富的运算符和数据类型，便于实现各类复杂的数据结构。它还可以直接访问内存的物理地址，进行位(bit)一级的操作。由于Ｃ语言实现了对硬件的编程操作，因此Ｃ语言集高级语言和低级语言的功能于一体。既可用于系统软件的开发，也适合于应用软件的开发。C是C++的基础，C++语言和Ｃ语言在很多方面是兼容的，C++程序员可以利用C++与C的兼容性而直接并有效的使用大量现成的程序库，从而开发出更简洁更高效的系统。
1.2 课程设计题目
用顺序和二叉链表作存储结构实现二叉排序树：
（1）以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；
（2）对二叉排序树T作中序遍历，输出结果；
（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。
1.3课程设计要求
在处理题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。对于稍复杂的程序设计，要充分利用模块化程序设计方法，自顶向下，逐步细化，在整体思路确定的情况下，考虑所需模块数，各模块完成功能以及模块之间的数据联系和调用关系。给出主要模块的算法描述，用流程图或伪代码表示。说明：在设计的过程中，步骤1---步骤4往往是反复进行，在后续步骤中发现问题，往往需要从头重新分析、设计。

第二章 算法思想

2.1二叉排序树的定义

二叉排序树的定义：二叉排序树或者是一棵空树， 或者是一棵具有如下性质的二叉树：
（1）每个结点都有一个作为搜索依据的关键码（key），所有结点的关键码互不相同；
（2） 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
（3） 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
（4） 左、右子树本身又各是一棵二叉排序树
2.2二叉排序树的实现

2.2.1建立二叉排序树

建二叉树的结点至少应当包含三个域，分别存放结点的数据data，左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针，它指向二叉树的根结点，其作用是当作树的访问点
从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。
根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点指针，b为当前待插入元素，其过程可以描述为：
若为空树（p=nil），动态生成一个结点，其数据域为当前待插入元素b，左、右指针域为“空”，p指向该结点。
若非空树，比较b与根结点数据data（p）
如果b<data(p), 将b插入左子树中；
如果b≥data(p)，将b插入右子树中；
左、右子树的插入方式与二叉排序树的插入方式相同。
不断调用上述的插入过程，直到所有待排序序列均排入后，就形成一棵二叉排序树。
由此可见，建立二叉排序树就是多次调用二叉排序树的插入算法。

2.2.2二叉排序树的中序遍历

中序遍历二叉树算法的框架是：
若二叉树为空，则空操作；否则
中序遍历左子树（L）；
访问根结点（V）；
中序遍历右子树（R）。
中序遍历二叉树也采用递归函数的方式，先访问左子树,然后访问根结点,最后访问右子树.直至所有的结点都被访问完毕

2.2.3二叉排序树中元素的查找

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

2.2.4二叉排序树中元素的删除

对于二叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。假设在二叉排序树上被删除结点为*p（指向结点的指针是p），其双亲结点为*f（结点指针为f），且不失一般性，可设*p是*f的左孩子，若*p结点为叶子结点，即p和l均为空，只需修改其双亲结点指针即可。若*p结点只有左子树或者只有右子树，只要令左子树或右子树直接成为其双亲结点即可。若左子树和右子树都不为空，令*p的直接前驱替代*p，然后从二叉排序树中删除它的直接前驱，即可。

第三章 算法实现
3.1 程序设计思想

程序主要设计了四个功能：首先是创建二叉排序树，完成后出现任务菜单，以数字代码确定，二叉排序树的中序遍历和查找，删除步骤，最后完成，结束。

3.2程序模块

本程序设计采用树形结构实现二叉排序树
建立二叉排序树，输入数据，开始查找，查找不成功或查找成功：
typedef struct Tnode{
    int   data;                      
struct  Tnode    *lchild,*rchild;    
    }*node,BSTnode;
searchBST(node t,int key,node f,node *p)
{
    if(!t)
{*p=f;return (0);}        
else
  if(key==t->data)    {*p=t;return (1);}
    else
  if(key<t->data)   searchBST(t->lchild,key,t,p);  
else  
searchBST(t->rchild,key,t,p);
}
对二叉排序树进行中序遍历：
 inorderTraverse(node *t)  
{
    if(*t){
            if(inorderTraverse(&(*t)->lchild))          
              printf("%d  ",(*t)->data);  
                if(inorderTraverse(&(*t)->rchild));
            }
return(1) ;
}
删除节点
node Delete(node t,int  key)   /*删除函数*/
{
    node    p=t,q=NULL,s,f;
   while(p!=NULL)   /*查找要删除的点*/
    {
        if(p->data==key)
   break;
        q=p;
        if(p->data>key)   p=p->lchild;
        else
   p=p->rchild;
    }
    if(p==NULL)
  return  t;    /*查找失败*/
    if(p->lchild==NULL)     /*p指向当前要删除的结点*/
    {
        if(q==NULL)   t=p->rchild;  /*q指向要删结点的父母*/
        else
   if(q->lchild==p)    q->lchild=p->rchild;  /*p为q的左孩子*/
                else
     q->rchild=p->rchild;/*p为q的右孩子*/
        free(p);
    }
    else{           /*p的左孩子不为空*/
        f=p;
        s=p->lchild;
        while(s->rchild)   /*左拐后向右走到底*/
        {
            f=s;
            s=s->rchild;
        }
        if(f==p)    f->lchild=s->lchild;  /*重接f的左子树*/
        else    f->rchild=s->lchild;   /*重接f的右子树*/
        p->data=s->data;
        free (s);
    }
    return  t;
}

3.3流程图
初始化
输入数据
无X
查找函数
中序遍历
遍历结果
插入节点X
1
2
删除节点
存在含x的结点
不存在
输出遍历结果

3.4源程序代码

用顺序存储实现：

#include<stdio.h>
#include<stdlib.h>

typedef struct Tnode{
    int   data;                       /*输入的数据*/
    struct  Tnode    *lchild,*rchild;     /*结点的左右指针，分别指向结点的左右孩子*/
    }*node,BSTnode;
searchBST(node t,int key,node f,node *p) /*查找函数*/
{
    if(!t)
{*p=f;return (0);}         /*查找不成功*/
else
  if(key==t->data)    {*p=t;return (1);} /*查找成功*/
    else
  if(key<t->data)   searchBST(t->lchild,key,t,p);   /*在左子树中继续查找*/
else  
searchBST(t->rchild,key,t,p); /*在右子树中继续查找*/
}

insertBST(node *t,int key)  /*插入函数*/
{
    node p=NULL,s=NULL;

    if(!searchBST(*t,key,NULL,&p))   /*查找不成功*/
    {
        s=(node)malloc(sizeof(BSTnode));
        s->data=key;
        s->lchild=s->rchild=NULL;
        if(!p)  *t=s;     /*被插结点*s为新的根结点*/
        else
   if(key<p->data)   p->lchild=s;/*被插结点*s为左孩子*/
                else    p->rchild=s;  /*被插结点*s为右孩子*/
        return (1);
    }
else
return (0);/*树中已有关键字相同的结点，不再插入*/
}

  inorderTraverse(node *t)  /*中序遍历函数*/
{
    if(*t){
            if(inorderTraverse(&(*t)->lchild))          /*中序遍历根的左子树*/
              printf("%d  ",(*t)->data);  /*输出根结点*/
                if(inorderTraverse(&(*t)->rchild)); /*中序遍历根的右子树*/
            }
return(1) ;
}
node Delete(node t,int  key)   /*删除函数*/
{
    node    p=t,q=NULL,s,f;
   while(p!=NULL)   /*查找要删除的点*/
    {
        if(p->data==key)
   break;
        q=p;
        if(p->data>key)   p=p->lchild;
        else
   p=p->rchild;
    }
    if(p==NULL)
  return  t;    /*查找失败*/
    if(p->lchild==NULL)     /*p指向当前要删除的结点*/
    {
        if(q==NULL)   t=p->rchild;  /*q指向要删结点的父母*/
        else
   if(q->lchild==p)    q->lchild=p->rchild;  /*p为q的左孩子*/
                else
     q->rchild=p->rchild;/*p为q的右孩子*/
        free(p);
    }
    else{           /*p的左孩子不为空*/
        f=p;
        s=p->lchild;
        while(s->rchild)   /*左拐后向右走到底*/
        {
            f=s;
            s=s->rchild;
        }
        if(f==p)    f->lchild=s->lchild;  /*重接f的左子树*/
        else    f->rchild=s->lchild;   /*重接f的右子树*/
        p->data=s->data;
        free (s);
    }
    return  t;
}
void main()
{
    node  T=NULL;
    int   num;
    int   s=0,j=0,i=0;
    int   ch=0;
    node  p=NULL;
  printf("输入一串数，每个数以空格分开:");
    do{
        scanf("%d",&num);
        if(!num) printf("完成输入!\n");
        else    insertBST(&T,num);
    }while(num);
    printf("\n  1:  中序输出");

    printf("\n  2:  输入元素");

    while(ch==ch)
    {

        scanf("%d",&ch);
        switch(ch){
            case 0:
    exit(0);    /*0－－退出*/
            case 1:
    printf("   中序遍历输出结果为:\n   ");
                      inorderTraverse(&T); /*1－－中序遍历*/
                      break;

            case 2:
    printf(" 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历，否则输出无x :");
                      scanf("%d",&num);  /*3－－删除某个结点*/
                     if(searchBST(T,num,NULL,&p))
                      {
                        T=Delete(T,num);
                        printf("   删除成功!中序遍历输出：\n   ");
                        inorderTraverse(&T);
                      }
                      else
        printf("   无%d",num);
                      break;

            default:
    printf("无此结点\n");
                      break;   /*输入无效字符*/
        }
    }
}
二叉链表做存储结构：
#include <iostream>
using namespace std;

class node
{
public:
node(int i):data(i),left(NULL),right(NULL){}
void inorder(node *&root) //中序遍历，符合升序输出
{
if(root!=NULL)
{
inorder(root->left);
cout<<root->data<<' ';
inorder(root->right);
}
}
void insert(node *&ptr,int item) //在查找树中插入元素
{
if(ptr==NULL)
ptr=new node(item);
else if(item<ptr->data)
insert(ptr->left,item);
else insert(ptr->right,item);
}
node *find(node *&ptr,int item) //在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。
{
if(ptr==NULL)
return NULL;
if(ptr->data==item)
return ptr;
else if(item<ptr->data)
find(ptr->left,item);
else find(ptr->right,item);
}
node *&findy(node *&ptr,int item) //在查找树中查找肯定存在的元素,并返回其引用
{
if(ptr->data==item)
return ptr;
else if(item<ptr->data)
findy(ptr->left,item);
else findy(ptr->right,item);
}
node* rl(){return left;}
node* rr(){return right;}
void dele(node *&ptr) //删除值为item所在结点
{
if(ptr->rl()==NULL&&ptr->rr()==NULL)
ptr=NULL;
else if(ptr->rr()==NULL)
ptr=ptr->rl();
else
ptr=ptr->rr();
}
private:
int data;
node *left; //左孩子结点
node *right; //右孩子结点
};

int main()
{
int t,i=0,j;
cout<<"输入数字个数(结点个数):";
cin>>t;
cout<<"输入"<<t<<"个数字，数字之间用空格隔开:";
cin>>j;
node *x=new node(j);
for(;i<t-1;i++)
{
cin>>j;
x->insert(x,j);
}
cout<<"中序遍历为:";
x->inorder(x); //作中序遍历
cout<<"\n输入操作(当输入-1时程序结束):"<<endl;
cin>>j;
while(j!=-1)
{

node *t=x->find(x,j); //定位结点
if(t!=NULL)
{
node *&y=x->findy(x,j);
x->dele(y);
cout<<"中序遍历为:";
x->inorder(x);
}
else cout<<"无"<<j;
cout<<"\n输入操作(当输入-1时程序结束):"<<endl;
cin>>j;
}
return 0;
}

第四章 测试与分析
4.1程序调试

（1） 顺序存储

（2）二叉链表储存

4.2测试结果分析
输入一串数据，进行中序遍历，输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。验证结果正确，说明其符合算法设计的要求：(1)正确性、可读性、健壮性、效率与低储存量需求.要写一个优质的算法，就必须考虑其时间复杂度（它表示随问题的规模n的增大，算法执行时间的增长率和f（n）的增长率相同）和空间复杂度。遍历二叉树的算法中的基本操作是访问结点，则不论按那一次次序进行遍历，对含n个结点的二叉树，其时间复杂度为O（n）。所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，则空间复杂度也为O（n）。
总  结
这次课程设计使我对数据结构认识深刻了许多，其中最深刻的是我理解了用二叉链表结构存储实现二叉排序树，同时也加深了对二叉树的理解。本课程设计实现了二叉排序树的创建、中序遍历、删除二叉排序树中某个结点,。在进行搜索时，还可以采用更好的搜索结构即动态搜索结构。当没有找到时，可以将其插入，而不是仅仅提示未找到。通过一周的课程设计，我已经会用二叉链表存储结构实现对二叉排序树的的创建，中序遍历，查找和某个删除结点等基本操作。
但我同时也发现了自己许多不足之处 。
首先，对数据结构的掌握还不够。虽然完成了程序，但是只用到了基本的结点以及链表，在数据结构的选择上避重就轻，覆盖面较小，不能很好的体现各种数据结构的掌握度，同时也缺少了适当的锻炼，在这方面还需要自己主动去提高。
其次，在程序整体的设计上还不够完善，各模块可以适当增加内容，界面还可以更加的人性化些，这样整个程序才具有更强的美观性与实用性。
总而言之，这次课程设计给了我很大启发，我明白了，不管遇到什么问题，只要抓住根源，不气馁，从不同方面去攻破它，终究会成功，生活也是如此。在今后的工作、学习中我将认真总结经验教训，努力使自己成为一名技术过硬、工作严谨、思维活跃的工程人员，为提高人们的生活质量做出更大的贡献。

心得体会

一周的课程设计结束了，在这次的课程设计中不仅检验了我所学的知识，也培养了我如何去把握一件事情，如何去做一件事情，课程设计是我们专业课程知识综合应用的实践训练是我们迈向社会，从事职业工作前一个必不可少的过程。
我们这次设计的科目是数据结构，数据结构，是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。作为一门独立的课程在国外是从1968年才开始的。这次通过对二叉排序树的深入研究，我又一次的温习了c和数据结构的有关知识，也为我今后对c++的学习奠定了基础，尽管这中间经历好多困难，但我们齐心协力，查找多种资料，利用网络优势，完成了任务。
我这次课程设计代码中主要使用了链表的循环和遍历这两种操作。循环链表是单链表的另一种形式。遍历是指沿着某条收索路线，依次对树中每个节点均作一次且仅作一次访问。通过这次的课程设计，更是让我深刻认识到自己在学习中的不足，同时也找到了克服这些不足的方法，这是一笔很大的资源。在以后的学习中，我们应该利用更多的时间去上机实验，加强自学的能力、多编写程序，相信不久以后我们的编程能力都会有很大的提高，能设计更多的更有创新的作品。

参考文献
1.潭浩强.程序设计.北京：清华大学出版社，2000
2.严蔚敏，吴伟民.数据结构.北京：清华大学出版,2001
3. 陈慧南．数据结构与算法 C++ 语言描述．高等教育出版社 2005
4. 编程爱好者网

29