My WordPress Site

二叉查找树

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

在排序上可以说是动态 的， 即随时告诉我们排序（中序遍历）

在二元排序树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;
}

自此树便建立了

nike0good