经过重大的重新格式化工作,我已将您的代码重构为更清晰的形式。虽然有很大不同,但以下内容在逻辑上与您的代码相同:
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 注释,用@param
and记录其参数和返回值@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
班级!你不应该有一个,它的所有功能都应该完全存在于节点类中。理想情况下,根节点是树。