二叉排序树的创建删除插入等操作及二杈线索存储表示.doc

武 汉 工 程 大 学 计算机科学与工程学院 《数据结构》实验报告 专业班级 09计算机工程01 实验地点 419 学生学号 0905080116 指导教师 蔡琼 学生姓名 沈亮 实验时间 实验项目 查找技术综合应用 实验类别 操作性（）验证性（ ）设计性（ ）综合性（Y ）其它（ ） 实验目的及要求 （1）熟练掌握查找的常用算法； （2）熟练设计和应用查找算法解决比较简单的实际问题。 成 绩 评 定 表 类 别 评 分 标 准 分值 得分 合 计 上机表现 积极出勤、遵守纪律 认真完成实验任务 30分 报告质量 程序代码规范、功能正确 填写内容完整、体现收获 70分 说明： 评阅教师： 日 期： 年 月 日  实验内容：二叉排序树。 任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。 实验说明： 二叉排序树存储结构如下： typedef struct typedef 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, * BSTre