当我穿越树时，为什么要超过呼叫堆栈的最大大小

Question

我试图从我的二进制树中获取最小值，但是我遇到了一个超过最大呼叫堆栈大小的错误。我如何正确获取二进制搜索树中项目的最小值？

这是我在JSBIN上的代码：

function Node(val){
    this.value = val;
    this.left = null;
    this.right = null;
}
function BinarySearchTree(){
    this.root = null;
}
BinarySearchTree.prototype.minNode =function() {
    var node = this.root;
    if(!node){
        return 0;
    }
    if(node.left){
        return this.minNode(node.left)
    }
    return node.value
}
BinarySearchTree.prototype.push = function(val){
    var root = this.root;
    if(!root){
        this.root = new Node(val);
        return;
    }
    var currentNode = root;
    var newNode = new Node(val);
    while(currentNode){
        if(val < currentNode.value){
            if(!currentNode.left){
                currentNode.left = newNode;
                break;
            }
            else{
                currentNode = currentNode.left;
            }
        }
        else{
            if(!currentNode.right){
                currentNode.right = newNode;
                break;
            }
            else{
                currentNode = currentNode.right;
            }
        }
    }
}
var bt = new BinarySearchTree();
bt.push(23);
bt.push(1);
bt.push(2);
bt.push(25);
console.log(bt.minNode());

Answer 1

如@andrewli所述。您正在通过编写

再次设置相同的根源

var node = this.root;

改为更改您功能的定义

BinarySearchTree.prototype.minNode =function(nextNode) {
    var node = nextNode || this.root;
    if(!node){
        return 0;
    }
    if(node.left){
        return this.minNode(node.left)
    }
    return node.value
}

Answer 2

问题在于，您在穿越节点时不会推进节点。您只需将node设置为根部元素，因此它永远递归。定义函数应该有效：

BinarySearchTree.prototype.minNode = function(nextNode) {
  var node = nextNode || this.root;
  if(!node) {
    return 0;
  }
  if(node.left) {
    return this.minNode(node.left)
  }
  return node.value
}

这将使该函数接受下一个节点的参数。然后，如果存在，则将node分配给下一个节点，如果是第一个呼叫，则将其分配为root。这不会永远反复出现，因为它会推进并穿越树。