Обход двоичного дерева - рекурсия - PullRequest
Новая
       30

Обход двоичного дерева - рекурсия

0 голосов
/ 15 февраля 2019

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

   void inOrderTraversal(BinNode root)
    {  if (root != null) {
        System.out.println("left: "+root.value);
        inOrderTraversal(root.left);
        System.out.println(root.value);
        System.out.print("left is empty: ");
        System.out.println(root.left ==null);
        System.out.print("right is empty: ");
        System.out.println(root.right ==null);
        inOrderTraversal(root.right);

    }
}

Используемые входные данные выглядят так: 

          5
         / \
        4   5
       / \   \
      4   4   5

Вывод кода доступен здесь .

В прилагаемом выходном файле, в четвертой строке вывода, где посещается узел,код находится в конце левого поддерева.Следующий рекурсивный вызов идет справа от поддерева, которое является нулевым.Но в выходных данных в строках 8 и 9 каким-то образом код перемещается обратно на уровень дерева 2, о чем свидетельствуют левый и правый узлы, возвращающие ненулевое значение.

Как рекурсия возвращается обратно вверх по дереву,когда нет ссылки или указателя на предыдущие узлы, например, в связанном списке?

...