二叉排序树的创建、删除、插入等操作.doc

安徽工程大学计算机与信息学院课程设计报告课程名称 《数据结构》 课题名称 二叉排序树的创建、删除、插入操作专 业 计算机科学与技术 班 级 计算机121班 学 号 3120701140 姓 名 殷世军 联系方式 指导教师 姚红燕 实验内容：二叉排序树。 任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。实验说明： 二叉排序树存储结构如下：typedef structtypedef struct BiTNode { // 结点结构 struct BiTNode *lchild, *rchild; // 左右孩子指针} BiTNode, *BiTree; 二叉排序树插入算法伪代码如下：1. 若root是空树，则将结点1. 若root是空树，则将结点s作为根结点插入；否则2. 若s-data＜root-data，则把结点s插入到root的左子树中；否则3. 把结点s插入到root的右子树中。二叉排序树中删除一个结点f的左孩子结点p算法伪代码如下：1. 若结点p是叶子，则直接删除结点p；1. 若结点p是叶子，则直接删除结点p； 2. 若结点p只有左子树，则只需重接p的左子树； 若结点p只有右子树，则只需重接p的右子树； 3. 若结点p的左右子树均不空，则 3.1 查找结点p的右子树上的最左下结点s以及结点s的双亲结点par；3.2 将结点s数据域替换到被删结点p的数据域；3.3 若结点p的右孩子无左子树，则将s的右子树接到par的右子树上；否则，将s的右子树接到结点par的左子树上；3.4 删除结点s；1.实验分析：程序的主要流程图： 否否是开始建树： = 1 \* GB3 ① 依次输入n个关键字 = 2 \* GB3 ② 插入二叉排序树中 = 3 \* GB3 ③ 中序输出创建过程删除任意结点插入一个结点查找关键字中序输出操作后二叉排序树是否继续结束主要模块： 1）主函数模块 Main(){建立n个关键字的二叉排序树并输出；从二叉树排序树T中删除任意结点,其关键字为key；在二叉树排序树T中，插入一个结点t,其关键字为key；在二叉排序树T中递归查找关键字等于 key2 的数据元素；}2）创建二叉排序树模块BiTree CreatBST(int n){建立n个关键字的二叉排序树； 从键盘输入调建立n个关键字依次用InsertBST1（插入函数）； 返回根结点T； 输出过程；} 3）删除模块DeleteNode(BiTree T, int x){从二叉树排序树T中删除任意结点,其关键字为x； 可以实现删除根结点、叶子结点以及其它任意结点的功能；} 4）插入模块void InsertBST1(BiTree T,BiTNode *s){在二叉树排序树T中，插入一个结点s(递归算法)； 被CreatBST函数调用；} 5）查找模块BiTree searchBST1(BiTree T,TElemType key){在根指针T所指二叉排序树中递归查找关键字等于 key 的数据元素； 若成功，返回指向该数据元素结点的指针； 否则返回空指针；}2.源程序代码：#includeiostream.using namespace std;typedef int KeyType;typedef struct tree//声明树的结构{ struct tree *left; //存放左子树的指针 struct tree *right; //存放又子树的指针 KeyType key; //存放节点的内容} BSTNode, * BSTree; //声明二叉树的链表BSTree insertBST(BSTree tptr,KeyType key)// 在二叉排序树中插入结点 { //若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回 BSTree f,p=tptr; //p的初值指向根结点 while(p) //查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲 { if(p-key==key) //树中已有key，无须插入 ret