爲什麼我遍歷樹時超出了調用堆棧的最大尺寸？

我想從我的二叉樹得到最小值，但我得到一個錯誤，最大調用堆棧大小已超出。如何正確獲取二叉搜索樹中項目的最小值？爲什麼我遍歷樹時超出了調用堆棧的最大尺寸？

這裏是我的代碼在：

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());

來源

2017-06-29 user5711656

你不會推進'節點'。您在每次遞歸中將其設置爲根。 – Li357

它不是最新的嗎？什麼是正確的方式.t獲得最小值 – user5711656

您或者需要將它作爲參數傳遞給遞歸方法，或者您需要在實例上保留一個'.currentSearchNode'屬性並使用它來代替'this.root'你可以跟蹤你在哪裏。請注意，這對於任何有意義的數據集都可以很容易地溢出堆棧。 JavaScript在處理直接遞歸方面並不太好。相反，你總是可以蹦蹦跳跳。 –

像@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 
}

來源

2017-06-29 17:09:53 karthick

是的，我也在想同樣的事情。但是，由於您在評論中首先回復了信用信息，所以您需要信用 – karthick

問題的定義是，你不前進的節點，當你穿越它。你只要繼續設置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到下一個節點（如果它存在），或者如果它是第一個呼叫則分配給根。這不會一直遞增，因爲它會前進並穿過樹。

來源

2017-06-29 17:10:53 Li357

爲什麼我遍歷樹時超出了調用堆棧的最大尺寸？

回答

相關問題