如何基于对象结构实现树的节点查找与插入？

原函数存在几个关键问题：

• 当当前节点不存在目标父节点时，Object.keys(tree[parentNode])会直接抛出错误，因为tree[parentNode]为undefined，无法调用Object.keys
• 递归遍历的对象错误，应该遍历当前节点的所有子节点（即Object.keys(tree)），而非tree[parentNode]的子节点
• 缺少递归终止条件，找到目标父节点插入后，没有停止递归流程

修复后的函数实现 #

type Tree = Record<string, Tree | {}>;

const findAndInsert = (node: string, tree: Tree, parentNode: string): boolean => {
  // 检查当前节点是否包含目标父节点
  if (tree.hasOwnProperty(parentNode)) {
    // 插入新节点
    tree[parentNode][node] = {};
    return true; // 找到父节点，终止递归
  }

  // 遍历当前节点的所有子节点，递归查找
  for (const key of Object.keys(tree)) {
    const child = tree[key] as Tree;
    // 如果子节点是对象（非空或嵌套结构），递归查找
    if (typeof child === 'object' && child !== null) {
      const found = findAndInsert(node, child, parentNode);
      if (found) return true; // 找到后立即终止遍历
    }
  }

  // 未找到目标父节点
  return false;
};

代码说明 #

1. 类型定义：新增Tree类型，明确树结构的类型约束，避免类型报错
2. 父节点检查：使用hasOwnProperty判断当前节点是否包含目标父节点，避免原型链干扰
3. 递归终止：找到父节点插入后返回true，触发上层递归终止，避免无效遍历
4. 子节点遍历：遍历当前节点的所有子节点，仅对对象类型的子节点进行递归，确保遍历有效性

使用示例 #

const resultTree = {
  grand_parent: {
    parent: {
      child: {},
    },
    sibling: {
      cousin: {},
    },
  },
};

// 插入grand_child到child下
findAndInsert('grand_child', resultTree, 'child');
console.log(resultTree);

// 再插入sibling到child下
findAndInsert('sibling', resultTree, 'child');
console.log(resultTree);

执行后会得到预期的树结构：

{
  grand_parent: {
    parent: {
      child: {
        grand_child: {},
        sibling: {}
      },
    },
    sibling: {
      cousin: {},
    },
  },
}

内容的提问来源于stack exchange，提问作者webber