Java递归迭代器与我自己的树

Question

我有两段代码，在我看来它们做同样的事情，但事实并非如此。 我正在尝试为我的自定义集树创建一个迭代器。这是代码。

public LinkedList<AnyType> traverse (TheNode<AnyType> node,LinkedList<AnyType> theList){ 
    if (node.left != null)
        return traverse (node.left,theList);        
    theList.push(node.element);
    if (node.right != null)
        return traverse (node.right,theList);       

    return theList;

}

public void traverseNrTwo (TheNode<AnyType> node){ 
    if (node.left != null){
        traverseNrTwo (node.left);
    }
    list.push(node.element);
    if (node.right != null){
        traverseNrTwo (node.right);
    }
}

traverse 仅遍历树的左侧并将其添加到列表中，但 traveseNrTwo 会遍历整个树。所以，我的问题是，为什么他们要做两件不同的事情？

Answer 1

您不应返回递归调用的结果，因为它会导致递归仅访问树的左侧。

public LinkedList<AnyType> traverse (TheNode<AnyType> node,LinkedList<AnyType> theList){ 
    if (node.left != null)
        traverse (node.left,theList); // if you return traverse(node.left,theList) here,
                                      // you end the recursion without adding the current
                                      // node and visiting the right sub-tree 
    theList.push(node.element);
    if (node.right != null)
        traverse (node.right,theList);       

    return theList;   
}

另请注意，由于您正在传递 LinkedList<AnyType>作为方法的参数(即您没有在方法中创建新的 LinkedList 实例)，您不必返回它。您只需将返回类型更改为 void .