二叉搜索树递归问题

Question

我已经创建了一个排列数字的二叉树。小于节点的数字位于左侧，而大于节点的数字位于右侧。

我有一个带有根的树对象。稍后，我将第一个节点设置为根。 node是另一个由Node构造器构造的对象，该构造器具有一个值，左右作为参数。

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

下图可以为您提供思路并阐明递归调用：

您还可以调试以下示例代码以查看其在Java中的工作方式：

class GFG { 
    static void printFun(int test) 
    { 
        if (test < 1) 
            return; 

        else { 
            System.out.printf("%d ", test); 

            // Statement 2 
            printFun(test - 1); 

            System.out.printf("%d ", test); 
            return; 
        } 
    } 

    public static void main(String[] args) 
    { 
        int test = 3; 
        printFun(test); 
    } 
} 

[输出：3 2 1 1 2 3

有关更多信息，请参见Recursion in Java。

Answer 2

据我所知，您被卡在递归堆栈之间的某个位置，每次您在内部调用相同的函数时，该堆栈便会得到维护。这样，每个函数都会堆积在自身上，直到它遇到return语句，最终每个函数才开始弹出并清除调用堆栈/递归堆栈。

让我尝试解释您的情况。

在您的访问功能中，您继续访问左节点，直到找到没有左子节点的节点为止。到那时，您已经将访问的每个左节点添加到了调用堆栈中，当访问函数返回时，该节点最终将返回。

现在，当您在没有左子节点的节点上时，将记录其数据，该数据是树中最小的节点。我希望到目前为止一切都清楚。

此后...

您再次开始为刚刚注销的节点的任何右子节点进入调用堆栈。

这再次将合适的子项添加到调用堆栈中，然后为其执行访问功能，然后注销您的第二个最小的节点。

我在这里看到的问题是，您在访问函数的末尾没有使用return语句。因此，该函数在碰到右花括号后将自身退出。

现在，既然您已经按升序注销了所有节点。

我希望我能够解决一些问题。谢谢。