一道js遞歸算法題

1.有樹狀結構的一個對象數組
[{id:0},
{id:1,parentId:0},
{id:2},
{id:3,parentId:1},
{id:4,parentId:0},
{id:5,parentId:3}]

2.要求排完順序為
[{id:0},
{id:1,parentId:0},
{id:3,parentId:1},
{id:5,parentId:3}
{id:4,parentId:0},
{id:2}]
解釋一下：就是一個深度優(yōu)先遍歷吧，有父節(jié)點的數據會有parentId這個屬性，如果一個節(jié)點有子節(jié)點（有節(jié)點parentID==它自己的id），則直接插入他的子節(jié)點，循環(huán)直到插入節(jié)點沒有子節(jié)點為止。同級的按照之前的先后順序排列。

思路大概有，但是寫了半天都是錯的，求大神給個demo學習一下

回答

編輯回答

涼汐

https://jsfiddle.net/g7askt9w... 只能先寫個這個樣的開銷很大如果數據很大

let datas =[{id:0},{id:2},
{id:1,parentId:0},
{id:6,parentId:2},
{id:7,parentId:6},
{id:3,parentId:1},
{id:4,parentId:0},
{id:5,parentId:3}]
let arr=[]
function treedata(data,a){
   data.forEach((r,index)=>{
      if(r.parentId==a.id){
        arr.push(r)
        /* datas.splice(index,1) */
        treedata(datas,r)
      }
       
   })
}
datas.forEach((r,index)=>{
   if(r.parentId || r.parentId===0){
   }else{
      arr.push(r)
      /* datas.splice(index,1) */
      treedata(datas,r) 
   }
})
console.log(arr)

2017年11月29日 15:14

編輯回答

鹿惑

var array =[{id:0},
{id:1,parentId:0},
{id:2},
{id:3,parentId:1},
{id:4,parentId:0},
{id:5,parentId:3}];

//構造樹結構
for(var i = 0;i < array.length;i++){
      var cur = array[i];
        for(var j = i+1;j < array.length;j++){
            var next = array[j];
            if(cur.id === next.parentId){
                     if(!cur.nextIndexArray){
                                cur.nextIndexArray = [];
                         }
                      cur.nextIndexArray.push(j);
                    next.preIndex = i;
            }else if(cur.parentId === next.id){
                    if(!next.nextIndexArray){
                                next.nextIndexArray = [];
                         }
                      next.nextIndexArray.push(i);
                    cur.preIndex = j;
            }
        }
}
var result = [];
//遞歸遍歷樹結構
function recursiveTree(obj){
     result.push(obj);
      var nextIndexArray = obj.nextIndexArray;
      if(!nextIndexArray){
            return;
        }
      for(var i = 0;i < nextIndexArray.length;i++){
               recursiveTree(array[nextIndexArray[i]]);
        }
}
for (var i = 0;i < array.length;i++){
       if(typeof(array[i].preIndex) == "undefined"){
                recursiveTree(array[i]);
         }
}
console.log(result);

2017年9月23日 02:53