高效回溯樹形數據：從葉子節點Value到根節點Label路徑拼接
處理樹形數據時，常需根據末節點value回溯至根節點，并拼接路徑。本文將提供一種高效的算法，無需依賴特定ui組件。
問題描述:
給定一個樹形數據結構，例如：
const treeData = [ { label: "節點1", value: "1", children: [ { label: "節點1-1", value: "1-1" }, { label: "節點1-2", value: "1-2" } ]}, { label: "節點2", value: "2", children: [ { label: "節點2-1", value: "2-1" } ]} ];
目標：根據末節點的value (例如”1-2″)，回溯并拼接從該節點到根節點的所有label，生成路徑字符串，例如”節點1/節點1-2″。
解決方案:
我們采用遞歸搜索的方式，無需依賴任何UI組件。算法的核心在于深度優先遍歷樹形結構，并在找到目標value后，回溯過程中拼接路徑。
function getPath(tree, targetValue) { function traverse(node, path) { path.push(node.label); // 添加當前節點label if (node.value === targetValue) { return path.join('/'); // 找到目標節點，返回路徑字符串 } if (node.children) { for (const child of node.children) { const result = traverse(child, [...path]); // 遞歸遍歷子節點 if (result) return result; // 如果找到目標節點，則返回路徑 } } path.pop(); // 回溯：移除當前節點label，繼續搜索其他分支 return NULL; // 當前分支未找到目標節點 } for (const rootNode of tree) { const result = traverse(rootNode, []); if (result) return result; // 如果找到目標節點，則返回路徑 } return null; // 樹中未找到目標節點 } const path = getPath(treeData, "1-2"); console.log(path); // 輸出: 節點1/節點1-2 path = getPath(treeData, "2-1"); console.log(path); // 輸出: 節點2/節點2-1 path = getPath(treeData, "3-1"); // 測試不存在的節點 console.log(path); // 輸出: null
代碼解釋:
- getPath(tree, targetValue): 主函數，接收樹形數據和目標value。
- traverse(node, path): 遞歸函數，進行深度優先遍歷。
- path.push(node.label): 將當前節點的label添加到路徑數組。
- if (node.value === targetValue): 找到目標節點，拼接路徑并返回。
- if (node.children): 遍歷子節點。
- path.pop(): 回溯，移除當前節點的label。
- 函數返回找到的路徑字符串，或null表示未找到。
此方法高效且通用，適用于各種樹形數據結構，無需依賴特定UI庫，便于在各種場景下復用。 它清晰地展示了遞歸在處理樹形數據結構中的強大能力。
? 版權聲明
文章版權歸作者所有，未經允許請勿轉載。
THE END
