javascript如何用遞歸寫(xiě)一個(gè)簡(jiǎn)單的樹(shù)形結(jié)構(gòu)示例

更新時(shí)間：2017年09月06日 08:31:04 作者：Runlin

本篇文章主要介紹了javascript如何用遞歸寫(xiě)一個(gè)簡(jiǎn)單的樹(shù)形結(jié)構(gòu)示例，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧

現(xiàn)在有一個(gè)數(shù)據(jù)，需要你渲染出對(duì)應(yīng)的列表出來(lái)：

var data = [
 {"id":1},
 {"id":2},
 {"id":3},
 {"id":4}, 
];

var str="<ul>";

data.forEach(function(v,i){
  str+="<li><span>"+v.id+"</span></li>"
})

str="</ul>"

$(doucment).append(str);

哼，easy!

語(yǔ)罷，又是一道題飛來(lái)!

哦，還帶了兒子來(lái)當(dāng)幫手。我一個(gè)循環(huán)再一個(gè)循環(huán)，輕松帶走你們

var data2 = [
  {"id":1,children:[{"id":"child11"},{"id":"child12"}]},
  {"id":2},
  {"id":3children:[{"id":"child31"},{"id":"child32"}]},
  {"id":4}, 
];


var str="<ul>";

data2.forEach(function(v,i){
  if(v.children&&v.children.length>0){
    str+="<li><span>"+v.id+"</span>";
    str+="<ul>";
    v.children.forEach(function(value,index){
       str+="<li><span>"+value.id+"</span>";
    })
    str="</ul>";
    str="</li>";

  }else{
    str+="<li><span>"+v.id+"</span></li>"
  } 
})
str="</ul>"

$(doucment).append(str);

還有誰(shuí)？

var json=[
    {
     name:123,id:1
     children:[
      {
       name:453,id:456,children:[{name:789,id:777,children:[{name:"hahahqqq---qq",id:3232,children:[name:'son',id:"13132123211"]}]}]
      },
      {
       name:"Cessihshis" , id:12121
      }
     ]
    },
    {
     name:"啊啊啊11", id:12
    },
   ];

竟然把全家都帶來(lái)了，看我循環(huán)循環(huán)再循環(huán)大法。

嗯，不知道他家?guī)状茫以撗h(huán)幾次？突然間你感覺(jué)遇到對(duì)手了。

正納悶著，突然有人拍了一下你的肩膀，兄弟，我這里有一本遞歸秘籍，我看你骨骼驚奇，是個(gè)練武奇才，10塊錢(qián)賣(mài)你了。

 function render(treeJson){  
  if(!Array.isArray(treeJson)||treeJson.length<=0){return ""}  
  var ul=$("<ul>");
  treeJson.forEach(function(item,i){   
   var li=$("<li><span class='treeName'>"+item.name+"</span></li>");
   if(Array.isArray(item.children)&&item.children.length>0){
    li.append(render(item.children))
   }
   ul.append(li);
  })
  return ul
 }

 $(document).append(render(json));

好了不扯了，通過(guò)遞歸，無(wú)需再判斷數(shù)據(jù)有多少層級(jí)，只有當(dāng)前數(shù)組有children并且長(zhǎng)度大于0，函數(shù)就會(huì)遞歸調(diào)用自身，并且返回一個(gè)ul。

這樣一來(lái)，一顆非常簡(jiǎn)陋的樹(shù)就生成了，不過(guò)通常樹(shù)都帶有radio或者checkbox選擇框，而且很多時(shí)候都需要對(duì)樹(shù)的右側(cè)進(jìn)行拓展，比如加一些新增，編輯等按鈕什么的，可以考慮多傳一個(gè)對(duì)象作為參數(shù)。

   var checkbox={
    radio:"<label class='myTreeIcon'><input type='radio' name='selectTreeRedio'><span></span></label>",

    multi:"<input type='checkbox' name='selectTreeRedio'>"
   }


   function render(treeJson,option={type:0,expandDom:function(){}}){  
     if(!Array.isArray(treeJson)||treeJson.length<=0){return ""}  
     var {type,expandDom}=option;    
     var ul=$("<ul>");
     treeJson.forEach(function(item,i){
      var str="";
      if(type==1){
       str+=checkbox.multi
      }else if(type==2){
       str+=checkbox.radio
      }
      var li=$("<li data-id='"+item+"'>"+str+"<span class='treeName'>"+item.name+"</span></li>");
      expandDom&&expandDom(li,item);
      if(item.children&&item.children.length>0){
       li.append(render(item.children,option))
      }
      ul.append(li);
    })
    return ul
   }

   //option使用了一個(gè)默認(rèn)對(duì)象，默認(rèn)為不需要選擇框和不需要拓展， 如果傳入的type為1或者2，則生成checkbox或者radio，由于radio樣式比較丑，用label包起來(lái)自己模擬選中的效果；如果傳入拓展參數(shù)，則把當(dāng)前的父級(jí)li以及當(dāng)前的參數(shù)傳入，以便進(jìn)行拓展。


   $("#tree").append(render(json,{
    type:1,
    expandDom:function(el,data){
     el.append("<button>編輯</button><button>測(cè)試</button><a data-msg='"+JSON.stringify(data)+"'></a>")
    }
   }))

有時(shí)候后臺(tái)返回的可能不是拼裝好層級(jí)的數(shù)組，而是帶有pid標(biāo)識(shí)的所有數(shù)組的集合，比如：

var data = [
 {"id":2,"name":"第一級(jí)1","pid":0},
 {"id":3,"name":"第二級(jí)1","pid":2},
 {"id":5,"name":"第三級(jí)1","pid":4},
 {"id":100,"name":"第三級(jí)2","pid":3},
 {"id":6,"name":"第三級(jí)2","pid":3},
 {"id":601,"name":"第三級(jí)2","pid":6},
 {"id":602,"name":"第三級(jí)2","pid":6},
 {"id":603,"name":"第三級(jí)2","pid":6}
];

為了用遞歸來(lái)渲染出樹(shù)來(lái)，這時(shí)，就需要我們手動(dòng)來(lái)將層級(jí)裝好了：

  function arrayToJson(treeArray){
  var r = [];
  var tmpMap ={};

  for (var i=0, l=treeArray.length; i<l; i++) {
   // 以每條數(shù)據(jù)的id作為obj的key值，數(shù)據(jù)作為value值存入到一個(gè)臨時(shí)對(duì)象里面
   tmpMap[treeArray[i]["id"]]= treeArray[i]; 
  } 

  for (i=0, l=treeArray.length; i<l; i++) {
   var key=tmpMap[treeArray[i]["pid"]];
   
   //循環(huán)每一條數(shù)據(jù)的pid，假如這個(gè)臨時(shí)對(duì)象有這個(gè)key值，就代表這個(gè)key對(duì)應(yīng)的數(shù)據(jù)有children，需要Push進(jìn)去
   if (key) {
    if (!key["children"]){
      key["children"] = [];
      key["children"].push(treeArray[i]);
    }else{
     key["children"].push(treeArray[i]);
    }    
   } else {
    //如果沒(méi)有這個(gè)Key值，那就代表沒(méi)有父級(jí),直接放在最外層
    r.push(treeArray[i]);
   }
  }
  return r
  }

現(xiàn)在我們已經(jīng)實(shí)現(xiàn)了將沒(méi)有層級(jí)結(jié)構(gòu)的數(shù)組轉(zhuǎn)化為帶有層級(jí)的數(shù)組，那么問(wèn)題來(lái)了，樹(shù)形圖還常常會(huì)需要帶搜索功能，有沒(méi)有辦法把帶層級(jí)結(jié)構(gòu)的數(shù)組轉(zhuǎn)化為不帶層級(jí)結(jié)構(gòu)的一個(gè)數(shù)組呢？因?yàn)槿绻粠蛹?jí)的話(huà)，進(jìn)行搜索等操作時(shí)就非常方便，一個(gè)filter基本就可以搞定了。

  var jsonToArray=function (nodes) {
   var r=[];
   if (Array.isArray(nodes)) {
    for (var i=0, l=nodes.length; i<l; i++) {
     r.push(nodes[i]);
     if (Array.isArray(nodes[i]["children"])&&nodes[i]["children"].length>0)
      //將children遞歸的push到最外層的數(shù)組r里面
      r = r.concat(jsonToArray(nodes[i]["children"]));
       delete nodes[i]["children"]
    }
   } 
   return r;
  }

這樣，不管后臺(tái)返回什么格式給我們，我們都可以自由的互轉(zhuǎn)了，不管是帶層級(jí)的轉(zhuǎn)不帶層級(jí)的，還是把不帶層級(jí)的轉(zhuǎn)化為帶有層級(jí)的，都只需要調(diào)用一個(gè)函數(shù)就可以輕松解決。

不過(guò)這里有一個(gè)隱患，就是由于對(duì)象的引用關(guān)系，操作后雖然返回了我們需要東西，但是會(huì)改變?cè)瓉?lái)的數(shù)據(jù)。

為了不影響到原來(lái)的數(shù)據(jù)，我們需要復(fù)制一份數(shù)據(jù)，需要進(jìn)行一次深拷貝。

為什么是深拷貝而不是淺拷貝？因?yàn)闇\拷貝只會(huì)復(fù)制最外面的一層，假入某一個(gè)key值里面又是一個(gè)對(duì)象，那對(duì)復(fù)制后的對(duì)象的這個(gè)key的值進(jìn)行操作通用會(huì)影響到原來(lái)的對(duì)象。淺拷貝的方法有很多，ES6的assign,jq第一個(gè)參數(shù)不為true的 $.extend(),數(shù)組的slice(0)，還有很多很多。

對(duì)于標(biāo)準(zhǔn)的json格式的對(duì)象，可以用JSON.parse(JSON.stringify(obj))來(lái)實(shí)現(xiàn)。當(dāng)然，本文寫(xiě)的是遞歸，所以還是來(lái)手寫(xiě)一個(gè)

function deepCopy(obj){
  var object;
  if(Object.prototype.toString.call(obj)=="[object Array]"){  
   object=[];
   for(var i=0;i<obj.length;i++){
    object.push(deepCopy(obj[i]))
   }  
   return object
  }

  if(Object.prototype.toString.call(obj)=="[object Object]"){  
   object={};
   for(var p in obj){
    object[p]=obj[p]
   }  
   return object
  }
 }

其實(shí)有點(diǎn)類(lèi)似于淺拷貝，淺拷貝會(huì)復(fù)制一層，那么我們判斷某個(gè)值是對(duì)象，通過(guò)遞歸再來(lái)一次（好比飲料中獎(jiǎng)再來(lái)一瓶一樣，如果中獎(jiǎng)了，就遞歸再來(lái)一瓶，又中獎(jiǎng)就又遞歸再來(lái)一瓶，直到不再中獎(jiǎng)），也就是說(shuō)我們通過(guò)無(wú)盡的淺拷貝來(lái)達(dá)到復(fù)制一個(gè)完全的新的對(duì)象的效果。

這樣，對(duì)樹(shù)結(jié)構(gòu)操作時(shí)，只需要傳入深拷貝后新對(duì)象，就不會(huì)影響原來(lái)的對(duì)象了；