无法理解二叉搜索树删除

Question

我试图通过这个链接BinarySearchTree来理解BST。但我在其他部分感到困惑

 /* Functions to delete data */
 public void delete(int k)
 {
     if (isEmpty())
         System.out.println("Tree Empty");
     else if (search(k) == false)
         System.out.println("Sorry "+ k +" is not present");
     else
     {
         root = delete(root, k);
         System.out.println(k+ " deleted from the tree");
     }
 }
 private BSTNode delete(BSTNode root, int k)
 {
     BSTNode p, p2, n;
     if (root.getData() == k)
     {
         BSTNode lt, rt;
         lt = root.getLeft();
         rt = root.getRight();
         if (lt == null && rt == null)
             return null;
         else if (lt == null)
         {
             p = rt;
             return p;
         }
         else if (rt == null)
         {
             p = lt;
             return p;
         }
         else
         {
             p2 = rt;
             p = rt;
             while (p.getLeft() != null)
               p = p.getLeft();
             p.setLeft(lt);
             return p2;
         }
     }
     if (k < root.getData())
     {
         n = delete(root.getLeft(), k);
         root.setLeft(n);
     }
     else
     {
         n = delete(root.getRight(), k);
         root.setRight(n);             
     }
     return root;
 }

我不能理解其他部分，其中左大部分节点的右子树被找到，然后分配到该节点。但在这里，该节点都不为空，并且返回右节点，这对我来说是没有意义的。我希望这是一个正确的实现。有人能帮我了解一下这里发生了什么吗。

Answer 1

这段代码中的最后一个else块涵盖了删除具有两个子节点的情况。

代码似乎要做的是：

• 查找按顺序的后继节点（即右侧子树中最左侧的节点）
• 将整个原始左子树追加到此节点
• 返回原来的右子级作为树的新根