3

以下内容未能返回正确的子节点，即使它实际上是在树的更深处找到子节点。它似乎在找到孩子后放弃了它，继续搜索树的其余部分。

private Node<K, V> getNode(K key, ArrayList<Node<K, V>> children){
    if (children == null) return null;

    if (root.getKey().equals(key)) return root;

    for (Node<K, V> child : children) {
        if (child.getKey().equals(key)) return child;
        getNode(key, child.getChildren());
    }

    return null;
}

我使用以下代码对其进行了测试：

Tree<Integer, String> tree = new Tree<>(1, "1");

tree.addChild(1, new Node<>(2, "2"));
tree.addChild(1, new Node<>(3, "3"));
tree.addChild(1, new Node<>(4, "4"));
tree.addChild(2, new Node<>(5, "5"));

System.out.println(tree.addChild(5, new Node<>(6, "6")));
System.out.println(tree.addChild(5, new Node<>(7, "7")));

但是，控制台会输出false两次，即使它应该是true. 5即使我在树中添加了一个，也找不到带有 键的孩子。

4

3 回答 3

1

写 return getNode(key, child.getChildren())在else声明中。它是使用递归的方式。

      ....
      else
      {
       return getNode(key, child.getChildren());
      }
于 2013-12-16T21:21:56.220 回答
1

经过重大的重新格式化工作，我已将您的代码重构为更清晰的形式。虽然有很大不同，但以下内容在逻辑上与您的代码相同：

private Node<K, V> getNode(K key, ArrayList<Node<K, V>> children){
    if (children == null) return null;

    if (root.getKey().equals(key)) return root;

    for (Node<K,V> child : children) {
        if (child.getKey().equals(key)) return child;
        getNode(key, child.getChildren());
    }

    return null;
}

现在，我们可以分解代码并修复它。

第一个问题是在方法前面没有 javadoc 注释，用@paramand记录其参数和返回值@return。那是你需要解决的问题。

其次，这个方法应该被实现为类的类方法Node，并且应该是public. 那是：

class Node<K,V> {

// ... whatever else this class has in it ... 

    public K getKey() { /* ... stuff ... */ }

    ArrayList<Node<K,V>> children = new ArrayList<>();

    public Node<K, V> getNode(K key){
        if (children == null) return null;

        if (key.equals(this.getKey())) return this;

        for (Node<K,V> child : children) {
            if (child.getKey().equals(key)) return child;
            child.getNode(key);
        }

        return null;
    }
}

此外，由于我们现在保证children总是被初始化，并且完全在我们的控制之下，我们可以摆脱虚假null检查。

public Node<K, V> getNode(K key){    
    if (key.equals(this.getKey())) return this;

    for (Node<K,V> child : children) {
        if (child.getKey().equals(key)) return child;
        child.getNode(key);
    }

    return null;
}

现在，您正在冗余地检查孩子。由于getNode()已经检查是否this是正确的节点，因此没有理由单独检查当前节点的每个子节点：

public Node<K, V> getNode(K key){    
    if (key.equals(this.getKey())) return this;

    for (Node<K,V> child : children)
        child.getNode(key);

    return null;
}

现在我们已经摆脱了这么多代码，问题实际上是相当明显的：upper 方法实际上从未对通过搜索子节点出现的节点做任何事情。一个简单的改变就足以解决这个问题：

public Node<K, V> getNode(K key){    
    if (key.equals(this.getKey())) return this;

    for (Node<K,V> child : children){
        Node<K,V> result = child.getNode(key);
        if(result != null) return result;
    }

    return null;
}

请注意，我们不应该检查孩子是否是null. 这应该通过我们为添加新值而公开的方法来处理，并且我们永远不应该将外部节点添加到我们的树中：

public boolean put(K key, V value){
    children.add(new Node<>(key, value));
}

还有一件事：根本不需要单独的Tree班级！你不应该有一个，它的所有功能都应该完全存在于节点类中。理想情况下，根节点是树。

于 2013-12-16T22:44:46.203 回答
1

问题是当你在子树中寻找一个孩子时，你忽略了返回值：

if (child.getKey().equals(key))
{
    // This is fine
    return child;
}
else
{
    // This is bad: you ignore the return value.
    getNode(key, child.getChildren());
}

要修复，捕获返回值，如果不是则返回null，如下所示：

if (child.getKey().equals(key))
{
    return child;
}
else
{
    Node<K, V> res = getNode(key, child.getChildren());
    if (res != null) {
        return res;
    }
}

另外，你的代码会错过当值存储在根，并且根没有孩子的情况，因为没有孩子的节点root.getKey().equals(key)上没有做。

于 2013-12-16T21:20:46.350 回答