数据结构 第九章 静态查找.ppt

3．二叉排序树的插入算法 根据动态查找表的定义，“插入”操作在查找不成功时才进行； 二、二叉平衡树 何谓“二叉平衡树”？ 若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。 Status Insert BST(BiTree T, ElemType e ) { // 当二叉排序树中不存在关键字等于 e.key 的 // 数据元素时，插入元素值为 e 的结点，并返 // 回 TRUE; 否则，不进行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p )) // 查找不成功 { } // 插入 else return FALSE; // 查找成功 } // Insert BST …… s = (BiTree) malloc (sizeof (BiTNode)); // 为新结点分配空间 s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; // 插入 s 为新的根结点 else if ( LT(e.key, p-data.key) ) p-lchild = s; // 插入 *s 为 *p 的左孩子 else p-rchild = s; // 插入 *s 为 *p 的右孩子 return TRUE; // 插入成功 (1) 被删除的结点是叶子； (2) 被删除的结点只有左子树或者只有右子树； (3) 被删除的结点既有左子树，也有右子树。 4．二叉排序树的删除算法 可分三种情况讨论： 和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。 50 30 80 20 90 85 40 35 88 32 (1) 被删除的结点是叶子结点 例如: 被删关键字 = 20 88 其双亲结点中相应指针域的值改为“空” 50 30 80 20 90 85 40 35 88 32 (2) 被删除的结点只有左子树或者只有右子树 其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。 被删关键字 = 40 80 50 30 80 20 90 85 40 35 88 32 (3) 被删除的结点既有左子树，也有右子树 40 40 以其前驱替代之，然后再删除该前驱结点 被删结点 前驱结点 被删关键字 = 50 Status DeleteBST (BiTree T, KeyType key ) { // 若二叉排序树 T 中存在其关键字等于 key 的 // 数据元素，则删除该数据元素结点，并返回 // 函数值 TRUE，否则返回函数值 FALSE if (!T) return FALSE; // 不存在关键字等于key的数据元素 else { } } // DeleteBST 算法描述如下： … … if ( EQ (key, T-data.key) ) // 找到关键字等于key的数据元素 else if ( LT (key, T-data.key) ) else { Delete (T); return TRUE; } DeleteBST ( T-lchild, key ); // 继续在左子树中进行查找 DeleteBST ( T-rchild, key ); // 继续在右子树中进行查找 void Delete ( BiTree p ){ // 从二叉排序树中删除结点 p， // 并重接它的左子树或右子树 if (!p-rchild) { } // 右子树为空 els