2009/12/29 9.2.1-二叉排序树：查找举例 9.2.1-二叉排序树：查找算法 ·查找算法（算法9.5(a)) 基于二叉树先序遭历 BiTree SearchBST(BiTree T,KeyType key){ 查找key=70? ∥在根指针T所指二叉排序树中查找某关键字等于 23 66 ∥ky的数据元素，若查找成功，则返回指向该数据 查找key=28? 元素结点的指针，否则返回空指针 097099 f(TEQ(key,T->data.key》return(T:∥查找结束 else if(LT(key,T->data.key)) return(SearchBST(T->lchild,key)); else return(SearchBST(T->rchild,key)); 371103 备 38/103 圄 9.2.1-二叉排序树：插入 9.2.1-二叉排序树：改进的查找算法 二叉排序树的插入 。改写查找算法为算法9.5(b): 。新插入的结点一定是一个新深加的 Status SearchBST(BiTree T.KeyType key,BiTree f.BiTree &p){ 叶子结点并且是查找不成功时查找 33 ∥若查找成功，则指针指南试最调元素结点，并运图 略径上访问的最后一个结点的左孩 ∥T取UE,否则指针推向查找路径上访间的最后一个结点并 子或右盛子结点 运回FALSE,指针指向T的京亲：其初地调用值为NUL山 ,示例：从空树出发，待插的关镀字 if (T)(p-f;return FALSE; ebse if (EQ(key,T->data.key))(p-T;return TRUE:} 序列为33,44,23,46,12,37 else if (LT(key,T->data.key)) 中序遗历二叉排序树可得到一个关键字的有序序列。 return SearehBST(Tlchild,key.T,p): 该例中，中序遗历结果为：12,23,33,37,44,46 else return SearchBST(Trchild,key,T,p): 39/103 40/103 图 9.2.1-二叉排序树：插入算法 9.2.1-二叉排序树：删除1 ·二叉排序树的擂入算法9.6： ■二叉排序树的副除 Status Ins ertBST(BiTree &T,ElemType e) ∥当二又排序刺T中不存在关辅字等于：key的兼烟元素时，插 假设被副结点为°p,其双亲结点为*， 入e并返回IRLE:否则延回FAL.SE 。*p为叶子结点：副去*p,并修政f的孩子域。 if(SearchBST(T,e.key,NLp){H查找不成功 ,p只有左子树P或只有右子树Pk:令P或P.直接成 s-(BiTree)malloc(sizeof(BiTNode)): data-e;slchild -s->rchild-NULL: 为的子树 (p)T∥被结点为新的视结点 33 else if(LT(e.key,p->data.key))p>lchild-s p>rchild一s∥被插结点为右孩子 return TRUE; }else return FALSE:∥树中已有关字湘同的点，不再入 12 41/103 42/103 圄 72009/12/29 7 9.2.1 -二叉排序树:查找举例 45 23 66 查找key=70? 37/103 4 34 48 30 44 87 70 99 36 69 查找key=28? 9.2.1 -二叉排序树:查找算法  查找算法( 算法9.5(a) ) ——基于二叉树先序遍历 BiTree SearchBST(BiTree T, KeyType key){ // 在根指针T所指二叉排序树中查找某关键字等于 38/103 // key的数据元素，若查找成功，则返回指向该数据 //元素结点的指针，否则返回空指针 if (!T || EQ(key, T->data.key)) return (T); // 查找结束 else if (LT(key, T->data.key) ) return(SearchBST(T->lchild, key)); else return(SearchBST(T->rchild, key)); } 9.2.1 -二叉排序树: 插入  二叉排序树的插入  新插入的结点一定是一个新添加的 叶子结点,并且是查找不成功时查找 33 39/103 路径上访问的最后一个结点的左孩 子或右孩子结点.  示例：从空树出发，待插的关键字 序列为33,44,23,46,12,37 23 44 12 37 46 中序遍历二叉排序树可得到一个关键字的有序序列。 该例中，中序遍历结果为：12, 23, 33, 37, 44, 46 9.2.1 -二叉排序树:改进的查找算法  改写查找算法为算法9.5(b)： Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){ // 若查找成功，则指针p指向该数据元素结点，并返回 // TRUE 否则指针 指向查找路径上访问的最后 个结点并 40/103 // TRUE；否则指针p指向查找路径上访问的最后一个结点并 //返回FALSE。指针f 指向T的双亲，其初始调用值为NULL if (!T) { p=f; return FALSE;} else if ( EQ(key, T->data.key)) { p=T; return TRUE; } else if ( LT(key, T->data.key) ) return SearchBST(T->lchild, key, T, p); else return SearchBST(T->rchild, key, T, p); } 9.2.1 -二叉排序树:插入算法  二叉排序树的插入算法9.6： Status InsertBST(BiTree &T, ElemType e){ // 当二叉排序树T中不存在关键字等于e.key的数据元素时，插 //入e 并返回TRUE；否则返回FALSE 41/103 if (!SearchBST(T, e.key, NULL, p)) { // 查找不成功 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; else p->rchild = s; // 被插结点*s为右孩子 return TRUE; } else return FALSE; // 树中已有关键字相同的结点，不再插入 } 9.2.1 -二叉排序树:删除1  二叉排序树的删除 假设被删结点为*p，其双亲结点为*f，  *p为叶子结点：删去*p，并修改*f 的孩子域。 42/103 p p  *p只有左子树PL或只有右子树PR：令PL或PR直接成 为*f 的子树 33 23 44 12 37 46 33 23 44 12 46 45 46 45 46