二叉排序树运算-数据结构与算法课程设计报告 l

合肥学院

计算机科学与技术系

课程设计报告

2009 ～2010 学年第 二 学期

课学学专指

业导

班教生

姓

程 数据结构与算法

二叉排序树运算

顾成方 0704011033 08计科(2) 王昆仑 张贯虹

名 号 级 师

课程设计名称

2010 年 5 月

题目：（二叉排序树运算问题）设计程序完成如下要求：对一组数据构造二叉排序树，并在二叉排序树中实现多种方式的查找。基本任务：⑴选择合适的储存结构构造二叉排序树；⑵对二叉排序树T作中序遍历，输出结果；⑶在二叉排序树中实现多种方式的查找，并给出二叉排序树中插入和删除的操作。⑷尽量给出“顺序和链式”两种不同结构下的操作，并比较。

一、 问题分析和任务定义

本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历，然后输出遍历后的数据序列；其次，该二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删除等基本操作。 实现本程序需要解决以下几个问题： 1、 如何构造二叉排序树。

2、 如何通过中序遍历输出二叉排序树。 3、 如何实现多种查找。

4、 如何实现插入删除等操作。

二叉排序树的定义： ⑴ 其左子树非空，则左子树上所有结点的值均小于根结点的值。

⑵ 若其右子树非空，则右子树上所有结点的值大于根结点的值。 ⑶ 其左右子树也分别为二叉排序树。

本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现：输入（插入）的第一个数据即为根结点；继续插入，当插入的新结点的关键值小于根结点的值时就作为左孩子，当插入的新结点的关键值大于根结点的值时就作为右孩子；在左右子树中插入方法与整个二叉排序树相同。当二叉排序树建立完成后，要插入新的数据时，要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此，插入算法还要包括对数据的查找判断过程。

本问题的难点在于二叉排序树的删除算法的实现。删除前，首先要进行查找，判断给出的结点是否已存在于二叉排序树之中；在删除时，为了保证删除结点后的二叉树仍为二叉排序树，要考虑各种情况，选择正确的方法。删除操作要分几种情况讨论，在后面有介绍。 二、 概要设计和数据结构选择

用二叉链表作为二叉排序树的存储结构，其中key为结点关键值，*lchlid、*rchild分别为左右孩子指针。该程序的结构如下图所示：

递归查找 非递归查找 三、 详细设计和编码

首先定义二叉排序树的数据类型如下：

二叉排序树的查找 二叉排序树的插入 二叉排序树的删除 二叉排序树的显示 Main() 先建立一棵二叉排序树，并输出其中序排序后的序列 typedef struct node {

int key;//关键字项

struct node *lchild,*rchild;//左右孩子指针

}Bstnode;

然后按一定顺序来编写算法程序： 1、 递归查找算法

具体思想如下：

（1）若二叉树为空，则查找失败。

（2）否则，将根结点的关键值与待查关键字进行比较，若相等，则查找成功；若根结点关键值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤；若在查找过程的中遇到二叉排序树的叶子结点时，还没有找到待查结点，则查找不成功。 }

if(t==NULL) return NULL; else{ if(t->data==x)

return t; if(xdata) return(Bsearch(t->lchild,x)); else

return(Bsearch(t->rchild,x));

二叉排序树递归查找算法流程图

2、 非递归查找算法

查找过程是从根结点开始逐层向下进行的。并定义一个标记量记录是否找到结点。

Bstnode *searchBST(Bstnode *t,int x)

{

Bstnode *p;int flag=0;p=t;//定义*p结点用于逐层查找，丛根结点开始查找 while(p!=NULL)//二叉排序树不为空 {

if(p->key==x)//查找成功

{

printf(\该结点值存在!\

break;

}

//查找不成功，到下一层继续查找

if(xkey) p=p->lchild;//查找左子树

else p=p->rchild;//查找右子树

}

if(flag==0) {

printf(\找不到值为%d的结点!\p=NULL;

}

return p;

}

3、 插入算法

从根结点开始，根据比较规则，逐一与待插入结点的值比较，查找到插入结点在二叉排序树中的未来位置，然后插入该结点。将一个关键字的值为x的结点s插入到二叉排序树中，方法如下：

（1）若二叉排序树为空，则关键字值为x的结点s成为二叉排序树的根。

（2）若二叉排序树非空，则将x与二叉排序树的根进行比较，如果x的值等于根结点关键字的值，则停止插入；如果x的值小于根结点关键字的值，则将x插入左子树；如果x的值大于根结点关键字的值，则将x插入右子树。在左右子树中插入方法与整个二叉排序树相同。

Bstnode *InsertBST(Bstnode *t,int x)// 插入关键值为x的元素

{

Bstnode *s,*p,*f;//*s为待插结点，*p为逐层查找结点，*f为待插结点的父结点 p=t;

while(p!=NULL) {

f=p;//查找过程中，f指向*p的父结点

if(x==p->key)//若二叉树中已有关键值为x的元素，无需插入 return t; if(xkey) { } else { }

p=p->rchild; p=p->lchild;

}

s=(Bstnode *)malloc(sizeof(Bstnode)); s->key=x;

s->lchild=NULL;s->rchild=NULL;

if(t==NULL)//原树为空，新结点作为二叉排序树的根 return s; if(xkey) f->lchild=s;//新结点作为*f左孩子 else f->rchild=s;//新结点作为*f右孩子 return t; }

4、 二叉排序树的生成算法

建立二叉排序树，就是反复在二叉排序树中插入新的结点。插入的原则是如果待插入结点的值小于根结点的值，则插入到左子树中，否则插入到右子树中。

大致方法是：首先建一棵空二叉排序树，然后逐个读入元素，每读入一个元素，就建一个新结点，并调用上述二叉排序树的插入算法，将新结点插入到当前已生成的二叉排序树中，最终生成一棵二叉排序树。 Bstnode *CreateBST() {

Bstnode *t;

int key;

t=NULL;//设置二叉排序树的初态为空 scanf(\ while(key!=endflag) { t=InsertBST(t,key); }

scanf(\

return t; }

5、 中序遍历算法

void Inorder(Bstnode *t) {

if(t!=NULL) { } }

先遍历左孩子，再遍历父结点，最后遍历右孩子。由于是对一个二叉排序树进行中序遍历，遍历结果则是一个有序序列。

6、 删除算法

（1） 待删除结点*p无左孩子，也无右孩子，则*p的父结点对应的孩子指针置空； （2） 待删除结点*p有左孩子，无右孩子，则*p的左孩子替代自己；

Inorder(t->lchild);

Printf(“M\\n”,t->key); Inorder(t->rchild);

{

t=InsertBST(t,s); scanf(\ }

return t; }

//显示函数

void print_Bitree(Bstnode *t)

{ if(t!=NULL)//中序遍历二叉排序树,并显示遍历结果

{

print_Bitree(t->lchild);

printf(\遍历结点%d\

if(t->lchild!=NULL) printf(\该结点的左孩子为%d\ else

printf(\该结点的左孩子为空\

if(t->rchild!=NULL)

printf(\该结点的右孩子为%d)\ else

printf(\该结点的右孩子为空)\ printf(\

print_Bitree(t->rchild); } }

//主菜单 int mainmenu() {

int choice;

int flag=1;//标记量

printf(\

printf(\┏***对二叉排序树进行操作***┓\\n\

printf(\┇┏┅┅┅┅┅┅┅┅┅┅┅┓┇\\n\ printf(\┇┃ ┃┇\\n\

printf(\┇┃1.二叉排序树------查找┃┇\\n\ printf(\┇┃2.二叉排序树------插入┃┇\\n\ printf(\┇┃3.二叉排序树------删除┃┇\\n\ printf(\┇┃4.二叉排序树------显示┃┇\\n\ printf(\┇┃0.退出该程序 ┃┇\\n\

printf(\┇┃ ┃┇\\n\printf(\┇┗┅┅┅┅┅┅┅┅┅┅┅┛┇\\n\ printf(\┗**************************┛\\n\

printf(\

do{ if(flag==0) printf(\您的输入有误,请重新输入\\n\ printf(\请选择您要进行的项目:\ scanf(\ }

//查找方法菜单 int searchmenu() {

int choice;

int flag=1;//标记量 flag=0;

}while(choice<0||choice>4); return choice;

printf(\ printf(\┏*****二叉树的查找方法*****┓\\n\ printf(\┋┏┅┅┅┅┅┅┅┅┅┅┅┓┇\\n\

printf(\┇┃ ┃┇\\n\printf(\┇┃1.方法1-------递归查找┃┇\\n\ printf(\┇┃2.方法2-----非递归查找┃┇\\n\printf(\┇┃ ┃┇\\n\printf(\┇┗┅┅┅┅┅┅┅┅┅┅┅┛┇\\n\printf(\┗**************************┛\\n\

printf(\ do{

if(flag==0) printf(\您的输入有误,请重新输入\\n\ printf(\请选择查找方法:\ scanf(\ flag=0;

}while(choice!=1&&choice!=2); return choice;

}

//主函数 void main() {

int i,j,k; Bstnode *tree,*p;

system(\ printf(\ ★☆★☆★请先建立一棵二叉排序树★☆★☆★\\n\\n\ printf(\输入其结点信息(输入一组正整数,当输入0时结束):\\n\

tree=CreateBST();

printf(\中序遍历的二叉排序树:\\n\ Inorder(tree);

printf(\二叉排序树的根为:%d\\n\ for(;;)

switch(i=mainmenu()) {

case 0:exit(0);

case 1:switch(j=searchmenu())

{

case 1:search_Bitree(tree);break;

case 2:printf(\请输入要查找的结点的值:\

scanf(\ printf(\

break;

//default:printf(\输入有误!\

} break;

case 2:tree=insert_Bitree(tree);break;

case 3:tree=delete_Bitree(tree);break;

case 4:printf(\ printf(\二叉排序树的根为:%d\\n\ printf(\中序遍历后的序列为:\\n\ print_Bitree(tree);

printf(\中序遍历的二叉排序树:\\n\

Inorder(tree); printf(\

break;

//default:printf(\输入有误!\ }

}

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