动态查找---二叉排序树

二叉排序树：

若它的左子树不为空，则左子树上所有结点均小于根节点的值。若它的右子树不为空，则右子树上所有结点均大于根节点的值。它的左，右子树分别也是二叉排序树 注： 因此，二叉排序树中序遍历是有序序列。 查找： 每次和根结点进行比较，若根结点的值等于key,返回true,若根节点的值大于key,则访问根的左子树，否则访问右子树。（类似折半查找） bool Search(BiTree T,int key){ if(!T){ cout<<"未找到！"<<endl; return false; } else{ if(T->date==key){ cout<<"查找成功"<<endl; return true; } if(T->date>key) return Search(T->lchild,key); else return Search(T->rchild,key); } } 动态查找： 未到到时，进行插入。

核心思想： 首先要明确，插入的一定是叶子结点（不相等的时候一直往下递归，为空的之后才跳出）。因此，需要标记要插入的位置（p），所以在遍历的时候需要一个指针进行跟踪（f）,通过f把位置传给p。

bool Search_Insert(BiTree &T,int key,BiTree f,BiTree &p){ if(!T){ p=f; return false; } else if(T->date==key){ p=f; cout<<"查找成功"<<endl; return true; } else if(T->date>key) return Search_Insert(T->lchild,key,T,p); else return Search_Insert(T->rchild,key,T,p); } bool Insert(BiTree &T,int key){ if(!Search_Insert(T,key,f,p)){ Node *s=new Node; s->date=key;//插入的结点一定是叶子结点 s->lchild=NULL; s->rchild=NULL; if(!p) //树为空 T=s; else if(key<p->date) p->lchild=s; else p->rchild=s; return true; } return false; } 动态查找： 找到时，进行删除。

核心思想： 若删除的叶子结点，直接删除； 若删除的结点只有左孩子或者右孩子，直接它的左孩子或者右孩子代替该节点。 若删除结点左，右子树都不为空，则进行查找它的前驱，即它的左子树的右子树最右的一个结点。以这个结点替代删除的结点。 1>如果它的左子树的右子树为空时，直接用它的左孩子(s)替代删除的结点，然后将左孩子的接在该结点。 2>左孩子的右子树不为空的时候，用右子树的最后一个结点（s）代替删除结点，然后将该结点的后续接在该结点根节点(q)的右孩子。

bool Search_Delete(BiTree &T,int key){ if(!T){ cout<<"查找失败"<<endl; return false; } else{ if(T->date==key) return Delete(T); else if(T->date<key) return Search_Delete(T->rchild,key); else return Search_Delete(T->lchild,key); } } bool Delete(BiTree &p){ Node *q; if(!p->lchild){//删除结点只有右子树 q=p; p=p->rchild; delete(q); } else if(!p->rchild){//删除结点只有左子树 q=p; p=p->lchild; delete(q); } else{//左右子树均不为空 q=p;//s代表前驱，q是删除结点 Node *s=p->lchild;//找删除结点的前驱(左孩子的最后一个右孩子) while(!s->rchild){ q=p; s=s->rchild; } p->date=s->date; if(p==q)//左孩子没有右孩子的时候 q->lchild=s->lchild; else q->rchild=s->lchild;//此时,s没有右孩子 } return true; }