Самый простой способ понять код - это попробовать его с помощью отладчика. Chrome имеет превосходный отладчик , который вы можете использовать для пошагового пошагового выполнения кода в реальном времени.
Следующий простой способ - использовать журналы консоли для распечатайте, что происходит, и именно так большинство программистов в определенном возрасте выяснили бы, что происходило до того, как отладчики сделали это проще.
Поскольку я не могу сидеть рядом с вами с открытым отладчиком, давайте сделаем следующее Лучше всего и добавьте несколько журналов консоли, чтобы мы могли видеть, что происходит:
function inOrderHelper(root) {
console.group("Entering inOrderHelper with ", root);
if (root !== null && root !== undefined) {
console.log("Root is not null, so continue");
console.group("Traversing down the left node");
inOrderHelper(root.left);
console.groupEnd();
console.log("The root value is ", root.value);
console.group("Traversing down the right node");
inOrderHelper(root.right);
console.groupEnd();
} else {
console.log("Root is null, so back up");
}
console.log("Exiting inOrderHelper");
console.groupEnd();
}
Итак, давайте попробуем пример BST:
Что может быть сконструировано так, чтобы выглядеть примерно так в JavaScript:
{
left: {
left: {
value: 1,
},
value: 2,
right: {
value: 3,
},
},
value: 4,
right: {
value: 5,
},
}
Вы можете запустить этот код в инструментах разработчика вашего браузера , вставив вышеуказанную функцию (и нажав Enter ), а затем вызвать его так:
inOrderHelper({
left: {
left: {
value: 1,
},
value: 2,
right: {
value: 3,
},
},
value: 4,
right: {
value: 5,
},
})
Результат должен выглядеть примерно так:
Entering inOrderHelper with {left: {…}, value: 4, right: {…} }
Root is not null, so continue
Traversing down the left node
Entering inOrderHelper with {left: {…}, value: 2, right: {…}}
Root is not null, so continue
Traversing down the left node
Entering inOrderHelper with { value: 1 }
Root is not null, so continue
Traversing down the left node
Entering inOrderHelper with undefined
Root is null, so back up
Exiting inOrderHelper
The root value is 1
Traversing down the right node
Entering inOrderHelper with undefined
Root is null, so back up
Exiting inOrderHelper
Exiting inOrderHelper
The root value is 2
Traversing down the right node
Entering inOrderHelper with { value: 3 }
Root is not null, so continue
Traversing down the left node
Entering inOrderHelper with undefined
Root is null, so back up
Exiting inOrderHelper
The root value is 3
Traversing down the right node
Entering inOrderHelper with undefined
Root is null, so back up
Exiting inOrderHelper
Exiting inOrderHelper
Exiting inOrderHelper
The root value is 4
Traversing down the right node
Entering inOrderHelper with { value: 5 }
Root is not null, so continue
Traversing down the left node
Entering inOrderHelper with undefined
Root is null, so back up
Exiting inOrderHelper
The root value is 5
Traversing down the right node
Entering inOrderHelper with undefined
Root is null, so back up
Exiting inOrderHelper
Exiting inOrderHelper
Exiting inOrderHelper
Вы также можете использовать онлайн-инструменты, такие как BinaryTreeVisualizer , чтобы увидеть это с помощью анимации. * 10 30 *
Как программа узнает, что нужно остановить до завершения дерева? Мне кажется, что он должен продолжать go до левого узла бегуна, пока он не станет нулевым, и в этот момент он пропустит console.log
Обратите внимание, что когда функция возвращается влево сторона, когда рекурсивная функция возвращается, управление возвращается к родительской функции, которая продолжается вниз по правой стороне. Когда рекурсивная функция возвращается, она не сразу завершает родительскую функцию. Родительская функция обрабатывает рекурсивную функцию как любую другую функцию. Он вызывает его, а затем, когда возвращается, переходит к следующему:
Как программа узнает, что узел уже напечатан? Мне кажется, что он просто напечатал бы минимальное значение многократно или один раз, прежде чем перейти к максимальному значению, но, очевидно, узлы каким-то образом проверяются.
Это - то, где javascript получает немного запутанный. По сути, функция пытается go вниз по левой и правой стороне, но если значение root представляет собой строку, например "B", то root.left и root.right относятся к несуществующим свойствам. В javascript вместо выдачи ошибки просто возвращается undefined. Поэтому, когда мы возвращаемся к root.left и это значение равно undefined, мы ничего не делаем.
Итак, в нашем примере дерева:
{
left: {
left: {
value: 1,
},
value: 2,
right: {
value: 3,
},
},
value: 4,
right: {
value: 5,
},
}
Наш первый root равен { left: { ... }, value: 4, right: { value: 5 } }
Когда мы go влево, root теперь { left: { value: 1 }, value: 2, right: { value: 3 } }.
Когда мы go ушли снова, root теперь { value: 1 }.
Когда мы go снова ушли, root теперь undefined, поэтому мы ничего не делаем и возвращаемся к предыдущему вызову, где root равен { value: 1 }.
Мы print 1.
Затем мы go направо и root теперь undefined, поэтому мы ничего не делаем и возвращаемся к предыдущему вызову, где root равно { value: 1 }.
Мы закончили с { value: 1 }, поэтому мы возвращаемся к предыдущему вызову, где root равно { left: { value: 1 }, value: 2, right: { value: 3 } }
Мы печатаем 2.
Сейчас мы go вниз вправо, и процесс повторяется, как и для левой, печатая 3.
Затем мы go возвращаемся к предыдущему root, { left: { ... }, value: 4, right: { value: 5 } }
Мы печатаем 4.
Мы go вправо и, как и в предыдущем достаточно, напечатайте 5.
Мы возвращаемся и, поскольку мы достигли исходного вызова функции, мы возвращаем и завершаем программу.
В результате мы напечатали 1, 2, 3, 4, 5, в таком порядке.
Как печатаются все значения? Например, если второе наименьшее значение является правым узлом третьего наименьшего значения, как учитывается второе наименьшее значение?
Я не уверен, что вы спрашиваете, но это Важно отметить, что эта функция не сортирует дерево. Он просто сообщает значения. Так что, если BST не был построен должным образом (например, меньшее значение - это право большего значения), тогда оно будет также печатать эти значения не по порядку.