资源描述：
《二叉排序树的建立、插入、删除和查找》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、题目：二叉排序树的建立、插入、删除和查找完成日期：2010-7-一、需求分析1、运行环境：VC++6.0;语言：C语言；程序所实现的功能：给出一组关键值，建立相应的二叉排序树，完成：1结点的删除操作，插入一个新结点的操作2对给定的值在二叉排序树进行查找；3随时显示操作的结果。2、程序的输入：n个关键字，及要插入，删除，查找的关键字；3、程序的输出：操作后的二叉排序树的中序序列即递增序列；4、测试数据：1）812510611139（n=8）;10；7；11；2）1071298（n=5）;10;6;10
2、;3)856(n=3);6;9;8;二、概要设计1、程序的主要流程图：否是开始建树：①依次输入n个关键字②插入二叉排序树中③中序输出创建过程删除任意结点插入一个结点查找关键字中序输出操作后二叉排序树是否继续结束72、主要模块：1）主函数模块Main(){建立n个关键字的二叉排序树并输出；从二叉树排序树T中删除任意结点,其关键字为x；在二叉树排序树T中，插入一个结点t,其关键字为key1；在二叉排序树T中递归查找关键字等于key2的数据元素；查找成功则输出SUCCESS；查找失败则输出NOSUCCES
3、S；}2）创建二叉排序树模块BiTreeCreatBST(intn){建立n个关键字的二叉排序树；从键盘输入调建立n个关键字依次用InsertBST1（插入函数）；返回根结点T；输出过程；}3）删除模块DeleteNode(BiTree&T,intx){从二叉树排序树T中删除任意结点,其关键字为x；可以实现删除根结点、叶子结点以及其它任意结点的功能；}4）插入模块voidInsertBST1(BiTree&T,BiTNode*s){在二叉树排序树T中，插入一个结点s(递归算法)；被CreatBST函
4、数调用；}5）查找模块BiTreeSearchBST1(BiTreeT,TElemTypekey){在根指针T所指二叉排序树中递归查找关键字等于key的数据元素；若成功，返回指向该数据元素结点的指针；否则返回空指针；}3、抽象数据类型设计；对于二叉树排序树而言，每个节点都是由“数据域”、左右“指针域”三部分组成的，因此将二叉树抽象成一个指向根结点由“关键字，左右孩子”构成的二叉链表。三、详细设计71、二叉排序树数据类型定义；typedefstructBiTNode{TElemTypedata;str
5、uctBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;BiTreeT;//二叉树排序树T2、主要函数说明：（伪代码及算法设计思想）voidmain(){T=CreatBST(n);//建立n个关键字的二叉排序树,返回根结点T//从二叉树排序树T中删除任意结点,其关键字为xDeleteNode(T,x);Inorder(T);//在二叉树排序树T中，插入一个结点t,其关键字为key1t=(BiTree)malloc(sizeof(BiTNode));t-
6、>data=key1;t->lchild=NULL;t->rchild=NULL;InsertBST1(T,t);Inorder(T);//在二叉排序树T中递归查找关键字等于key2的数据元素s=SearchBST1(T,key2);if(s)printf("SUCESS");//查找成功elseprintf("NOSUCESS");//查找失败}BiTreeSearchBST1(BiTreeT,TElemTypekey){//在根指针T所指二叉排序树中递归查找关键字等于key的数据元素//
7、若成功，返回指向该数据元素结点的指针，否则返回空指针；s为返回//指针if(T==NULL)returnNULL;if(T->data==key)s=T;elseif(T->data>key)//key大于当前结点的关键字，则查找左子树s=SearchBST1(T->lchild,key);//key小于当前结点的关键字则查找右子树Elses=SearchBST1(T->rchild,key);returns;}voidInorder(BiTreeT){//中序输出二叉树排序树T(非空时)if(T!
8、=NULL)7{Inorder(T->lchild);//中序输出左子树printf("%3d",T->data);//访问结点Inorder(T->rchild);//中序输出右子树}}voidInsertBST1(BiTree&T,BiTNode*s){//在二叉树排序树T中，插入一个结点s的递归算法t=SearchBST1(T,s->data);//若s的关键字不在T中出现，则插入if(!t){if(T==NULL)T=s;//空树时作为根结点elseif(s-
