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.