JS树形数据常用递归方法总结

// 定义一个树形结构的函数
function Tree() {
  const nodes = new Map();
 
  // 添加节点
  this.add = function(parent, id) {
    nodes.set(id, { parent, children: new Set() });
  };
 
  // 移除节点
  this.remove = function(id) {
    nodes.delete(id);
    // 还需要从其父节点的children中移除
  };
 
  // 获取所有子孙节点
  this.getSubtree = function(id) {
    const subtree = new Set([id]);
    const dfs = (nodeId) => {
      nodes.get(nodeId).children.forEach(child => {
        subtree.add(child);
        dfs(child);
      });
    };
    nodes.get(id).children.forEach(dfs);
    return subtree;
  };
 
  // 获取所有祖先节点
  this.getAncestors = function(id) {
    const ancestors = new Set();
    let node = nodes.get(id);
    while (node.parent) {
      ancestors.add(node.parent);
      node = nodes.get(node.parent);
    }
    return ancestors;
  };
 
  // 检查是否为叶子节点
  this.isLeaf = function(id) {
    return nodes.get(id).children.size === 0;
  };
 
  // 检查是否为根节点
  this.isRoot = function(id) {
    return !nodes.get(id).parent;
  };
 
  // 获取树的深度
  this.getDepth = function() {
    let depth = 0;
    // 需要遍历所有节点并更新depth
    return depth;
  };
}
 
// 使用示例
const tree = new Tree();
tree.add(null, 'A');
tree.add('A', 'B');
tree.add('A', 'C');
tree.add('B', 'D');
tree.add('B', 'E');
tree.add('C', 'F');
 
console.log(tree.getSubtree('A')); // 输出节点A的所有子孙节点
console.log(tree.getAncestors('D')); // 输出节点D的所有祖先节点
console.log(tree.isLeaf('B')); // 输出节点B是否为叶子节点
console.log(tree.isRoot('D')); // 输出节点D是否为根节点
// 注意: 需要实现getDepth方法来获取树的深度

这个代码示例展示了如何实现一个简单的树形数据结构，并提供了几个常用的递归方法，如获取子孙节点、祖先节点，检查叶子和根节点，以及计算树的深度。需要注意的是，示例中的getDepth方法尚未实现，因为它需要遍历所有节点并更新最大深度。