遞歸二進制搜索樹時無法正確返回我的值

Question

我已測試過，看看我的樹是否正確插入，並且正在使用僞古典實例來完成此工作。我的問題是，調試器會告訴我，真理被設置爲true，然後當我從函數結尾返回真值時，我會得到錯誤信息。我嘗試了所有我能想到的，但我無法弄清楚爲什麼會發生這種情況。這是我的代碼，用於搜索二叉搜索樹。

var valuetest; 
 
    var truth = false; 
 
    if (this.value === value) { 
 
    var truth = true; 
 
    return truth; 
 
    } else if (value > this.value) { 
 
    valuetest = this.right.value; 
 
    if (valuetest === value) { 
 
     truth = true; 
 
     return truth; 
 
    } else { 
 
     this.right.contains(value); 
 
    } 
 
    } else { 
 
    valuetest = this.left.value; 
 
    if (valuetest === value) { 
 
     truth = true; 
 
     return truth; 
 
    } else { 
 
     this.left.contains(value); 
 
    } 
 
    } 
 
    return truth; 
 
    //returns false even if truth is set to true for some reason.

Answer 1

更新線路用的回報。試試這個片段。

var valuetest; 
 
    var truth = false; 
 
    if (this.value === value) { 
 
    var truth = true; 
 
    return truth; 
 
    } else if (value > this.value) { 
 
    valuetest = this.right.value; 
 
    if (valuetest === value) { 
 
     truth = true; 
 
     return truth; 
 
    } else { 
 
     return this.right.contains(value); 
 
    } 
 
    } else { 
 
    valuetest = this.left.value; 
 
    if (valuetest === value) { 
 
     truth = true; 
 
     return truth; 
 
    } else { 
 
     return this.left.contains(value); 
 
    } 
 
    } 
 
    return truth; 
 
    //returns false even if truth is set to true for some reason.

Answer 2

你忘了return遞歸調用。所以你看到thruth變爲真，但後來一級退出遞歸，的真值變量有一個不同的變量，它根本沒有設置。

此外，您已通過重複相等檢查來實施arm's length recursion，這在此處確實不是必需的。您可以將代碼壓縮到：

return value === this.value || 
     value > this.value && this.right && this.right.contains(value) || 
     value < this.value && this.left && this.left.contains(value); 

如果未找到該值，則應停止遞歸。如果您已經以value爲null或undefined的方式構建了樹，則表示樹葉時，上述方法將起作用。

或者，您可能會忽略left和/或right屬性，當該方向上沒有更多的子項時。此外，如果樹是這樣構建的，上面的代碼將起作用。

或者還是有點聰明：

const branch = this[value > this.value ? 'right' : 'left']; 
return value === this.value || branch && branch.contains(value);