2017-09-26 106 views
1

我有對象樹,並且找不到具體對象ID的所有父母。想象一下,我需要一些新的字段添加到每個家長與ID對象= 5.有人能幫助遞歸循環請通過樹Javascript:查找樹中元素的所有父母

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

+1

你可能會FF創建地圖的id更好 – epascarello

+1

請讓您的片段** **可運行通過移除語法錯誤(''....並且這樣),分配初始反對變量等。 –

+0

我已經將開始帖子編輯爲正確的格式。 – Lemmy

回答

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

+0

是不是創建循環引用? – user93

+0

是的。這是一個關於如何遞歸處理整個樹並將引用留給父代的例子。只要你不嘗試串聯,應該沒有問題。 –

1

遞歸函數並不難。請記住,如果您的參數不符合,您將新的級別傳遞給函數。

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. 
 

 
    } 
 
    } 
 
}

+0

謝謝!這部分是有用的,但是對於4-5深層次,沒有找到主父(沒有parentId)。 – Lemmy

+0

現在看看它,但對於大型結構,其他繪圖解決方案更有效。 – Mouser

1

最簡單的辦法就是擊敗樹結構,所以你可以只是仰望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))

2

數據構造函數

人們需要停止寫入數據是這樣的:

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

+0

咦,這是什麼?我喜歡它。擰結構文字並給出一個名字!我不會稱之爲'type',而是'tag'。但這只是挑剔。 +100。 – ftor

+0

'tag'比'type'更精確。如果有的話,爲了避免人們對類型有誤解 - 甚至更好,我敢肯定它也是*計算機程序結構和解釋*(Sussman,Abelson)中使用的名稱。當我在我的辦公桌旁時,我會更新它^ _^ – naomik

+0

@ftor再次感謝您的評論和所有內容,但我只收到了100分中的10分!談到堆點,我目前有[500](https://stackoverflow.com/questions/42652411/how-to-wire-data-to-a-deep-component-in-react-router-relay)打開^ _ ^ – naomik