JavaScript 二叉樹是一種數據結構,由于它是二叉的,因此它只有兩個分支:左分支和右分支。每個節點含有一個值以及指向左右兒子節點的指針。在二叉樹中,每個節點都可以有兩個兒子節點,其中一個節點是左邊,另一個節點是右邊。
下面是一個簡單的 JavaScript 二叉樹實現示例:
class Node { constructor(value) { this.value = value; this.left = null; this.right = null; } } class BinaryTree { constructor() { this.root = null; } insert(value) { const node = new Node(value); if (!this.root) { this.root = node; return; } let current = this.root; while (current !== null) { if (value< current.value) { if (current.left === null) { current.left = node; break; } current = current.left; } else { if (current.right === null) { current.right = node; break; } current = current.right; } } } }
在上面的代碼中,我們定義了一個 Node 類來表示樹的節點,包含值以及左右節點。BinaryTree 類的 insert 方法可以向樹中插入一個新的節點并排好序。
我們使用 insert 方法來向二叉樹中添加節點。例如,下面創建了一個 BinaryTree 對象并向其插入一些值:
const tree = new BinaryTree(); tree.insert(5); tree.insert(3); tree.insert(8); tree.insert(1); tree.insert(7);
上面的代碼將會往二叉樹中插入以下幾個節點:5, 3, 8, 1, 7。插入的方式是根據每個節點的大小來決定它應該放在左邊還是右邊,如果節點的值比當前節點的值小,則插入到左邊,否則插入到右邊。
我們可以使用遞歸來遍歷整個二叉樹,可以使用前序、中序或后序遍歷。下面是一個實現中序遍歷的示例:
class BinaryTree { constructor() { this.root = null; } insert(value) { // 省略不重要的部分 let current = this.root; while (current !== null) { // 省略不重要的部分 } return node; } inorderTraversal(callback) { function traverse(node) { if (node === null) { return; } traverse(node.left); callback(node.value); traverse(node.right); } traverse(this.root); } } // 創建 BinaryTree 對象并向其插入節點 const tree = new BinaryTree(); tree.insert(5); tree.insert(3); tree.insert(8); tree.insert(1); tree.insert(7); // 使用中序遍歷獲取所有節點的值 const result = []; tree.inorderTraversal((value) =>result.push(value)); console.log(result); // 輸出 [1, 3, 5, 7, 8]
上面的代碼中,我們定義了一個名為 inorderTraversal 的方法,該方法使用遞歸來處理二叉樹。內部的 traverse 函數用于處理節點,如果節點為 null,則終止程序,否則遍歷其左子樹、處理當前節點和遍歷其右子樹。在 inorderTraversal 中調用 callback 函數并將當前節點的值傳遞給它。最后我們使用 console.log 打印節點的值。
在 JavaScript 中實現二叉樹有許多種方式,并根據你的數據集和算法要求進行優化。上述示例代碼僅為演示和示范目的,并非最佳實踐。