二叉排序树中删除一个结点.docVIP

数据结构上机实验报告 题目：二叉排序树中删除一个结点 学生姓名 学生学号 学院名称 计算机学院 专 业 计算机科学与技术 时 间 2015.01.13  PAGE PAGE I 目 录 TOC \o 1-2 \h \u 27654 第一章 需求分析 1 29415 1.1 原题表述 1 4283 1.2 问题解决方案 1 3275 第二章 概要设计 2 4388 2.1 抽象数据类型 2 28395 2.2 主要算法描述 2 3664 第三章 详细设计 3 28515 3.1 程序代码 3 30212 第四章 调试分析 5 32323 4.1 出现的问题及解决方法 5 1045 第五章 测试分析 6 32287 5.1 测试样例 6 计算机学院2013级数据结构上机实验报告 PAGE PAGE 10 需求分析 原题表述 写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针p所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。给出删除节点之前和之后二叉排序树的输出表示。 示例： 对于如下所示的二叉排序树： 输出形式如下：4(0(,1(,3(2))),9(8(6(5,7)))) 1.2 问题解决方案 题目需要建立一个二叉排序树，之后输入节点数据，根据内容查找得到节点，然后对此节点进行删除操作。 第二章 概要设计 2.1 抽象数据类型 typedef struct Node{ int data; struct Node *left; struct Node *right; Node(int val){left = right = NULL,data = val;} }Node; 2.2 主要算法描述 void InsertTree(Node **root,int val) { if(root == NULL) return; Node *e = new Node(val); if(e == NULL) return; if(*root == NULL){ *root = e; } else{ Node *p = *root,*pre = NULL; while(p != NULL){ pre = p; if(e-data p-data){ p = p-left; } else if(e-data p-data){ p = p-right; } else{ delete e; return; } } if(e-data pre-data) pre-left = e; else{ pre-right = e; } } } void Delete_right(int m,Node * root) { Node * p=root,*pf,*q,*s; while(p!=NULLp-data!=m){ pf = p; if(p-data m) p=p-left; else p=p-right; } if(p == NULL){ printf(未找到该节点！\n); return; } else if(pf-right != p){ printf(该节点不是双亲的右节点，无法删除！\n); return; } else{ if(p-left == NULL){ pf-right = p-right; return; } else if(p-right == NULL){ pf-right = p-left; return; } else{ q=p; s=q-left;