java - 二叉树 : method remove subtree

Question

我有一个无序的二叉树，我必须执行一个删除根 x 的子树的方法。如果元素 x 在二叉树中多次出现，则该方法仅删除根 x 的一个子树(它找到的第一个)。如果执行了删除，则返回 true。如果元素 x 不存在于二叉树中，则返回 false。所以方法是:

    public class BinaryTree 
{
    protected class Node 
    {
        Integer element;
        Node left;
        Node right;

        Node(int element) 
        {
            this.element = element;
            left = right = null;
        }

        Node(int element, Node left, Node right) 
        {
            this.element = element;
            this.left = left;
            this.right = right;
        }

    protected Node root;

    public BinaryTree() 
    {
        root = null;
    }

    private class BoolNode 
    {
        boolean ft;
        Node nodo;

        BoolNode(boolean ft, Node nodo) 
        {
            this.ft = ft;
            this.nodo = nodo;
        }
    }

    public boolean removeSubtree(int x) 
    {
        BoolNode ris = removeSubtree(x, root);
        //root = ...;
        return ris.ft;
    }

    private BoolNode removeSubtree(int x, Node node) 
    {
        return null;
    }
}

我不知道如何开始，有人知道吗？甚至伪代码..谢谢!

Answer 1

应该是这样的....

• 找到包含值X的节点N
• 如果N是一片叶子，去掉叶子

• 如果N是 parent ，

   removeNodes(N.left);
   removeNodes(N.right);
   remove(N);
  

• 重复直到碰到一片叶子

   private void removeNodes(Node base);  //prepare for this when the teacher asks you why it's private
   // - because you do not want to expose this functionality outside of the class;
   // the only 'interface' exposed is the wrapper call removeSubtree(...) as the user shouldn't worry about the internal functionality.
  

removeSubtree() 是递归 removeNodes() 的包装器；

编辑:好吧，澄清你的谜团。假设我们有这棵树

             1 --- this is root
            / \
           3   7
          / \ / \
     (a) 5  4 3  2  //these branches don't matter right now
        / \
       5   6
      / \  / \
     5  4 3   2

现在，假设您调用 removeSubtree(5, root);

它将遍历树直到它到达节点 (a) - 左边的前 5 个。按照您当前代码的编写方式，您将这样做:它将找到值为 X (5) 的节点；然后它会为他所有的左右子子寻找值 5。

让我们专注于此

             1 --- this is root
            / \
           3   7
            \ / \
            4 3  2  

这是调用 removeSubtree(5, root) 后应该得到的；换句话说，在找到第一个值为 5 的节点并删除其子节点后，查看应该删除的子树

         5  -- we should delete all of these starting from here
        / \
       5   6
      / \  / \
     5  4 3   2

但是您的代码随后会在该子树中查找要删除的值 5。这就是为什么您需要一个通用的 deleteSubtree() 例程，该例程将遍历树并删除它找到的所有内容。您的 removeSubtree(int, node) 例程必须依赖它或通过实现该机制本身来“内联”它。

现在你的代码只会删除这个

             1 --- this is root
            / \
           3   7
          / \ / \
     (a) 5  4 3  2  //these branches don't matter right now
        / \
  (b)  5   6
      / \  / \
(c)  5  4 3   2

换句话说，它将登陆节点 A(前 5 个)，而不是删除节点 (a) 以下的所有内容，它将搜索 A 下面的另一个值 5，找到 (b) 并尝试删除它的子树，仅匹配节点(c)。

最终结果将是这样的——您的代码将只删除三个五并留给您

             1 --- this is root
            / \
           3   7
          / \ / \
         x  4 3  2  
        / \
       x   6
      / \  / \
     x  4 3   2

你现在明白为什么你不能递归地使用同一个函数了吗？ :) 至少不是您现在想要的方式。但是，你可以试试这个 -

 removeSubtree(node.left.value, node);
 removeSubtree(node.right.value, node);
 removeNode(node);

这将有效地找到正确的子树 - 节点 (a)，然后调用自身来匹配它的子节点 - 节点 5 和 6(在节点 (b) 的深度)并因此删除它们。在任何情况下，您都不能像以前那样在这些调用中重复使用值 X

 removeSubtree(x, node.left);
 removeSubtree(x, node.right);
 removeNode(node);

我希望这能澄清一些事情 :) 嘿也许我应该教这个 :D