《二叉排序树的基本操作的实现(共9页).doc》由会员分享，可在线阅读，更多相关《二叉排序树的基本操作的实现(共9页).doc（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上二叉排序树的基本操作的实现I. 设计要求1. 问题描述 从磁盘读入一组数据，建立二叉排序树并对其进行查找、遍历、插入、删除等基本操作。2. 需求分析建立二叉排序树并对其进行查找，包括成功和不成功两种情况。II. 概要设计为了实现需求分析中的功能，可以从以下3方面着手设计。1. 主界面设计为了方便对二叉排序树的基本操作，设计一个包含多个菜单选项的主控制子程序以实现二叉排序树的各项功能。本系统的主控制菜单运行界面如图1所示。图1二叉排序树的基本操作的主菜单2. 存储结构的设计本程序主要采二叉树结构类型来表示二叉排序树。其中二叉树节点由1个表示关键字的分量组成，还有指向该左
2、孩子和右孩子的指针。3. 系统功能设计本程序设置了5个子功能菜单，其设计如下。1) 建立二叉排序树。根据系统提示，输入节点的关键字，并以0作为结束的标识符。该功能由Bstree Create()函数实现。2) 插入二叉排序新的节点信息。每次只能够插入一个节点信息，如果该节点已经存在，则不插入。该功能由Bstree Insert(y)函数实现。3) 查询二叉排序树的信息。每次进行查询，成功则显示“查询到该节点”，不成功则“显示查询不到该节点“该功能由Bstree Search()函数实现。4) 删除二叉排序树的节点信息。可以对二叉排序树中不需要的节点进行删除，删除的方式是输入关键字，查询到该节点
3、后删除。该功能由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 t
4、ree,int key); /查找4) void Traverse(Bstree tree); /遍历5) Bstree Delete(Bstree tree,int key); /删除信息3. 函数主要的调用关系本系统9个子程序见的主要调用关系图3.Main()Main()Insert()Search( )Traverse ()Delete ()IV. 详细设计1. 数据类型定义本系统采用二叉树结构存储节点信息，节点定义如下： typedef struct Bstnodeint key;struct Bstnode *lchild,*rchild;Bstnode,* Bstree;2. 主要
5、子程序的详细设计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(keykey)
6、 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) print
7、f(查询到该节点！);flag=1;return(p);break;if (keykey) 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，可以插入
8、一个新的节点信息。运行的结果如图6.图6插入新的节点4. 查询二叉树的节点信息在主菜单下，用户选择3，首先通过输入关键字查询相关信息。运行的结果如图7. 图7查询节点信息5. 删除二叉树的节点在主菜单下，用户选择5，可以通过输入要删除的关键字来删除该节点的全部信息。运行的结果如图8. 图8删除二叉排序树的节点VI. 原程序清单#include#include#include/*二叉排序树的数据结构*/typedef struct Bstnodeint key;struct Bstnode *lchild,*rchild;Bstnode,* Bstree;Bstree Create(); /创建
9、二叉排序树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;/*
10、插入*/ Bstree Insert(Bstree tree,int key)Bstree p=tree;Bstree s,f;while (p!=NULL)f=p; if(key=p-key) return tree; if(keykey) 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; ret
11、urn 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 (keykey) p=p-lchild; else p=p-rchild; if(flag=0)printf(查询不到关键字为%d的节点！,key);return NULL; /*遍历*/void Traverse(Bstree tree)if(tree) Traverse(tree-lchild); p
12、rintf(%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-keykey) 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) tre
13、e=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;/*/voi
14、d 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
15、,&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: pr
16、intf(遍历所得序列为: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. 小结 由于为了简化程序的复杂度，本程序只以整形的关键字作为节点的唯一信息，但本程序能够很好的实现二叉排序树的基本操作。在调试程序过程中，对左右孩子的处理是难点，其中出现了许多的错误，但通过错误的改正也加深了对二叉排序树的认识。专心-专注-专业