Javascript: двоичное дерево поиска в порядке обхода, рекурсивная путаница - PullRequest
Новая
       10

Javascript: двоичное дерево поиска в порядке обхода, рекурсивная путаница

2 голосов
/ 18 апреля 2020

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

BinarySearchTree.prototype.inOrder = function() {
    if (this.root == null) {
      return null;
    } else {
      var result = new Array();
      function traverseInOrder(node) {       
        node.left && traverseInOrder(node.left);
        result.push(node.data);
        node.right && traverseInOrder(node.right);
      }
      traverseInOrder(this.root);
      return result;
    };
}

Я попытался добавить оператор отладчика и выполнить следующие действия: но я теряюсь внутри: 

  function traverseInOrder(node) {       
    node.left && traverseInOrder(node.left); //step 1
    result.push(node.data);  //step 2
    node.right && traverseInOrder(node.right); //step 3
  }

node.left && traverseInOrder(node.left); (Шаг 1) запускается, затем запускается снова, затем запускается снова. Наконец, когда нет node.left, вызывается Шаг 2: result.push(node.data);
Это та часть, где он теряет меня . Теперь он пытается запустить node.right && traverseInOrder(node.right), но нет node.right, но вместо того, чтобы выйти из функции, он возвращается к шагу 2, result.push(node.data);.

Поставлено ли это в очередь из-за нескольких рекурсивных вызовов на шаге 1?

Ответы [ 2 ]

3 голосов
/ 18 апреля 2020

Давайте посмотрим на пример. Пусть это будет дерево ниже, которое будет пройдено in order.

enter image description here

  • Первое traverseInOrder вызывается с this.root, это означает, что параметр из приведенного выше примера A. node.left существует, следовательно, traverseInOrder вызывается с параметром B.
    • В вызове B существует node.left, следовательно, traverseInOrder вызывается с параметром D.
      • В вызове D node.left не существует (node.left - ложь), поэтому result.push(node.data); вызывается с параметром D. На следующем шаге node.right ложно, следует, что traversInOrder с параметром D завершен. Мы возвращаемся к B.
    • Мы вернулись к вызову B, и, поскольку traversInOrder с D только что закончился, result.push(node.data) будет вызван с параметр B. И поскольку следующий node.right является правдивым, то traverseInOrder вызывается с node.right, поэтому с E.
      • При E node.left ложно, result.push вызывается с параметром E. node.right является ложью, звонок с E закончился здесь. Мы возвращаемся к вызову A, потому что когда мы возвращаемся к вызову B, он заканчивается в этой точке.
  • При вызове с параметром A мы только что закончили левый узел, result.push(node.data); вызывается для A, а следующий node.right правдив, поэтому result.push(node.data) вызывается с правым узлом, что означает параметр C.

И то же самое происходит с C, F, G.

2 голосов
/ 18 апреля 2020

tenkmilan уже отлично показал, как представить этот код.

Здесь я go другой путь и пишу более простой inorder обход. Должно быть достаточно ясно, как это можно сопоставить с предоставленным кодом.

Обход inorder достаточно прост. preorder и postorder являются другими наиболее распространенными обходами деревьев, и они работают на произвольных конечных деревьях. Inorder определен только для двоичных деревьев и использует left - и right -детей вашего узла. Порядок обхода состоит в том, чтобы (рекурсивно) пройти по левому потомку, затем посетить сам узел и, наконец, (рекурсивно) пройти по правому потомку.

Мы можем написать такой обход просто: 

const inorder = (tree) =>
  tree 
    ? [
        ... inorder (tree .left),
        tree .data,
        ... inorder (tree .right)
      ]
    : []

У нас есть базовый случай, когда узел, на который мы смотрим, пуст, и мы просто возвращаем пустой массив. В общем случае мы просто объединяем рекурсивный вызов на left .tree со значением нашего текущего узла и рекурсивный вызов на right .tree.

Это все, что нужно для inorder обхода. Вы можете увидеть это в действии в этом фрагменте: 

const inorder = (tree) =>
  tree 
    ? [
        ... inorder (tree .left),
        tree .data,
        ... inorder (tree .right)
      ]
    : []

const tree = {
  data: 'F',
  left: {
    data: 'B',
    left: {data: 'A'},
    right: {
      data: 'D',
      left: {data: 'C'},
      right: {data: 'E'}
    }
  },
  right: {
    data: 'H',
    left: {data: 'G'},
    right: {data: 'I'}
  }
}

console .log (inorder (tree))

Конечно, это для простого дерева, хранящегося в виде простого JS объекта. Но сопоставить ваш пример кода достаточно просто. Я предполагаю, что если вы можете следовать этому, вы можете быстро следовать этому.

...