二叉查找树

二叉查找树是一种支持查找,删除,排序的数

在排序上可以说是动态 的, 即随时告诉我们排序(中序遍历)

在二元排序树b中查找x的过程为:

  1. 若b是空树,则搜索失败,否则:
  2. 若x等于b的根节点的数据域之值,则查找成功;否则:
  3. 若x小于b的根节点的数据域之值,则搜索左子树;否则:
  4. 查找右子树。

插入则是一直找

删除分情况:
A:无子树,直接删
B:有一个子树,直接将其子树代替删除点
C:有两个子树
1.先找左子树的最大值,向右递归直至无右子树的点最大

q=p;

    s=p->lchild;
while(s->rchild){ 
      q=s; 
      s=s->rchild;
}

此时p为删点地址,q为最右子父,s为最右子

 p->data = s->data;

直接搬移本身的值,不必删地址,这样不需要维护关系

问题转化为删无右子树的s

 if(q!=p)    
      q->rchild = s->lchild; //维护s,把s跳过     
else 
      q->lchild = s->lchild; //还是维护被删代替p(该子树的根)的s   此处s为q的左子树根 故特判
delete s;
}

自此树便建立了