Javascript:查找树中元素的所有父项 [英] Javascript: Find all parents for element in tree

查看:22
本文介绍了Javascript:查找树中元素的所有父项的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有对象树,但我无法找到具体对象 ID 的所有父对象.想象一下,我需要为 id = 5 的对象的每个父级添加一些新字段.有人可以帮忙通过树进行递归循环

var tree = {编号:1,孩子们: [{编号:3,父 ID:1,孩子们: [{编号:5,父 ID:3,孩子们: []}]}]}控制台日志(搜索树(树,5));功能搜索树(树,nodeId){for (让 i = 0; i 

解决方案

数据构造函数

人们需要停止这样写数据:

const 树 ={ id: 1, parentId: null, children:[ { id: 3, parentId: 1, 孩子:[ { id: 5, parentId: 3, children: [] } ] } ] }

并开始使用数据构造函数

写入数据

//节点"数据构造函数const Node = (id, parentId = null, children = Children()) =>({ id, parentId, children })//儿童"数据构造函数const Children = (...values) =>价值观//写入复合数据常量树 =节点(1,空,子节点(节点 (3, 1,子节点(节点 (5, 3)))))控制台日志(树)//{ id: 1, parentId: null, children: [ { id: 3, parentId: 1, children: [ { id: 5, parentId: 3, children: [] } ] } ] }

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

stack-snippets 在下面的程序中处理输出是完美的.打印出来的数据是什么样子并不重要打印出来 - 重要的是我们人类很容易在我们的中读/写>program,我们的程序很容易/

当/如果您需要特定格式/形状的它,将其强制为该形状然后;在那之前,请保持良好的易用性

const Node = (id, parentId = null, children = Children()) =>({标签:节点,id,parentId,children})const Children = (...values) =>({标签:儿童,价值观})//写入复合数据常量树 =节点(1,空,子节点(节点 (3, 1,子节点(节点 (5, 3)))))控制台日志(树)//{ ... 非常丑陋的输出,但谁在乎!.. }

<小时>

开始搜索

我们可以用一个简单的loop 辅助函数来编写search——但是请注意您没有看到的内容;几乎没有逻辑(使用单个三元表达式);没有像 for/while 这样的命令式结构或像 i++ 这样的手动迭代器递增;不使用像 push/unshift 这样的修改器或像 .forEach 这样的有效函数;没有对 .length 属性的无意义检查或使用 [i] 样式查找的直接索引读取——它只是函数和调用;我们不必担心任何其他噪音

const Node = (id, parentId = null, children = Children()) =>({标签:节点,id,parentId,children})const Children = (...values) =>({标签:儿童,价值观})常量树 =节点(1,空,子节点(节点 (3, 1,子节点(节点 (5, 3)))))const search = (id, tree = null) =>{const loop = (path, node) =>node.id === id?[小路]: node.children.values.reduce ((acc, child) =>acc.concat (loop ([...path, node], child)), [])返回循环([],树)}常量路径 =搜索(5,树)console.log (paths.map (path => path.map (node => node.id)))//[ 1, 3 ]

所以 search 返回一个 array 路径,其中每个路径都是一个 array 节点——为什么会这样?如果 ID 为 X 的孩子出现在树中的多个位置,所有到孩子的路径将被返回

const Node = (id, parentId = null, children = Children()) =>({标签:节点,id,parentId,children})const Children = (...values) =>({标签:儿童,价值观})常量树 =节点(0,空,儿童(节点 (1, 0, 子节点 (Node (4, 1))),节点 (2, 0, Children (Node (4, 2))),节点 (3, 0, Children (Node (4, 3)))))const search = (id, tree = null) =>{const loop = (path, node) =>node.id === id?[小路]: node.children.values.reduce ((acc, child) =>acc.concat (loop ([...path, node], child)), [])返回循环([],树)}常量路径 =搜索(4,树)console.log (paths.map (path => path.map (node => node.id)))//[ [ 0, 1 ],//[ 0, 2 ],//[ 0, 3 ] ]

<小时>

你不小心写了列表单子

list monad 编码了模糊计算的思想——也就是说,可以返回一个或多个结果的计算思想.让我们对我们的程序做一个小改动——这是有利的,因为 List 是通用的,现在可以在我们程序中需要这种计算的其他地方使用

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

const List = (xs = []) =>({标签:列表,价值:xs,链:f =>列表 (xs.reduce ((acc, x) =>acc.concat (f (x) .value), []))})const Node = (id, parentId = null, children = Children()) =>({标签:节点,id,parentId,children})const Children = (...values) =>列表(值)const search = (id, tree = null) =>{const loop = (path, node) =>node.id === id?列表([路径]): node.children.chain (child =>循环 ([...path, node], child))返回循环 ([], tree) .value}常量树 =节点(0,空,儿童(节点 (1, 0, 子节点 (Node (4, 1))),节点 (2, 0, Children (Node (4, 2))),节点 (3, 0, Children (Node (4, 3)))))常量路径 =搜索(4,树)console.log (paths.map (path => path.map (node => node.id)))//[ [ 0, 1 ],//[ 0, 2 ],//[ 0, 3 ] ]

I have the objects tree, and i can't found all parents for concrete object id. Imagine i need to add some new field to each parent for object with id = 5. Can someone help please with recursive loop through tree

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

解决方案

data constructors

People need to stop writing data like this:

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

and start writing data using data constructors

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

This allows you to separate your mind from details like whether {}, or [] or even x => ... is used to contain your data. I would go just one step further and create a uniform interface with a guaranteed tag field – so that it could later be distinguished from other generic datum

It's perfect that stack-snippets butchers the output in this program below. It does not matter what the data looks like when printed outwhat matters is it's easy for us humans to read/write in our program, and it's easy for our program to read/write

When/if you need it in a specific format/shape, coerce it into that shape then; until that point, keep it nice an easy to work with

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


let's get searching

We can write search with a simple loop helper function – but notice what you're not seeing; almost no logic (a single ternary expression is used); no imperative constructs like for/while or manual iterator incrementing like i++; no use of mutators like push/unshift or effectful functions like .forEach; no senseless inspection of .length property or direct index reads using [i]-style lookups – it's just functions and calls; we don't have to worry about any of that other noise

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 ]

So search returns an array of paths, where each path is an array of nodes – why is this the case? In the event a child with an ID of X appears in multiple locations in the tree, all paths to the child will be returned

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


you accidentally wrote the list monad

The list monad encodes the idea of ambiguous computations – that is, the idea of a computation that can return one or more result. Let's make a small change to our program - this is advantageous because List is generic and now can be used other places in our program where this kind of computation is essential

If you like this solution, you will probably enjoy reading my other answers that talk about the list monad

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

这篇关于Javascript:查找树中元素的所有父项的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆