二叉查找树的插入和删除操作

插入操作

public void insertBST(int val){
    TreeNode p=root;
    
    // 父节点
    TreeNode prev=null;

    while(p!=null){
      prev = p;
      if(val<p.val) p = p.left;
      else if(val>p.val) p=p.right;
      else return;
    }
    // prev是待插入节点的父节点，根据节点值的大小，决定被插入的位置
    if(root==null)root=new TreeNode(val);
    else if(val<prev.val)prev.left=new TreeNode(val);
    else prev.right=new TreeNode(val);

}

删除操作

分为三种情况：要删除的节点为p，其父节点为f

1. 要删除的p节点是叶子节点，只需要修改他的双亲节点的指针为空
2. 若p只有左子树或者只有右子树，则直接让左子树或右子树代替p
3. 若p既有左子树悠悠右子树，则用p左子树中最大的值（即最右端S）代替p，删除S，重接其左子树

public void deleteBST(int val){
  deleteBST(root,val);
}

private boolean deleteBST(TreeNode node,int val){
  if(node==null) return false;
  if(val==node.val)return delete(node);
  else if(val<node.val)return deleteBST(node.left,val);
  else return deleteBST(node.right,val);
}

private boolean delete(TreeNode node){
  TreeNode temp=null;
  // 右子树为空，只需要重接他的左子树
  // 如果是叶子节点，则再这里也把叶子节点删除了
  if(node.right==null){
    temp=node;
    node=node.left;
  }else if(node.left==null){
    temp=node;
    node=node.right;
  }else {
    temp=node;
    TreeNode s=node;
    // 转向左子树，然后向右走到尽头
    s = s.left;
    while(s.right!=null){
      temp=s;
      s=s.right;
    }
    node.val=s.val;

    if(temp!=node)temp.right=s.left;
    else temp.left=s.left;
  }
  return true;
  
}

赏

谢谢你请我吃糖果

微信