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

(完整word版)用顺序和二叉链表作存储结构实现二叉排序树全代码

安徽新华学院

数据结构课程设计报告

题目：用顺序和二叉树存储结构实现二叉树排序
学院：信息工程
专业：信息与计算科学
班级：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 总体设计 2
2.1二叉排序树的建立 2
2.2二叉排序树的中序遍历 2
2.3二叉排序树中元素的查找 2
2.4二叉排序树中元素的删除 3
2. 5 总体设计流程图
3 详细设计 6
3.1 中序遍历模块 9
3.2 删除模块 9
4编码与调试 12
4.1 顺序存储 12
4.2 二叉链表存储 16
5 总结 19
总  结 19
心得体会 20
参考文献 21
全部代码 22
二叉链表结构c 22
二叉链表结构c++ 26
顺序存储结构c 29

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<data(p), 将b插入左子树中；
如果b≥data(p)，将b插入右子树中；
左、右子树的插入方式与二叉排序树的插入方式相同。
不断调用上述的插入过程，直到所有待排序序列均排入后，就形成一棵二叉排序树。
由此可见，建立二叉排序树就是多次调用二叉排序树的插入算法。
2.2二叉排序树的中序遍历
中序遍历二叉树算法的框架是：
若二叉树为空，则空操作；否则
中序遍历左子树（L）；
访问根结点（V）；
中序遍历右子树（R）。
中序遍历二叉树也采用递归函数的方式，先访问左子树,然后访问根结点,最后访问右子树.直至所有的结点都被访问完毕。
2.3二叉排序树中元素的查找
在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设我们想要在二叉排序树中查找关键码为x的元素，查找过程从根结点开始。如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键码进行比较；如果给定值等于根结点的关键码，则查找成功，返回查找成功的信息，并报告查找到的结点地址。如果给定值小于根结点的关键码，则继续递归查找根结点的左子树；否则，递归搜索根结点的右子树。
2.4二叉排序树中元素的删除
对于二叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。假设在二叉排序树上被删除结点为*p（指向结点的指针是p），其双亲结点为*f（结点指针为f），且不失一般性，可设*p是*f的左孩子，若*p结点为叶子结点，即p和l均为空，只需修改其双亲结点指针即可。若*p结点只有左子树或者只有右子树，只要令左子树或右子树直接成为其双亲结点即可。若左子树和右子树都不为空，令*p的直接前驱替代*p，然后从二叉排序树中删除它的直接前驱，即可。

2.5 总体设计流程图

初始化
输入数据
无X
查找函数
中序遍历
遍历结果
插入节点X
1
2
删除节点
存在含x的结点
不存在
输出遍历结果
4.1程序总体流程图
3．详细设计
· Tnode的声明
typedef struct Tnode{
int data;
struct Tnode *lchild,*rchild;
}*node,BSTnode;
· searchBST的声明
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的声明
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;
else
if(key<p->data) p->lchild=s;
else p->rchild=s;
return (1);
}
else
return (0);
}
· inorderTraverse类的声明
inorderTraverse(node *t)
{
if(*t){
if(inorderTraverse(&(*t)->lchild))
printf("%d ",(*t)->data);
if(inorderTraverse(&(*t)->rchild));
}
return(1) ;
}
· Delete类的声明
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)
{
if(q==NULL) t=p->rchild;
else
if(q->lchild==p) q->lchild=p->rchild;
else
q->rchild=p->rchild;
free(p);
}
else{
f=p;
s=p->lchild;
while(s->rchild)
{
f=s;
s=s->rchild;
}
if(f==p) f->lchild=s->lchild;
else f->rchild=s->lchild;
p->data=s->data;
free (s);
}return t;
}

3.1 中序遍历模块
系统将提示用户输入新添加的数据，输入结束后进行中序遍历
关键代码：

inorderTraverse(node *t) /*中序遍历函数*/
{
if(*t){
if(inorderTraverse(&(*t)->lchild)) /*中序遍历根的左子树*/
printf("%d ",(*t)->data); /*输出根结点*/
if(inorderTraverse(&(*t)->rchild)); /*中序遍历根的右子树*/
}
return(1) ;
}
3.2 删除模块
系统将对用户输入的数进行查找，查找到之后删除此数，并对全部数据进行中序遍历。
关键代码：
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;}

4编码与调试
首先进入VC++6.0，打开工程zjr.dsw，然后进入源程序，也可以不打开工程，直接双击zjr文件夹下的zjr.exe文件即可运行程序。

4.1 顺序存储
图7.1.1 打开程序，成功显示提示信息

图7.1.2 输入数据，以0结束输入，操作成功

图7.1.3 功能1：中序输出数据，操作成功

图7.1.4 功能2：删除数据，显示提示信息，操作成功

图7.1.5 删除数据，操作成功

图7.1.6 重复执行程序，操作成功
4.2 二叉链表存储

图7.2.1打开程序，显示提示信息，操作成功

图7.2.2功能1：输入数据，进行中序遍历，操作成功

图7.2.3功能2：输入数据，进行删除，操作失败，因为没有此数据，显示 错误信息

图7.2.4功能2：输入数据，进行中序遍历，操作成功

通过上述测试，本系统实现了二叉树的生成，中序遍历，查找删除功能，能避免数据的输入错误等。验证结果正确，说明其符合算法设计的要求：(1)正确性、可读性、健壮性、效率与低储存量需求.要写一个优质的算法，就必须考虑其时间复杂度（它表示随问题的规模n的增大，算法执行时间的增长率和f（n）的增长率相同）和空间复杂度。遍历二叉树的算法中的基本操作是访问结点，则不论按哪一次次序进行遍历，对含n个结点的二叉树，其时间复杂度都为O（n）。所需空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，则空间复杂度也为O（n）。

5 总结
这次课程设计使我对数据结构认识深刻了许多，其中最深刻的是我理解了用二叉链表结构存储实现二叉排序树，同时也加深了对二叉树的理解。本课程设计实现了二叉排序树的创建、中序遍历、删除二叉排序树中某个结点,。在进行搜索时，还可以采用更好的搜索结构即动态搜索结构。当没有找到时，可以将其插入，而不是仅仅提示未找到。通过这一次的课程设计，我已经会用二叉链表存储结构实现对二叉排序树的的创建，中序遍历，查找和某个删除结点等基本操作。
但我同时也发现了自己许多不足之处 。
首先，对数据结构的掌握还不够。虽然完成了程序，但是只用到了基本的结点以及链表，在数据结构的选择上避重就轻，覆盖面较小，不能很好的体现各种数据结构的掌握度，同时也缺少了适当的锻炼，在这方面还需要自己主动去提高。
其次，在程序整体的设计上还不够完善，各模块可以适当增加内容，界面还可以更加的人性化些，这样整个程序才具有更强的美观性与实用性。总而言之，这次课程设计给了我很大启发，我明白了，不管遇到什么问题，只要抓住根源，不气馁，从不同方面去攻破它，终究会成功，生活也是如此。在今后的工作、学习中我将认真总结经验教训，努力使自己成为一名技术过硬、工作严谨、思维活跃的工程人员，为提高人们的生活质量做出更大的贡献。

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

参考文献
[1] 谭浩强 编著. 程序设计. 北京:清华大学出版社，2000
[2] 王珊珊，张志航 编著. C++程序设计教程. 北京:机械工业出版社，2011
[3] 严蔚敏，吴伟民 编著. 数据结构. 北京:清华大学出版社，2001

全部代码
二叉链表结构c
#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; /*输入无效字符*/
}
}
}

二叉链表结构c++
#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;
}

顺序存储结构c

#include"stdio.h"
#include"malloc.h"
#include"windows.h"
#define endflag 999999
#define N 1000
int b[N];

typedef struct
{
int data;
int other;
int flag1;
}Link;

void Build(Link a[N])
{
int w,i,j,k;
for(i=0;i<=N;i++)
{
a[i].flag1=0;
a[i].data=0;
}
printf("\n\t\t\t 请输入树的根结点：");
scanf("%d",&a[1].data);
a[1].flag1=1;
printf("\n\t\t\t 请输入结点个数：");
scanf("%d",&k);
for(j=1;j<=k;j++)
{
printf("\n\t\t\t 请输入结点的数值：");
scanf("%d",&w);
printf("\n\t\t\t 第%d位：%d",j,w);
a[0].data=w;
a[0].flag1=1;
i=1;
if(a[0].data<a[i].data)
{
loop:if(a[2*i].flag1==0)
{
a[2*i].data=a[0].data;
a[2*i].flag1=a[0].flag1;}
if(a[2*i].flag1==1)
{
i=2*i;
if(a[0].data<a[i].data)
goto loop;
if(a[0].data>a[i].data)
goto loop1;
}
}
if(a[0].data<a[i].data)
{
loop1:if(a[2*i+1].flag1==0)
{
a[2*i+1].data=a[0].data;
a[2*i+1].flag1=a[0].flag1;}
if(a[2*i+1].flag1=1)
{
i=2*i+1;
if(a[0].data<a[i].data)
goto loop;
if(a[0].data>a[i].data)
goto loop1;
}
}
}
}

void Sdel(Link a[N])
{
int i;int flag=0;
int q;int number=1;
int j=1;int b[N];
printf("\n\t\t\t 请输入需要删除的结点的数值：");
scanf("%d",&q);
for(i=1;i<=N;i++)
if(a[i].data=q)
{
a[i].data=0;
printf("\n\t\t\t 已删除%d：",q);
flag=1;
for(i=1;i<=N;i++)
{
if(a[i].data!=0)
{
b[j]=a[i].data;
j++;
number++;
}
}
for(i=1;i<=N;i++)
{
a[i].flag1=0;
a[i].data=0;
}
a[1].data=b[1];
a[1].flag1=1;
for(j=2;j<=number-1;j++)
{
a[0].data=b[j];
a[0].flag1=1;
i=1;