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);
            }
        }
      }
 }

Answer 1

数据构造器

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

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

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

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

这使您可以将您的想法与细节分开，例如{}，[]甚至x => ...是否用于包含您的数据。我会更进一步，创建一个具有保证tag字段的统一接口- 以便以后可以将其与其他通用数据区分开来

stack-snippets 在下面这个程序中处理输出是完美的。它并不重要的数据是什么时，看起来像打印出来-重要的是很容易为我们人类阅读我们/写程序，并很容易为我们的程序读取/写入

当/如果您需要特定格式/形状的它，然后将其强制为该形状；在那之前，请保持良好的工作状态

// "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: [] } ] } ] }

让我们开始寻找

我们可以search用一个简单的loop辅助函数来编写——但请注意你没有看到的东西；几乎没有逻辑（使用单个三元表达式）；没有像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 })

// 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 !.. }

所以search返回一个路径数组，其中每个路径都是一个节点数组——为什么会这样？如果 ID 为 的孩子X出现在树中的多个位置，则将返回该孩子的所有路径

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 ]

你不小心写了列表monad

列表 monad 编码了模糊计算的思想——即可以返回一个或多个结果的计算思想。让我们对我们的程序做一个小的改变——这是有利的，因为它List是通用的，现在可以在我们程序中需要这种计算的其他地方使用

如果你喜欢这个解决方案，你可能会喜欢阅读我关于 list monad 的其他答案

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 ] ]

Answer 2

最简单的解决方案是压平树结构，这样你就可以查找 ids 并执行一个简单的 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))

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);