(1)将指针S所指的结点插入到根结点指针为T的 二叉排序树中的算法 void Insert bst( BiTree &t, BiTree S) i BiTree p, q: if(!T)T-S elsei p=t while( p) i q=p if (S->data. key p->data. key)p=p->lchild else p= p->rchild f(S->data. key q->dat. key) q->lchild=S else g->rchild=S return
（1）将指针S所指的结点插入到根结点指针为T的 二叉排序树中的算法 void Insert_BST( BiTree &T, BiTree S ) { BiTree p, q; if(!T) T=S; else { p=T; while ( p ) { q = p; if (S->data.key < p->data.key) p = p->lchild; else p = p->rchild; } if (S->data.key < q->dat.key) q->lchild = S; else q->rchild = S; } return; }
(2)输入一组数据元素的序列,构造二叉排序树 的算法 void Creat BSt( BiTree &t i int x; BiTree S; T-NULL while( scanf ("%d, &x), x!=0) iS=(BiTNode s)malloc(sizeof(BitNode)) S→>data.key=x S-lchild= NUlL S->rchild= NULL Insert BST( T,S) return
（2）输入一组数据元素的序列，构造二叉排序树 的算法 void Creat BST( BiTree &T ) { int x; BiTree S; T=NULL; while ( scanf ( “%d”,&x), x!=0 ) { S = (BiTNode *) malloc(sizeof(BitNode)); S->data.key = x; S->lchild = NULL; S->rchild = NULL; Insert_BST( T,S ); } return; }
4)二又排序树上的查找(动态查找) int Searh BSt( BiTree t, int key t BiTree p,a,s,p=T while(p) if( p->data key=- key) return(1) else if p->data. key key) qp; p=p->lchild; 1 else(=p; p=p->rchild; i S=(BiTNode s)malloc(sizeof( BitNode)) S->data. key key; S->lchild=S->rchild=NULL if(!T)T=S else if q->data. key key )q->lchild=s leq-→> rchild=S; return(O) 说明:(1)正常情况下,返回0是未找到,但实际上已经插入 (2)也可以用 return返回一个自己定义的标志值
4) 二叉排序树上的查找（动态查找） int Searh_BST( BiTree T, int key ) { BiTree p, q, S, p = T; while ( p ) if ( p->data.key == key ) return(1); else if ( p->data.key > key) { q=p; p=p->lchild; } else {q=p; p=p->rchild; } S = (BiTNode *) malloc(sizeof(BitNode)); S->data.key = key; S->lchild=S->rchild=NULL; if (!T) T=S; else if ( q->data.key > key ) q->lchild=S; else q->rchild=S; return(0); } 说明：（1）正常情况下，返回0是未找到，但实际上已经插入； （2）也可以用return返回一个自己定义的标志值
5)二叉排序树的删除 ☆要求:删除一个结点后,仍然保持二叉排序树 的有序性 删除结点的算法: (1)确定被删除结点: A.有没有被删除的结点; B.若有,则确定被删除的结点是根结点还 是一般结点 (2)如果被删除结点是根结点,则调用删除根结点的 算法; (3)如果被删除结点是一般结点,则调用删除一般结 点的算法
❖ 要求：删除一个结点后，仍然保持二叉排序树 的有序性 删除结点的算法： （1）确定被删除结点： A. 有没有被删除的结点； B. 若有，则确定被删除的结点是根结点还 是一般结点 （2）如果被删除结点是根结点，则调用删除根结点的 算法； （3）如果被删除结点是一般结点，则调用删除一般结 点的算法。 5) 二叉排序树的删除
删除二叉排序树的根结点的算法 1)根结点有左右子树的情况下,选择根结点的 左子树中的最大结点为新的根结点;/或者是 右子树中的最小结点为新的根结点; 最大结点—中序遍历 (2)如果根结点没有左子树,则以右子树的根 结点作为新的根结点; (3)如果根结点没有右子树,则以左子树的根 结点作为新的根结点
删除二叉排序树的根结点的算法 （1） 根结点有左右子树的情况下，选择根结点的 左子树中的最大结点为新的根结点；/或者是 右子树中的最小结点为新的根结点； ** 最大结点——中序遍历 （2）如果根结点没有左子树，则以右子树的根 结点作为新的根结点； （3）如果根结点没有右子树，则以左子树的根 结点作为新的根结点