在二叉搜索樹中找到最近的值？[復制]

我有這個演算法結構問題；撰寫一個接收 BST 和目標整數值的函式，并將壁櫥值回傳到包含在 BST 中的目標值。

演算法網站給了我這個作業；

function findClosestValueInBst(tree, target) {
  // Write your code here.
}

// This is the class of the input tree. Do not edit.
class BST {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

我不是在尋求答案，但如何在本地 Visual Studio 代碼中對此進行測驗？我需要在函式的樹/目標引數引數中傳遞什么值，以便我什至測驗事物或 console.log 事物？

我猜他們給了我一個示例輸入但是..我什至如何將它記錄到我的函式中來測驗它？

  {
  "tree": {
    "nodes": [
      {"id": "10", "left": "5", "right": "15", "value": 10},
      {"id": "15", "left": "13", "right": "22", "value": 15},
      {"id": "22", "left": null, "right": null, "value": 22},
      {"id": "13", "left": null, "right": "14", "value": 13},
      {"id": "14", "left": null, "right": null, "value": 14},
      {"id": "5", "left": "2", "right": "5-2", "value": 5},
      {"id": "5-2", "left": null, "right": null, "value": 5},
      {"id": "2", "left": "1", "right": null, "value": 2},
      {"id": "1", "left": null, "right": null, "value": 1}
    ],
    "root": "10"
  },
  "target": 12
}

uj5u.com熱心網友回復：

您需要構建有效的搜索樹。

首先執行操作 Add(root, value)

然后進行操作Find，以查找確切的巧合，并Successor和Predecessor獲得最接近值比目前的一個更大和更小。

然后提供值序列來制作一棵樹（例如：）6,3,9,0,15,5,7,14并測驗上述功能。

為了實作findClosestValueInBst，你可以修改代碼，Find但是當你發現元素不存在（站在最后一片樹葉上）時，呼叫其中一個Successor或Predecessor函式來檢查鄰居并找到接近目標的值。

uj5u.com熱心網友回復：

提示：

想想事情怎么會出錯。典型的錯誤是

• 嚴重的編程錯誤（二進制搜索明顯錯誤，錯別字）；

• 微妙的極限情況（空樹，單個節點的樹，兩個節點；相等的節點；目標等于一個節點，目標在中間；在幾個節點上的二分搜索錯誤......）。

對于每種情況，您如何檢查？

我建議不要只嘗試幾個測驗用例，而是建議使用您知道必須在關鍵位置保持的斷言來檢測代碼。例如，檢查是否仍然在您考慮的子樹中找到解決方案。

還要確保實作一個在所有情況下都回傳正確答案的防彈功能（效率無關緊要）。

由于練習似乎不是關于如何構建 BST，因此可以為這部分任務復制現有代碼。確保來源可靠。（為了雙重安全，您可以驗證構建的樹。）

uj5u.com熱心網友回復：

您可能想要構建自己的 BST（或一些）來測驗您的代碼。您可以通過創建一堆節點并將它們鏈接在一起來手動構建它們，或者撰寫一個插入函式來傳遞值并像這樣構建樹。如果您愿意，您可以使用一組值并對其進行映射以構建節點。只需跟蹤 BST 的根節點即可。

然后使用您創建的 BST 的根和幾個不同的目標值呼叫您的函式。查看您的函式是否回傳您期望的值。嘗試涵蓋所有常見和邊緣情況：

目標正好在樹中：作為根節點、內部節點或葉節點；

目標不在樹中，而是在兩個值之間（請注意您回傳更接近的值）；

目標不在樹中，并且比樹中的所有內容都大或小（請參閱您回傳樹中實際的最大值或最小值）；

處理在空 BST、只有一個節點的 BST、有和沒有重復值的 BST 中的搜索

編輯：添加了一些樣板代碼以從值串列構建 BST，然后是如何將樹傳遞給函式并記錄輸出的示例。還有一個將樹列印到控制臺的功能。它就在它的一邊，您必須想象這些鏈接，但它可能會有所幫助。祝你好運

// This is the class of the input tree. Do not edit.
class BST {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function findClosestValueInBst(tree, target) {
  // Write your code here.
}

// build a BST from an array of values and return the root
function buildTree(values) {
  let root = null
  for (let value of values) root = insert(root, value)
  return root;
}
// insert a value into a BST
function insert(root, value) {
  if (!root) return new BST(value)
  if (value < root.value) 
    root.left = insert(root.left, value)
  else 
    root.right = insert(root.right, value)
  return root
}
// display a binary tree
function display(root, depth = 0) {
  if (!root) return;
  display(root.right, depth 1)
  console.log(`${'\t'.repeat(depth)}${root.value}`)
  display(root.left, depth 1)
}

const T1 = buildTree([
  10,  7,  2, 13, 10,  3,
   5, 12, 16, 23,  1, 20
])
display(T1)

// console.log(findClosestValueInBst(T1, 12)) // should return 12, because 12 is in T1
// console.log(findClosestValueInBst(T1, 14)) // should return 13, as it's the closest to 14

標籤：javascript 算法

上一篇：編程中的斷言代碼及其定義

下一篇：當您調整Hashmap的大小時，如果您正在進行線性探測，您是否會保留已洗掉的專案