javascript數據結構之多叉樹怎么實現

# JavaScript數據結構之多叉樹怎么實現

## 1. 多叉樹基礎概念

### 1.1 什么是多叉樹

多叉樹（N-ary Tree）是樹形數據結構的一種擴展形式，與二叉樹不同，多叉樹的每個節點可以有任意數量的子節點（通常稱為子節點列表）。這種數據結構能夠更自然地表示許多現實場景，比如：

- 文件系統的目錄結構
- 公司組織架構圖
- 游戲中的技能樹
- XML/HTML文檔對象模型(DOM)

### 1.2 多叉樹與二叉樹的區別

| 特性        | 多叉樹                  | 二叉樹               |
|-------------|-------------------------|----------------------|
| 子節點數量  | 0到N個                  | 最多2個（左/右）     |
| 存儲結構    | 通常使用數組/鏈表存儲子節點 | 明確分為左右節點     |
| 應用場景    | 層級關系復雜的數據       | 搜索/排序等算法      |
| 遍歷復雜度  | 相對較高                | 相對較低             |

### 1.3 多叉樹的基本術語

- **節點(Node)**：樹的基本構成單位
- **根節點(Root)**：沒有父節點的頂層節點
- **葉子節點(Leaf)**：沒有子節點的末端節點
- **度(Degree)**：節點直接子節點的數量
- **深度(Depth)**：從根到該節點的邊數
- **高度(Height)**：從節點到最深葉子節點的邊數

## 2. JavaScript實現多叉樹

### 2.1 基本節點結構

```javascript
class TreeNode {
  constructor(value) {
    this.value = value;       // 節點存儲的值
    this.children = [];       // 子節點數組
    this.parent = null;       // 父節點引用（可選）
  }
  
  // 添加子節點
  addChild(childNode) {
    childNode.parent = this;  // 設置父節點引用
    this.children.push(childNode);
    return this;              // 支持鏈式調用
  }
  
  // 移除子節點
  removeChild(childNode) {
    this.children = this.children.filter(
      child => child !== childNode
    );
    return this;
  }
}

2.2 完整多叉樹類實現

class NaryTree {
  constructor(rootValue) {
    this.root = new TreeNode(rootValue);
    this.size = 1;  // 節點計數器
  }
  
  // 查找節點（廣度優先）
  findBFS(value) {
    const queue = [this.root];
    
    while(queue.length) {
      const currentNode = queue.shift();
      if(currentNode.value === value) {
        return currentNode;
      }
      queue.push(...currentNode.children);
    }
    
    return null;
  }
  
  // 添加節點到指定父節點
  addNode(value, parentValue) {
    const parentNode = this.findBFS(parentValue);
    if(!parentNode) {
      throw new Error('Parent node not found');
    }
    
    const newNode = new TreeNode(value);
    parentNode.addChild(newNode);
    this.size++;
    return newNode;
  }
  
  // 獲取樹的高度
  getHeight(node = this.root) {
    if(!node.children.length) return 0;
    
    let maxHeight = 0;
    for(const child of node.children) {
      maxHeight = Math.max(maxHeight, this.getHeight(child));
    }
    
    return maxHeight + 1;
  }
}

3. 多叉樹的遍歷算法

3.1 深度優先遍歷(DFS)

// 遞歸實現
function traverseDFS(node, callback) {
  callback(node);
  node.children.forEach(child => {
    traverseDFS(child, callback);
  });
}

// 迭代實現（使用棧）
function traverseDFSIterative(root, callback) {
  const stack = [root];
  
  while(stack.length) {
    const node = stack.pop();
    callback(node);
    // 注意子節點要反向壓棧以保證順序
    for(let i = node.children.length - 1; i >= 0; i--) {
      stack.push(node.children[i]);
    }
  }
}

3.2 廣度優先遍歷(BFS)

function traverseBFS(root, callback) {
  const queue = [root];
  
  while(queue.length) {
    const node = queue.shift();
    callback(node);
    queue.push(...node.children);
  }
}

3.3 前序/后序遍歷

// 前序遍歷（父節點在子節點之前處理）
function preOrder(node, callback) {
  callback(node);
  node.children.forEach(child => {
    preOrder(child, callback);
  });
}

// 后序遍歷（父節點在子節點之后處理）
function postOrder(node, callback) {
  node.children.forEach(child => {
    postOrder(child, callback);
  });
  callback(node);
}

4. 多叉樹的高級操作

4.1 查找路徑

function findPath(targetValue) {
  const path = [];
  
  function search(node) {
    path.push(node.value);
    
    if(node.value === targetValue) {
      return true;
    }
    
    for(const child of node.children) {
      if(search(child)) {
        return true;
      }
    }
    
    path.pop();
    return false;
  }
  
  search(this.root);
  return path;
}

4.2 序列化與反序列化

// 序列化為JSON字符串
function serialize() {
  function serializeNode(node) {
    return {
      value: node.value,
      children: node.children.map(serializeNode)
    };
  }
  return JSON.stringify(serializeNode(this.root));
}

// 從JSON字符串反序列化
function deserialize(jsonStr) {
  const data = JSON.parse(jsonStr);
  
  function buildNode(obj) {
    const node = new TreeNode(obj.value);
    obj.children.forEach(childObj => {
      node.addChild(buildNode(childObj));
    });
    return node;
  }
  
  this.root = buildNode(data);
}

5. 性能優化技巧

5.1 子節點存儲優化

對于子節點數量可能很大的情況：

class OptimizedTreeNode {
  constructor(value) {
    this.value = value;
    this.firstChild = null;  // 第一個子節點
    this.nextSibling = null; // 下一個兄弟節點
  }
  
  // 添加子節點
  addChild(value) {
    const newNode = new OptimizedTreeNode(value);
    
    if(!this.firstChild) {
      this.firstChild = newNode;
    } else {
      let current = this.firstChild;
      while(current.nextSibling) {
        current = current.nextSibling;
      }
      current.nextSibling = newNode;
    }
    
    return newNode;
  }
}

5.2 緩存計算結果

class CachedTree extends NaryTree {
  constructor(rootValue) {
    super(rootValue);
    this._height = 0;
    this._size = 1;
  }
  
  getHeight() {
    if(this._heightDirty) {
      this._height = super.getHeight();
      this._heightDirty = false;
    }
    return this._height;
  }
  
  addNode(value, parentValue) {
    const node = super.addNode(value, parentValue);
    this._heightDirty = true;
    return node;
  }
}

6. 實際應用案例

6.1 文件系統模擬

class FileSystem {
  constructor() {
    this.tree = new NaryTree('/');
  }
  
  mkdir(path) {
    const parts = path.split('/').filter(Boolean);
    let current = this.tree.root;
    
    for(const part of parts) {
      let found = current.children.find(c => c.value === part);
      if(!found) {
        found = current.addChild(new TreeNode(part));
      }
      current = found;
    }
  }
  
  ls(path = '/') {
    const parts = path.split('/').filter(Boolean);
    let current = this.tree.root;
    
    for(const part of parts) {
      current = current.children.find(c => c.value === part);
      if(!current) throw new Error('Path not found');
    }
    
    return current.children.map(c => c.value);
  }
}

6.2 組織架構圖

class OrganizationChart {
  constructor(ceoName) {
    this.tree = new NaryTree(ceoName);
  }
  
  hire(employeeName, managerName) {
    return this.tree.addNode(employeeName, managerName);
  }
  
  getTeam(managerName) {
    const manager = this.tree.findBFS(managerName);
    if(!manager) return [];
    
    return manager.children.map(c => c.value);
  }
  
  getManagementChain(employeeName) {
    let node = this.tree.findBFS(employeeName);
    const chain = [];
    
    while(node && node.parent) {
      chain.unshift(node.parent.value);
      node = node.parent;
    }
    
    return chain;
  }
}

7. 常見問題與解決方案

7.1 循環引用檢測

function hasCycle(root) {
  const visited = new Set();
  
  function detect(node) {
    if(visited.has(node)) return true;
    
    visited.add(node);
    for(const child of node.children) {
      if(detect(child)) return true;
    }
    visited.delete(node);
    
    return false;
  }
  
  return detect(root);
}

7.2 內存泄漏預防

class SafeTree {
  constructor(rootValue) {
    this.root = new WeakRef(new TreeNode(rootValue));
  }
  
  // 使用WeakRef避免強引用
  addChild(parentRef, value) {
    const parent = parentRef.deref();
    if(!parent) throw new Error('Parent node garbage collected');
    
    const child = new TreeNode(value);
    parent.addChild(child);
    return new WeakRef(child);
  }
}

8. 測試與調試

8.1 單元測試示例

describe('NaryTree', () => {
  let tree;
  
  beforeEach(() => {
    tree = new NaryTree('root');
    tree.addNode('child1', 'root');
    tree.addNode('child2', 'root');
    tree.addNode('grandchild1', 'child1');
  });
  
  test('should find nodes', () => {
    expect(tree.findBFS('child1')).not.toBeNull();
    expect(tree.findBFS('notexist')).toBeNull();
  });
  
  test('should calculate height', () => {
    expect(tree.getHeight()).toBe(2);
  });
  
  test('should traverse correctly', () => {
    const values = [];
    tree.traverseBFS(tree.root, node => values.push(node.value));
    expect(values).toEqual(['root','child1','child2','grandchild1']);
  });
});

8.2 性能測試建議

• 使用console.time()測量大規模數據操作
• 測試不同實現方式的遍歷速度
• 內存分析使用Chrome DevTools的Memory面板

9. 擴展與變體

9.1 Trie樹（前綴樹）

class TrieNode {
  constructor() {
    this.children = new Map(); // 字符到子節點的映射
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  
  insert(word) {
    let current = this.root;
    
    for(const char of word) {
      if(!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char);
    }
    
    current.isEndOfWord = true;
  }
}

9.2 B樹與B+樹

class BTreeNode {
  constructor(order) {
    this.order = order;       // 階數
    this.keys = [];           // 鍵數組
    this.children = [];       // 子節點數組
    this.isLeaf = false;      // 是否為葉子節點
  }
  
  // 插入鍵的輔助方法
  insertKey(key) {
    let i = this.keys.length - 1;
    while(i >= 0 && key < this.keys[i]) {
      this.keys[i+1] = this.keys[i];
      i--;
    }
    this.keys[i+1] = key;
  }
}

10. 總結與最佳實踐

1. 選擇適當的結構：

   • 子節點數量少 → 使用數組存儲
   • 子節點數量多 → 考慮鏈表或Map結構

2. 遍歷選擇原則：

   • 需要快速訪問最近節點 → BFS
   • 需要深入處理分支 → DFS

3. 內存管理：

   • 大型樹結構考慮使用WeakRef
   • 及時清理不再需要的節點引用

4. 性能關鍵點：

   • 高頻查找操作可添加緩存
   • 頻繁修改時注意平衡性問題

5. 擴展建議：

   • 添加節點ID方便快速查找
   • 實現可視化方法便于調試

多叉樹作為基礎數據結構的擴展形式，在JavaScript中有著廣泛的應用場景。通過合理的實現和優化，可以構建出高效、穩定的樹形結構解決方案。 “`