多叉樹結構的數據，parent表示法轉成children表示法

最近碰到的問題，有個數組，數組元素是對象，該對象的結構就如樹的parent表示法的節點一樣。形象點講就是該數組存放了樹的所有“葉子節點”，並且葉子節點記憶體有父節點，一直到根節點為止，就如存了一條從葉子節點到根節點路徑。

現在有要求是將這個數組轉成一個children表示法的對象，即從根節點開始，每個節點存有其子節點數組。轉化效果如下（節點必須有個唯一標識符，以下id就是，並且轉化前後其他屬性保持不變，這裡為了顯示簡潔沒有加入其他屬性。）：

核心思想是使用遞歸，新建唯一的根節點開始，不斷生長出子節點。並再插入子節點時判斷子節點是否存在，存在的話不插入，反之插入。註意所有將子節點插入到父節點children數組的操作，都必須保證被插入父節點已經是“新建的唯一根節點”下的，這樣才能實現不斷生長的效果。以下通過遞歸返回父節點的方式確保，返回前是一次插入操作，這時已經判斷出“插入新節點”和“未插入新節點”，根據這兩種情況，遞歸返回值就可以判斷，如果插入新節點則返回該新節點作為父節點，反之返回已存在於“唯一根節點上的”的“該節點”作為父節點。

 1 var treeConverter = {
 2         result: null, //轉化後的結果，是根節點，所有節點都是從根節點長出來的
 3         attributeName: 'id', //節點唯一標識符
 4         needFind: true, //是否查詢節點在result中已經存在，為了優化效率
 5         transform: function (node) { //轉化遞歸函數，參數：一個待插入節點
 6             if (node.parent != null) { //該節點有父節點
 7                 var newNode = this.transform(node.parent); //遞歸進入，返回值為一個節點，用作父節點，該父節點必然存在於result中，這點由下麵的演算法可以控制
 8                 if (this.needFind) {
 9                     for (var i = 0; i < newNode.children.length; i++) { //查找要插入的node子節點是否在newNode這個父節點中存在
10                         if (newNode.children[i][this.attributeName] === node[this.attributeName]) {
11                             return newNode.children[i]; //存在的話直接返回newNode父節點內的該子節點,該子節點必然存在於result中，作為返回值它將被用作上級遞歸的newNode，因此newNode必然存在於result中
12                         }
13                     }
14                 }
15                 this.needFind = false; //不存在的話，關閉之後遞歸的迴圈判斷，因為待插入node節點不存在於result中，故而它的子節點一定不存在於result中，不用再迴圈判斷
16                 delete node.parent; //刪除該節點的parent屬性，如果有的話
17                 node.children = []; //因為確定是要新插入的節點，沒有children:[]屬性，故給該節點增加children:[]屬性
18                 newNode.children.push(node); //將該node節點push進newNode的子節點數組中
19                 return node; //return該新插入節點，作為遞歸返回值給上層，用作newNode父節點，node存在於result中故newNode存在於result中
20             } else if (node.parent == null) { //該葉節點沒有父節點，即為根節點
21                 delete node.parent; //刪除該節點的parent屬性，如果有的話
22                 if (this.result == null) { //根節點不存在
23                     node.children = []; //給該節點增加children:[]屬性
24                     return this.result = node; //該節點賦給result，並return根節點，作為返回值它將被用作上級遞歸的newNode，因此newNode必然存在於result中
25                 } else {
26                     return this.result // 直接return根節點，作為返回值它將被用作上級遞歸的newNode，因此newNode必然存在於result中
27                 }
28             }
29         },
30         getSingle: function (node, attributeName) { //傳入單個葉子節點，attributeName作為節點唯一標識符屬性，返回單個轉化結果
31             this.result = null; //重置根節點
32             this.needFind = true; //重置開啟節點是否已存在判斷
33             this.attributeName = attributeName == null ? 'id' : attributeName; //唯一標識符預設為“id”
34             this.transform(JSON.parse(JSON.stringify(node))); //複製出一個新的節點對象作為參數，保證不改變原有數據
35             return this.result; //返回根節點
36         },
37         getWhole: function (nodes, attributeName) { //傳入整個葉子節點數組，attributeName作為節點唯一標識符屬性，返回整個轉化結果
38             this.result = null; //重置根節點
39             this.attributeName = attributeName == null ? 'id' : attributeName; //唯一標識符預設為“id”
40             nodes = JSON.parse(JSON.stringify(nodes)); //複製出一個新的節點對象作為參數，保證不改變原有數據
41             nodes.forEach(item => { //迴圈調用轉化方法
42                 this.needFind = true; //重置開啟節點是否已存在判斷，保證不插入重覆節點
43                 this.transform(item);
44             })
45             return this.result; //返回根節點
46         }
47     }
48     var result = treeConverter.getWhole(nodes); //調用

模擬數據：

var nodes= [
    {
        id: 2,
        parent: {
            id: 5,
            parent: {
                id: 3,
                parent: null
            }
        }
    },
    {
        id: 1,
        parent: {
            id: 5,
            parent: {
                id: 3,
                parent: null
            }
        }
    },
    {
        id: 4,
        parent: {
            id: 7,
            parent: {
                id: 3,
                parent: null
            }
        }
    },
    {
        id: 14,
        parent: {
            id: 13,
            parent: {
                id: 9,
                parent: {
                    id: 8,
                    parent: {
                        id: 7,
                        parent: {
                            id: 3,
                            parent: null
                        }
                    }
                }
            }
        }
    },
    {
        id: 6,
        parent: {
            id: 7,
            parent: {
                id: 3,
                parent: null
            }
        }
    },
    {
        id: 10,
        parent: {
            id: 8,
            parent: {
                id: 7,
                parent: {
                    id: 3,
                    parent: null
                }
            }
        }
    }
]