二叉排序树的基本操作的实现

设计要求

1. 问题描述

从磁盘读入一组数据，建立二叉排序树并对其进行查找、、遍历、插入、删除等基本操作。 2. 需求分析

建立二叉排序树并对其进行查找，包括成功和不成功两种情况。

II. 概要设计

为了实现需求分析中的功能，可以从以下3方面着手设计。 1. 主界面设计

为了方便对二叉排序树的基本操作，设计一个包含多个菜单选项的主控制子程序以实现二叉排序树的各项功能。本系统的主控制菜单运行界面如图1所示。

图1二叉排序树的基本操作的主菜单

2. 存储结构的设计

本程序主要采二叉树结构类型来表示二叉排序树。其中二叉树节点由1个表示关键字的分量组成，还有指向该左孩子和右孩子的指针。 3. 系统功能设计

本程序设置了5个子功能菜单，其设计如下。

1) 建立二叉排序树。根据系统提示，输入节点的关键字，并以0作为结束的标

识符。该功能由Bstree Create()函数实现。

2) 插入二叉排序新的节点信息。每次只能够插入一个节点信息，如果该节点已

经存在，则不插入。该功能由Bstree Insert(y)函数实现。

3) 查询二叉排序树的信息。每次进行查询，成功则显示“查询到该节点”，不成

功则“显示查询不到该节点“该功能由Bstree Search()函数实现。

4) 删除二叉排序树的节点信息。可以对二叉排序树中不需要的节点进行删除，

删除的方式是输入关键字，查询到该节点后删除。该功能由Bstree Delete()函数实现。

5) 遍历二叉排序树。遍历二叉排序树可以显示该二叉排序树的全部节点信息。

该功能由void Traverse()实现。

III. 模块设计

1. 模块设计

本程序包含两个模块：主程序模块和二叉排序树操作模块。其调用关系如图2

图2模块调用示意图 2. 系统子程序及其功能设计

本系统共设计了5个子程序，个程序的的函数名及其功能说明如下： 1) Bstree Create(); //创建二叉排序树 2) Bstree Insert(Bstree tree,int key); //插入 3) Bstree Search(Bstree tree,int key); //查找 4) void Traverse(Bstree tree); //遍历 5) Bstree Delete(Bstree tree,int key); //删除信息 3. 函数主要的调用关系

本系统9个子程序见的主要调用关系图3.

IV. 详细设计

1. 数据类型定义

本系统采用二叉树结构存储节点信息，节点定义如下： typedef struct Bstnode { int key; struct Bstnode *lchild,*rchild; }Bstnode,* Bstree;

2. 主要子程序的详细设计

1) 二叉排序树的创建函数，主要用来建立二叉排序树。

Bstree Create() {

int key; Bstree tree=NULL; //初始化空树

scanf("%d",&key); while(key!=0) { tree=Insert(tree,key); //逐个插入节点 scanf("%d",&key); }

return tree;

}

2) 二叉排序插入函数如下：

Bstree Insert(Bstree tree,int key) { Bstree p=tree; Bstree s,f; while (p!=NULL) { f=p; if(key==p->key) return tree; if(key

key) p=p->lchild; else p=p->rchild; } s=(Bstree)malloc(sizeof(Bstnode)); s->key=key; s->lchild=NULL; s->rchild=NULL; if(tree==NULL) return s; if(keykey) f->lchild=s; else f->rchild=s; return tree; }

3) 二叉排序树查询函数如下： Bstree Search(Bstree tree,int key) { Bstree p=tree; int flag=0;

while(p!=NULL) { if(p->key==key) { printf("查询到该节点！"); flag=1; return(p); break; } if (key

key) p=p->lchild;

//新节点为二叉排序树的根

else p=p->rchild; } if(flag==0) { printf("查询不到关键字为%d的节点！",key); return NULL; } }

V. 测试分析

1. 二叉排序树的建立

首先进入主菜单，如图1。在主菜单下，用户根据菜单的选项输入1，然后按照提示建立二叉排序树，并以0未结束符。运行的结果如图4.

图4二叉排序树的建立

2. 遍历二叉树的节点信息

在主菜单下，用户选择4，可以打印出全部的节点信息。运行的结果如图5.

图5遍历二叉排序树

3. 插入节点信息信息

在主菜单下，用户选择2，可以插入一个新的节点信息。运行的结果如图

图6插入新的节点

4. 查询二叉树的节点信息

在主菜单下，用户选择3，首先通过输入关键字查询相关信息。运行的结果如图7.

图7查询节点信息

5. 删除二叉树的节点

在主菜单下，用户选择5，可以通过输入要删除的关键字来删除该节点的全部信息。运行的结果如图8.

图8删除二叉排序树的节点

VI. 原程序清单 #include #include #include

/******二叉排序树的数据结构********/ typedef struct Bstnode { int key; struct Bstnode *lchild,*rchild; }Bstnode,* Bstree;

Bstree Create(); //创建二叉排序树 Bstree Insert(Bstree tree,int key); //插入 Bstree Search(Bstree tree,int key); //查找

void Traverse(Bstree tree); //遍历 Bstree Delete(Bstree tree,int key); //删除

/*********************创建二叉排序树**************/ Bstree Create() {

int key; Bstree tree=NULL; //初始化空树 scanf("%d",&key); while(key!=0)

tree=Insert(tree,key); //逐个插入节点 scanf("%d",&key); } return tree; }

/*******************插入*********************/ Bstree Insert(Bstree tree,int key) { Bstree p=tree; Bstree s,f; while (p!=NULL) { f=p; if(key==p->key) return tree; if(key

key) p=p->lchild; else p=p->rchild; } s=(Bstree)malloc(sizeof(Bstnode)); s->key=key; s->lchild=NULL; s->rchild=NULL; if(tree==NULL) return s; if(keykey) f->lchild=s; else f->rchild=s; return tree; }

/**************查找**************/ Bstree Search(Bstree tree,int key) { Bstree p=tree; int flag=0;

while(p!=NULL) { if(p->key==key) { printf("查询到该节点！"); flag=1; return(p); break; } if (key

key) p=p->lchild; else p=p->rchild;

//新节点为二叉排序树的根

if(flag==0) { printf("查询不到关键字为%d的节点！",key); return NULL; } }

/***************遍历*********************/ void Traverse(Bstree tree) { if(tree) { Traverse(tree->lchild); printf("%4d",tree->key); Traverse(tree->rchild); } }

/***************删除*******************/ Bstree Delete(Bstree tree,int key) { Bstree p=tree; Bstree f,s,q; f=NULL; while(p) { //查找关键字为key的节点 if(p->key==key) break; f=p; if(p->key>key) p=p->lchild; else p=p->rchild; } if (p==NULL) return tree; if ((p->lchild==NULL)||(p->rchild==NULL)) { if(f==NULL) if(p->lchild==NULL) tree=p->rchild; else tree=p->lchild; else if (p->lchild==NULL) if(f->lchild==p) f->lchild=p->rchild; else f->rchild=p->rchild; else if(f->lchild==p) f->lchild=p->lchild; else f->lchild=p->lchild; free(p); } else {

q=p;s=p->lchild; while(s->rchild) { q=s;s=s->rchild; } if(q==p) q->lchild=s->lchild; p->key=s->key; free(s); } return tree; }

/*******************************************/ void main() {

system("color 1E"); Bstree tree,p; int key1,key2,key3; int select,flag; printf("############################################\n"); printf("|* 欢迎您使用本系统 *|\n"); printf("|******************************************|\n"); printf("|* 1.创建二叉排序树 *|\n"); printf("|* 2.插入 *|\n"); printf("|* 3.查找 *|\n"); printf("|* 4.遍历 *|\n"); printf("|* 5.删除 *|\n"); printf("|* 6.退出 *|\n"); printf("********************************************\n"); while(select!=6) { printf("选择的功能："); scanf("%d",&select); switch(select) { case 1: printf("请输入节点信息(0为结束符):\n"); tree=Create(); printf("\n"); break; case 2: printf("插入一个新的节点:"); scanf("%d",&key1);Insert(tree,key1); printf("插入后得序列为:\n"); Traverse(tree); printf("\n"); break;

case 3: printf("输入查找的数据:"); scanf("%d",&key2); p=Search(tree,key2); printf("\n"); break; case 4: printf("遍历所得序列为:\n"); Traverse(tree); printf("\n"); break; case 5: printf("输入删除的数据:"); scanf("%d",&key3); tree=Delete(tree,key3); printf("删除后遍历所得序列:\n"); Traverse(tree); printf("\n"); break;

case 6: printf("谢谢您的使用，再见！\n");flag=0;break; default:printf("输入错误,请重新输入\n");break; } } }

VII. 用户手册

运行程序进入本系统后，及显示系统的主菜单。用户可以根据菜单的提示选择相应的数字，进入相应的子菜单，在创建二叉排序树时注意以0为输入结束标志，在创建完成后可立即进行遍历，看创建的是否有误。此外，本程序关键字既是节点的关键字也是节点的信息。 VIII. 小结

由于为了简化程序的复杂度，本程序只以整形的关键字作为节点的唯一信息，但本

程序能够很好的实现二叉排序树的基本操作。在调试程序过程中，对左右孩子的处理是难点，其中出现了许多的错误，但通过错误的改正也加深了对二叉排序树的认识。