Перемещение по порядку с рекурсией?

Question

Я только начал изучать обходе дерева, и я с трудом понять этот код для упорядоченную обхода дерева:

class tree { 
    String data; 
    tree left; 
    tree right; 
} 

void inorder (tree root) { 
    if (root == null) return; 
    inorder (root.left); 
    out.printf ("%s%n", root.data); 
    inorder (root.right); 
} 

Я не понимаю, что после того, как корень = нуль, то выиграл» t выполнение программы рекурсивно вызывает линию 2 метода in-order? и это не приведет к выполнению заявления печати?

Answer 1

Код перемещается по дереву до тех пор, пока он не попадет в корень, который не установлен - то есть left или right является null. Если это произойдет, текущий исполнитель inorder выйдет (преждевременно, можно сказать), позвонив return.

При использовании return, независимо от того, где в методе, метод завершается, поэтому следующие строки не выполняются.

---

Рассмотрим дерево

Чтобы представить это, вы могли бы создать структуру, подобную

Tree node4 = new Tree("Node 4", null, null); 
Tree node5 = new Tree("Node 5", null, null); 
Tree node2 = new Tree("Node 2", node4, node5); 
Tree node6 = new Tree("Node 6", null, null); 
Tree node7 = new Tree("Node 7", null, null); 
Tree node3 = new Tree("Node 3", node6, node7); 
Tree root = new Tree("Root", node2, node3); 

При вызове inorder на корень, вы получите:

Узел 4
Узел 2
Узел 5
Корень
Узел 6
Узел 3
Узел 7

Обратите внимание, что я обновил Tree, чтобы иметь конструктор (а также в верхнем регистре его, так как классы должны с большой буквы).

public Tree(String data, Tree left, Tree right) { 
    this.data = data; 
    this.left = left; 
    this.right = right; 
} 

Answer 2

I dont understand that, once root != null, then won't program execution keep recursively calling line 2 of the in order method?

Это правильно, но ключ к пониманию того, что происходит, чтобы понять, что вы передаете в левом ребенка в вызове метода. В какой-то момент текущий узел (т. Е. Root) будет пустым, поскольку в предыдущем узле больше нет left детей.

Необходимо обратить внимание на то, какие значения передаются.

Что касается выполнения инструкции печати, код по-прежнему выполняется сверху вниз.

Для примера рассмотрим следующую возможную последовательность событий:

root != null 
call in_order(left) 
    root != null 
    call in_order(left) 
    root == null 
    return 
    print root.data 
    call in_order(right) 
    root == null 
    return 
    # done 
print root.data 
call in_order(right) 
    root == null 
    return 
# done 

Когда метод вызывает себя, это не просто остановить выполнение. Он будет выполнять вызванный метод, как обычно, и как только метод вернется, он будет продолжен с того места, где он был остановлен.