数据结构-查找ds_chap(编辑修改稿)

数据结构-查找ds_chap(编辑修改稿)内容摘要：

结点的左孩子或右孩子结点。 插入前必须要查找，以确定要插入的位置，因此必须修改二叉排序树的查找算法 查找不成功时必须 返回插入的位置 南昌航空大学计算机学院 /软件学院 第 8章 查找 动态查找表 —— 二叉排序树  二叉排序树查找的递归算法 （ 查找不成功时返回插入的位置 ）  Status SearchBST(BiTree T， KeyType key， BiTree f， BiTree amp。 p){ //在根指针 T所指二叉排序树中递归地查找其关键字等于 key的数据元素， //若查找成功，则指针 p指向该数据元素结点，并返回 TRUE， //否则指针 p指向查找路径上访问的最后一个结点并返回 FALSE， //指针 f指向 T的双亲，其初始调用值为 NULL if (!T) { p=f； return FALSE； } //查找不成功 else if EQ(key, T) { p=T； return TRUE； } //查找成功 else if LT(key,T) SearchBST(Tlchild,key,T,p)； //在左子树中继续查找 else SearchBST(Trchild,key,T,p)； //在右子树中继续查找 }//SearchBST 南昌航空大学计算机学院 /软件学院 第 8章 查找 动态查找表 —— 二叉排序树 二叉排序树的插入算法  Status InsertBST(BiTree amp。 T， ElemType e){ //当二叉排序树 T中不存在关键字等于 ,插入 e并返回 TRUE，否则返回 FALSE if (!SearchBST(T， ， NULL， p){ //查找不成功 s=(BiTree)malloc(sizeof(BiTNode))； sdata=e； slchild =srchild=NULL； if (!p) T = s； //被插结点 *s为新的根结点，原树为空 else if LT(， p) plchild=s； //被插结点 *s为左孩子 else prchild=s //被插结点 *s为右孩子 return TRUE； } else return FALSE。 //树中已有关键字相同的结点，不再插入 }// InsertBST 南昌航空大学计算机学院 /软件学院 第 8章 查找 动态查找表 —— 二叉排序树 二叉排序树的建立  依次输入数据 { 53,78,65,17,87,09,81,15}， 建立二叉排序树 53 53 78 53 78 65 53 78 65 17 53 78 65 87 17 53 78 65 09 17 87 53 78 65 81 17 87 09 53 78 65 15 17 87 09 81 南昌航空大学计算机学院 /软件学院 第 8章 查找 动态查找表 —— 二叉排序树 二叉排序树的建立 重复插入 中序遍历二叉排序树，得到升序序列 建立的过程即为对无序序列进行排序的过程 二叉排序树既拥有类似于折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示 同样 n3 个数据，如果输入顺序不同，建立起来的二叉排序树的形态也不同，这直接影响到二叉排序树的查找性能。 南昌航空大学计算机学院 /软件学院 第 8章 查找 动态查找表 —— 二叉排序树 二叉排序树的建立算法 void CreateBST(BSTree bst) /*从键盘输入元素的值，创建相应的二叉排序树 */ { KeyType key。 bst=NULL。 scanf(%d, amp。 key)。 while (key!=ENDKEY) /*ENDKEY为自定义常数 */ { InsertBST(bst, key)。 scanf(%d, amp。 key)。 } } 南昌航空大学计算机学院 /软件学院 第 8章 查找 动态查找表 —— 二叉排序树 二叉排序树的删除 在二叉搜索树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉搜索树的性质不会失去。 为保证在删除后树的搜索性能不至于降低，还需要防止重新链接后树的高度增加。 分四种情况进行讨论 删除 叶结点 被删结点缺右子树 被删结点缺左子树 被删结点左、右子树都存在 单分支结点 双分支结点 南昌航空大学计算机学院 /软件学院 第 8章 查找 动态查找表 —— 二叉排序树 二叉排序树的删除 删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可。 53 78 65 17 87 09 23 45 删除 65 双亲结点指针清零 53 78 17 87 09 23 45 南昌航空大学计算机学院 /软件学院 第 8章 查找 动态查找表 —— 二叉排序树 二叉排序树的删除 被删结点缺右子树，可以拿它的左子女结点顶替它的位置，再释放它。 53 78 65 17 87 09 23 45 删除 45 缺右子树 , 用左子女顶替 53 78 65 17 87 09 23 南昌航空大学计。