2

我有一个无序的二叉树，我必须做一个删除根 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;
    }
}

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

4

1 回答 1

4

应该去这样的事情......

  • 找到包含值 X 的节点 N
  • 如果 N 是叶子，则删除叶子

  • 如果 N 是父母，

     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

于 2012-10-31T18:03:26.703 回答