Как работает поиск в глубину (рекурсивный), когда он достигает конечного узла?

Question

В настоящее время изучаю DFS и просто задаю несколько вопросов о механике его работы.

Перепишите ссылку ниже из-за большой длины кода:

https://repl.it/@Stylebender / DFS-Recursive

1. Является ли базовый случай функции traverseInOrder просто «списком возврата»?

2. Как вы можете видеть из строки 45 и когда код запускается (консоль регистрирует маршрут, по которому пересекаются узлы), я понимаю, что JS рекурсивно понижается с 9 => 4 => 1, так как все еще есть левый узел.

Мой вопрос: почему и как он переходит от Узла 1 к Узлу 6? Другими словами, как функция traverseinOrder может получить узел 6 в качестве аргумента после 1?

Answer 1

Я копирую строки с 39 по 55, чтобы сделать ответ понятным:

DFTInOrder(){
   return traverseInOrder(this.root, []);
 } 
}

//Note, base case occurs where the node within the function no longer has any children.
function traverseInOrder(node, list){
 console.log(node.value);
 if(node.left) {
   traverseInOrder(node.left, list);
 }
 list.push(node.value);
 if(node.right) {
   traverseInOrder(node.right, list);
 }
 return list;
}

1. Нет, traverseInOrder обновляет параметр list и затем возвращает его. Как вы видите в строке 39, первоначальный список пуст. Затем, для каждого вызова traverseInOrder, node.value добавляется в список после прохождения узлов левой ветви и до прохождения узлов правой ветви. Базовый случай (когда левые и правые поля пусты):

добавить node.value к текущему list и затем вернуть это list.

Здесь есть подводный камень, поскольку вы пересекаете узлы, используя в порядке , но регистрируете их, используя предварительный порядок . Посмотрите, что происходит, когда вы вызываете traverseInOrder с аргументами: Node(4) и list=[]:

    function traverseInOrder(node, list){
      console.log(node.value); // log 4
      if(node.left) { // 1
        traverseInOrder(node.left, list); 
        // log 1
        // add 1 to the list (since 1.left and 1.right are null)
      }
      list.push(node.value); // add 4 to the list
      if(node.right) { // 6
        traverseInOrder(node.right, list); 
        // log 6
        // add 6 to the list (since 6.left and 6.right are null)
      }
      return list;
    }

Отсюда и порядок обхода: 1, 4, 6. Но вы регистрируете узлы 4, 1, 6.