Javascript: 在树中查找元素的所有父级

Question

我有一个对象树，但我无法找到具体对象id的所有父级。假设我需要为id = 5的对象的每个父级添加一些新字段。请问有人能帮忙通过递归循环遍历树吗？

var tree = {
  id: 1,
  children: [
   {
  id: 3,
  parentId: 1,
  children: [
     {
    id: 5,
    parentId: 3,
    children: []
   }
  ]
 }
  ]
}

console.log(searchTree (tree, 5));

function searchTree (tree, nodeId){
      for (let i = 0; i < tree.length; i++){
        if (tree[i].id == nodeId) {
            // it's parent
            console.log(tree[i].id);
            tree[i].newField = true;
            if (tree[i].parentId != null) {
              searchTree(tree, tree[i].parentId);
            }
        }
      }
 }

- Lemmy

---

你最好创建一个 ID 映射表。 - epascarello

请通过消除语法错误（如...）并将初始对象分配给变量等方式，使您的代码段可运行。 - T.J. Crowder

我已经编辑了起始帖子，使其符合正确的格式。 - Lemmy

你说你需要在“每个ID为5的节点的父级”中添加一个新字段，但是在你的示例中，你正在向“ID为5的节点”添加一个新字段……我不明白。你需要找到“节点5”，然后向其父级添加字段吗？还是向它的子代添加字段，这些子代也是父级？我怎么知道一个节点是父级还是不是（在你的示例中，我看到所有节点都是父级，因为每个节点都有一个child属性）？ - Parziphal

Answer 1

数据构造器

人们需要停止像这样编写数据：

const tree = 
  { id: 1, parentId: null, children:
    [ { id: 3, parentId: 1, children:
      [ { id: 5, parentId: 3, children: [] } ] } ] }

并使用 数据构造函数 开始编写数据

// "Node" data constructor
const Node = (id, parentId = null, children = Children ()) =>
  ({ id, parentId, children })

// "Children" data constructor
const Children = (...values) =>
  values

// write compound data
const tree =
  Node (1, null, 
    Children (Node (3, 1,
      Children (Node (5, 3)))))

console.log (tree)
// { id: 1, parentId: null, children: [ { id: 3, parentId: 1, children: [ { id: 5, parentId: 3, children: [] } ] } ] }

这使您能够将注意力从细节上分离出来，比如是否使用{}、[]甚至是x => ...来包含数据。我会更进一步，创建一个统一的接口，并保证一个tag字段，以便稍后可以将其与其他通用数据区分开来。

很棒的是，stack-snippets在下面的程序中砍掉了输出。当打印出来的数据长什么样子并不重要，重要的是它对我们人类来说易于阅读/编写，在我们的程序中也易于读取/编写。

如果需要特定的格式/形状，则将其强制转换为该形状然后使用；在此之前，保持它的良好和易于操作性。

const Node = (id, parentId = null, children = Children ()) =>
  ({ tag: Node, id, parentId, children })

const Children = (...values) =>
  ({ tag: Children, values })

// write compound data
const tree =
  Node (1, null, 
    Children (Node (3, 1,
      Children (Node (5, 3)))))

console.log (tree)
// { ... really ugly output, but who cares !.. }

---

让我们开始搜索

我们可以使用一个简单的loop辅助函数来编写search - 但请注意您没有看到的内容；几乎没有逻辑（只使用了一个三元表达式）；没有命令式结构，如for/while或手动迭代器增量，如i++；没有使用改变原数组的方法，如push/unshift或具有副作用的函数，如.forEach；没有毫无意义地检查.length属性或直接使用[i]样式的索引读取 - 它只是函数和调用；我们不必担心任何其他噪音。

const Node = (id, parentId = null, children = Children ()) =>
  ({ tag: Node, id, parentId, children })

const Children = (...values) =>
  ({ tag: Children, values })

const tree =
  Node (1, null, 
    Children (Node (3, 1,
      Children (Node (5, 3)))))

const search = (id, tree = null) =>
  {
    const loop = (path, node) =>
      node.id === id
        ? [path]
        : node.children.values.reduce ((acc, child) =>
            acc.concat (loop ([...path, node], child)), [])
    return loop ([], tree)
  }

const paths =
  search (5, tree) 

console.log (paths.map (path => path.map (node => node.id)))
// [ 1, 3 ]

所以search会返回一个路径数组，其中每个路径都是节点数组 - 为什么会这样呢？如果树中出现了多个ID为X的子节点，则所有到达子节点的路径都将被返回。

const Node = (id, parentId = null, children = Children ()) =>
  ({ tag: Node, id, parentId, children })

const Children = (...values) =>
  ({ tag: Children, values })

const tree =
  Node (0, null, Children (
    Node (1, 0, Children (Node (4, 1))),
    Node (2, 0, Children (Node (4, 2))),
    Node (3, 0, Children (Node (4, 3)))))

const search = (id, tree = null) =>
  {
    const loop = (path, node) =>
      node.id === id
        ? [path]
        : node.children.values.reduce ((acc, child) =>
            acc.concat (loop ([...path, node], child)), [])
    return loop ([], tree)
  }
  
const paths =
  search (4, tree) 

console.log (paths.map (path => path.map (node => node.id)))
// [ [ 0, 1 ],
//   [ 0, 2 ],
//   [ 0, 3 ] ]

---

你不小心写了列表单子

列表单子编码了模棱两可的计算的概念--即一种可以返回一个或多个结果的计算的想法。让我们对我们的程序做一个小改变——这是有利的，因为List是通用的，现在可以在我们程序中的其他地方使用它，这种计算是必不可少的。

如果你喜欢这个解决方案，你可能会喜欢阅读我写的其他关于列表单子的答案。

const List = (xs = []) =>
  ({
    tag:
      List,
    value:
      xs,
    chain: f =>
      List (xs.reduce ((acc, x) =>
        acc.concat (f (x) .value), []))
  })

const Node = (id, parentId = null, children = Children ()) =>
  ({ tag: Node, id, parentId, children })

const Children = (...values) =>
  List (values)

const search = (id, tree = null) =>
  {
    const loop = (path, node) =>
      node.id === id
        ? List ([path])
        : node.children.chain (child =>
            loop ([...path, node], child))
    return loop ([], tree) .value
  }
  
const tree =
  Node (0, null, Children (
    Node (1, 0, Children (Node (4, 1))),
    Node (2, 0, Children (Node (4, 2))),
    Node (3, 0, Children (Node (4, 3)))))

const paths =
  search (4, tree) 

console.log (paths.map (path => path.map (node => node.id)))
// [ [ 0, 1 ],
//   [ 0, 2 ],
//   [ 0, 3 ] ]

- Mulan

---

哎呀，这是什么？我喜欢它。别管结构字面量了，给东西起个名字吧！虽然我不会叫它“type”，而是“tag”。但那只是挑剔而已。+100。 - user6445533

这里使用“标签”比“类型”更准确；如果有什么误解，为了避免人们已经对类型存在的误解，使用“标签”更好。我相信在《计算机程序的构造和解释》（Sussman, Abelson）中也是使用这个术语。下次我回到办公桌时会进行更新 ^_^ - Mulan

当一个节点没有子节点时，这个会出错。 - eddy

@eddy 可运行程序中存在没有子节点的节点; Node(4,1), Node(4,2)... - Mulan

我不得不添加另一个检查来查看是否有子元素（在这种情况下，我返回一个空数组）。 - eddy

这是因为您跳过了答案的第一部分——_数据构造器_，可能正在使用手写数组，其中某些节点没有children属性。解决方案是使用数据构造器，而不是添加一个空检查来检查children。 - Mulan

Answer 2

最简单的解决方案是将树形结构扁平化，这样你就可以查找ID并进行简单的while循环。

var tree = {
  id: 1,
  children: [
   {
  id: 3,
  parentId: 1,
  children: [
     {
    id: 5,
    parentId: 3,
    children: []
   }
  ]
 }
  ]
}

// We will flatten it down to an object that just holds the id with the object
var lookup = {}
function mapIt (node) {
  lookup[node.id] = node;
  //recursive on all the children
  node.children && node.children.forEach(mapIt);
}
mapIt(tree)

// This takes a node and loops over the lookup hash to get all of the ancestors
function findAncestors (nodeId) {
   var ancestors = []
   var parentId = lookup[nodeId] && lookup[nodeId].parentId
   while(parentId !== undefined) {
     ancestors.unshift(parentId)
     parentId = lookup[parentId] && lookup[parentId].parentId
   }
   return ancestors;
}

// Let us see if it works
console.log("5: ",  findAncestors(5))

- epascarello

Answer 3

这是一个可行的递归函数示例。

玩一会儿，你就应该明白了。

var tree = {
  id: 1,
  children: [{
    id: 3,
    parentId: 1,
    children: [{
      id: 5,
      parentId: 3,
      children: []
    }]
  }]
}

function mapit(node, parent = null) {
  node.parent = parent;
  if (node.children.length > 0) {
    for (var i = 0; i < node.children.length; i++) {
      var child = node.children[i];
      mapit(child, node);
    }
  }
}
mapit(tree);
console.log(tree);

- Emil S. Jørgensen

---

这不会创建循环引用吗？ - user93

是的，这是一个递归处理整个树并留下对父节点的引用的示例。只要不尝试将其转换为字符串，就不应该出现问题。 - Emil S. Jørgensen

for循环有效地检查节点.children.length（i < node.children.length）。在我看来，不需要另一个if。 - Elnur

Answer 4

递归函数并不难。记住，如果参数没有满足条件，你需要将新的层次传递给函数。

var tree = [{
  id: 1,
  children: [{
    id: 3,
    parentId: 1,
    children: [{
      id: 5,
      parentId: 3,
      children: [{
        id: 6,
        parentId: 5,
        children: [{
          id: 5,
          parentId: 3,
          children: []
        }]
      }]
    }]
  }]
}]; //wrap first obj in an array too.

searchTree(tree, 5);
console.log(tree);

function searchTree(tree, nodeId) {
  for (let i = 0; i < tree.length; i++) {
    if (tree[i].id == nodeId) {
      tree[i]; //id found, now add what you need.
      tree[i].newField = "added";
    }//if child has children of its own, continu digging.
    if (tree[i].children != null && tree[i].children.length > 0) {
      searchTree(tree[i].children, nodeId); //pass the original nodeId and if children are present pass the children array to the function.

    }
  }
}

- Mouser

---

谢谢！它部分起作用，但在4-5层深度中找不到主要的父级（没有parentId）。 - Lemmy

然而，对于大型结构，其他映射解决方案更为有效。 - Mouser