动态查找表 二叉排序树的插入算法 Status Insert BST(BiTree &T, ElemType e) f if (! SearchBST(T,e key, NULL, p)) d S=(BiTree)malloc(sizeof(BiTNode)) S->data=e: s->lchild=s->rchildNULL if( p)t=s: else if (lt(e key, p->data key) p->lchild=s: else p-rchild=s return TRUE return FALSE (结合图98说明二叉排序树的构造过程)
动态查找表 ◼ 二叉排序树的插入算法 Status Insert_BST(BiTree &T, ElemType e) { if ( ! SearchBST(T, e.key, NULL, p)) { s=(BiTree) malloc (sizeof(BiTNode)); s->data=e; s->lchild=s->rchild=NULL; if (! p) T=s; else if (LT(e.key, p->data.key)) p->lchild=s; else p-rchild=s; return TRUE; } return FALSE; } (结合图9.8说明二叉排序树的构造过程)
动态查找表 二叉排序树的删除 (在二叉排序树中删除个结点相当于删除有序序列中一个结点, 而不是删除以该结点为根的子树。) 删除操作首先进行査找,以确定被删结点是否在二叉排序树 中,若不在,则不做任何事情;否则,删除操作可按结点是否有 左子树(或右子树)来处理。 1)若p结点为叶子结点,即p1和p均为空; (2)若p结点只有左子树p或右子树p; (3)若p结点的左子树p和右子树p2均不空
动态查找表 ◼ 二叉排序树的删除 (在二叉排序树中删除一个结点相当于删除有序序列中一个结点， 而不是删除以该结点为根的子树。) 删除操作首先进行查找，以确定被删结点是否在二叉排序树 中，若不在，则不做任何事情；否则，删除操作可按结点是否有 左子树（或右子树）来处理。 （1）若p结点为叶子结点，即pL和pR均为空； （2）若p结点只有左子树pL或右子树pR； （3）若p结点的左子树pL和右子树pR均不空
动态查找表 二叉排序树的删除算法 Status Delete BST(BiTree&t, Key Type key) i if ( t) return FALSE else if (EQ(key, T->data key)) Delete(T, f else if (LT(key, T->data. key)Delete BST(T->lchild, key) else Delete BST(T->rchild, key) return trUe
动态查找表 ◼ 二叉排序树的删除算法 Status Delete_BST(BiTree &T, KeyType key) { if (! T) return FALSE; else if (EQ(key, T->data.key)) Delete(T, f ); else if (LT(key, T->data.key)) Delete_BST(T->lchild, key); else Delete_BST(T->rchild, key); return TRUE; }
动态查找表 二叉排序树的删除算法 Void Delete(BiTree &p, BiTree &f) f if ( P->rchild &a=p; p=p->lchild; f->lchild=p: free(a); else if(! P->lchild i a=p; p=p->rchild; f->lchild=p: free(@);) else q=p: s=p->lchild while(s->rchild) q=s: S=S->rchild; p->data=S->data if(ql=p)q->rchild=s->lchild else q->lchild=s->lchild
动态查找表 ◼ 二叉排序树的删除算法 Void Delete(BiTree &p, BiTree &f) { if (! P->rchild) { q=p; p=p->lchild; f->lchild=p; free(q); } else if (! P->lchild) { q=p; p=p->rchild; f->lchild=p; free(q); } else { q=p; s=p->lchild; while (s->rchild) { q=s; s=s->rchild;} p->data=s->data; if (q!=p) q->rchild=s->lchild; else q->lchild=s->lchild; } }
动态查找表 二叉排序树的查找分析 例:(参见:P231图910) ASL(a)=(1+2+2+3+3+3)/6=14/6 ASL(b)=(12+34+5+6)/6=21/6 结论:形态均称的二叉排序树的平均查找长度小,效率 高
动态查找表 ◼ 二叉排序树的查找分析 例： （参见：P231-图9.10） ASL(a)=(1+2+2+3+3+3)/6=14/6 ASL(b)=(1+2+3+4+5+6)/6=21/6 结论：形态均称的二叉排序树的平均查找长度小，效率 高