Проблема рекурсии двоичного дерева поиска

Question

Я создал двоичное дерево, в котором расположены числа. Числа, которые меньше узла go слева и большего go справа.

У меня есть объект дерева с root. Позже я установил первый узел как root. узел - это еще один объект, созданный из конструктора узла, имеющего значение, левое и правое в качестве аргументов.

function Node(val){
    this.value = val;
    this.left = null;
    this.right = null;
}

Позже я установил левую и правую ветви как узлы на основе значения val.

Node.prototype.branch= function(n){ //n is a New node            
    if(this.value > n.value){
        this.left = n;
    }else if (this.value < n.value){
        this.right = n;
    }

}

Я пытался пройти по дереву, используя рекурсивную функцию. Я посещаю каждый узел и распечатываю наименьшее значение.

Node.prototype.visit = function(){
    if(this.left != null){
        this.left.visit();
    }
    console.log(this.value)
    if(this.right != null){
        this.right.visit();
    }

}

Эта функция выше работает отлично и печатает все числа в возрастающем порядке .... но я не понимаю, как он переходит к наименьшему узлу, печатает значение и возвращается к предыдущему узлу ... поэтому, если кто-то может дать мне объяснение, это будет очень полезно. Спасибо

Answer 1

ОБНОВЛЕНИЕ : я добавил одно изображение для ясного объяснения.

Насколько я понял ваш вопрос, вы застряли где-то между стеком рекурсии, который поддерживается каждый раз, когда вы вызывать ту же функцию внутри себя. Таким образом, каждая функция складывается сама по себе, пока не встретит оператор return, и в конечном итоге каждая функция начнет всплывать и очищать стек вызовов / стек рекурсии.

Позвольте мне попытаться объяснить, что происходит в вашем случае.

В вашей функции посещения вы продолжаете посещать левые узлы, пока не найдете узел, у которого нет левого потомка. До этого вы добавляли каждый левый узел, который вы посетили, в свой стек вызовов, который в конечном итоге вернется, когда ваша функция посещения вернется.

Теперь, когда вы находитесь на узле, у которого нет левого дочернего элемента, вы регистрируете его data, который является самым маленьким узлом в дереве. Надеюсь, это ясно до сих пор.

После этого ...

Вы снова начинаете вводить sh в стек вызовов для любого правого дочернего элемента узла, из которого вы только что вышли из системы .

Это снова добавляет правого дочернего элемента в стек вызовов, а затем выполняет для него функцию посещения, которая затем выводит из системы ваш второй самый маленький узел.

Проблема, которую я вижу здесь, заключается в вы не используете оператор return в конце функции посещения. Следовательно, функция сама выйдет после того, как попадет в закрывающие фигурные скобки.

Надеюсь, мне удалось немного прояснить ситуацию. Спасибо.

PS: Обратите внимание, на изображении, когда я зарегистрировал «1», я ошибочно назвал это шагом 4. Пожалуйста, назовите его 4.1, и вы не пострадаете от понимания остального. Кроме того, это изображение просто объясняет вашу проблему только там, где вы на самом деле не посещаете нулевого ребенка. Вы просто проверяете, является ли его дочерний элемент нулевым или нет.