Chap7_算法与数据结构—C语言描述(第2版)张乃孝编课件2.ppt

第7章 高级字典结构 7.3二叉排序树 定义 定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值 它的左、右子树也分别为二叉排序树 二叉排序树的检索 二叉排序树的插入 插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子 二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树 插入算法 二叉排序树的删除 * * 10 18 3 8 12 2 7 4 在下面给出的检索算法中，设在二叉排序树上查找关键码为key的结点，算法结束时返回检索成功或失败的标志。并且检索成功时，position指向查找到的结点指针；检索失败时，position指向该结点应插入位置的父结点。 int search (PBinSearchTree ptree, KeyType key, PBinSearchNode *position) 10 18 3 8 12 2 7 4 例 {10， 18， 3， 8， 12， 2， 7， 4} 10 10 18 10 18 3 10 18 3 8 10 18 3 8 12 10 18 3 8 12 2 10 18 3 8 12 2 7 10 18 3 8 12 2 7 4 中序遍历二叉排序树可得到一个关键字的有序序列 int insert (PBinSearchTree ptree, KeyType key) 为了删除一个二叉树中的结点，必须首先找到这个结点，然后选择下面给出两种方法删除之，以保证删除后仍满足二叉排序树的定义。 第一种方法∶ (1)? 如果被删除结点p没有左子树，则用p的右子女代替p。 (2)? 否则，在p的左子树中，找出关键码最大的一个结点r ( r 处于p的左子树中最右下角的位置，r 一定无右子女)，将r 的右指针指向p的右子女，用p的左子女代替p结点。 第二种方法∶ (1)? 同第一种方法的(1)。 (2)? 同第一种方法找到r结点，用r结点代替被删除的结点p，p原来的左右子女不变。并且用原来r的左子女代替原来的r结点。