Javascript：查找树中元素的所有父母

Question

我有对象树，并且找不到具体对象ID的所有父母。想象一下，我需要一些新的字段添加到每个家长与ID对象= 5.有人能帮助递归循环请通过树

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

 
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

这里是一个工作递归函数的一个例子。

摆弄了一会儿，你应该是金色的

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

Answer 2

递归函数并不难。请记住，如果您的参数不符合，您将新的级别传递给函数。

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. 
 

 
    } 
 
    } 
 
}

Answer 3

最简单的办法就是击败树结构，所以你可以只是仰望ID和做一个简单的while循环

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

 
// 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 4

数据构造函数

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

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字段 - 以便它可以稍后与其他通用数据区分

堆栈片段在下面的程序中执行输出是完美的。它没有关系什么数据看起来当打印出来像 - 重要的是很容易为我们人类阅读我们的程序 /写，并很容易为我们的程序读/写

当/如果你需要它在一个特定的格式/形状，强制它成为然后;直到这一点，保持好的一个容易

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返回阵列路径，其中每个路径是节点的阵列案子？在与X ID的孩子出现在树多个位置的情况下，所有路径孩子将返回

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

---

你不小心写列表单子

列表monad编码模糊计算的想法 - 也就是说，可以返回一个或多个结果的计算的想法。让我们做一个小的改变我们的计划 - 这是有利的，因为List是通用的，现在可以用来在我们的程序中的其他地方，这种计算是必不可少的

如果你喜欢这个解决方案，你可能会喜欢阅读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 ] ]