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 回答