自然界的樹，不需要我來(lái)解釋。不過(guò)對(duì)于計(jì)算機(jī)中的樹結(jié)構(gòu)，可難倒了一大片人。其實(shí)，我們?nèi)粘Ｉ钪袝?huì)經(jīng)常接觸到樹結(jié)構(gòu)。

比如，一個(gè)公司的結(jié)構(gòu)劃分。公司最大的當(dāng)然是老板了，老板將公司劃分為多個(gè)大部門，各個(gè)大部門下又劃分為多個(gè)小部門，而每個(gè)小部門內(nèi)部還可能會(huì)劃分為多個(gè)小組，組內(nèi)還會(huì)根據(jù)工作種類的不同劃分為不同的崗位。這里，如果需要查詢這個(gè)公司總共有多少崗位，你會(huì)怎么辦？想想都頭大啊。

再比如，我們計(jì)算機(jī)中存儲(chǔ)文件的時(shí)候，一個(gè)文件夾下面有多個(gè)子文件夾，而這些子文件夾還會(huì)有其他子子文件夾，還可能會(huì)有更多。如果我們要找某個(gè)文件，在不知道它在哪個(gè)文件夾的時(shí)候，我們會(huì)使用計(jì)算機(jī)的搜索功能。那么，計(jì)算機(jī)如何來(lái)實(shí)現(xiàn)這個(gè)功能呢？想想都頭大啊。

這篇文章就來(lái)介紹一下我用JS實(shí)現(xiàn)的樹結(jié)構(gòu)及其常用操作。

介紹

了解一點(diǎn)計(jì)算機(jī)的朋友都知道，樹是由一堆具有相同結(jié)構(gòu)的元素嵌套而來(lái)的。它根據(jù)不同的特性分為很多的種類，比如二叉樹，滿樹，紅黑樹，B樹，B+樹等等等。而樹的嵌套結(jié)構(gòu)就決定了，它相關(guān)的算法多數(shù)可以通過(guò)遞歸來(lái)解決，比如二叉樹的先序遍歷、中序遍歷等。

廢話不多說(shuō)了，直接來(lái)看看實(shí)現(xiàn)代碼吧。

實(shí)現(xiàn)一棵樹

一棵樹最重要的東西就是它的節(jié)點(diǎn)了，包括當(dāng)前節(jié)點(diǎn)及其子節(jié)點(diǎn)，另外還需要一個(gè)ID來(lái)唯一標(biāo)識(shí)每一個(gè)節(jié)點(diǎn)。所以我這里的節(jié)點(diǎn)如下：

var nodeID = 1;

Ycc.Tree = function() {

   /**
    * 節(jié)點(diǎn)的自增ID，不允許修改，且每個(gè)對(duì)象必須唯一
    * @type {number}
    */
   this.$id = nodeID++;

   /**
    * 節(jié)點(diǎn)的父節(jié)點(diǎn)ID，不允許修改
    * @type {null|Ycc.Tree}
    */
   this.$parentID = null;

   /**
    * 節(jié)點(diǎn)的子節(jié)點(diǎn)列表
    * @type {Array}
    */
   this.children = [];

   /**
    * 節(jié)點(diǎn)所攜帶的數(shù)據(jù)
    * @type {any}
    */
   this.data = null;

};

上面代碼中Ycc為一個(gè)全局變量，是我真正做的一個(gè)項(xiàng)目名，可以忽略。

可以看到，這里除了自己的ID外，還使用了parentID，這樣在尋找父節(jié)點(diǎn)的時(shí)候會(huì)非常方便。

另外，借助js的靈活性，直接使用children數(shù)組表示當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)。

如果我告訴你，一棵樹我們就寫完了，你會(huì)感到驚訝嗎？

事實(shí)確實(shí)如此，樹是一個(gè)集合的概念，集合內(nèi)元素的結(jié)構(gòu)就決定了樹的結(jié)構(gòu)。只是，如果這樣我們就需要手動(dòng)的去設(shè)置ID和parentID，以此來(lái)保證它們的嵌套。

所以，為了豐富一棵樹，我們還需要新增一些便利的方法，來(lái)保證樹的特性，而不用手動(dòng)去設(shè)置。

給樹添加常用的操作

操作一：根據(jù)json初始化一棵樹

在js及其他語(yǔ)言中，最常用的數(shù)據(jù)結(jié)構(gòu)莫過(guò)于json了。比如，如下結(jié)構(gòu)是示例中的一個(gè)json，我們會(huì)根據(jù)它來(lái)生成對(duì)應(yīng)的樹。

{
   data:'/',
   children:[
      {
         data:"a",
         children:[
            {
               data:"d",
               children:[
                  {
                     data:"g"
                  },
                  {
                     data:"h"
                  },
                  {
                     data:"i"
                  },
               ]
            },
            {
               data:"e",
               children:[
                  {
                     data:"j"
                  },
                  {
                     data:"k"
                  },
                  {
                     data:"l"
                  },
               ]
            },
            {
               data:"f"
            },
         ]
      },
      {
         data:"b",
         children:[
            {
               data:"m"
            },
            {
               data:"n"
            },
         ]
      },
      {
         data:"c",
         children:[
            {
               data:"o"
            },
            {
               data:"p"
            },
            {
               data:"q"
            },
         ]
      }
   ]
}

這里的實(shí)現(xiàn)代碼如下：

Ycc.Tree.createByJSON = function (json) {
   var root = new Ycc.Tree();
   root.data = json.data;
   if(Ycc.utils.isArray(json.children) && json.children.length>0){
      for(var i=0;i<json.children.length;i++){
         root.addChildTree(Ycc.Tree.createByJSON(json.children[i]));
      }
   }
   return root;
};

上面代碼，第2行，新建了一個(gè)root，表示這棵樹的根節(jié)點(diǎn)，并在第3行將json中的數(shù)據(jù)附加給節(jié)點(diǎn)。

第4行判斷節(jié)點(diǎn)是否有子節(jié)點(diǎn)，如果有子節(jié)點(diǎn)，在第5~7行我們遞歸調(diào)用方法createByJSON來(lái)為每一個(gè)子節(jié)點(diǎn)創(chuàng)建一顆子樹，并調(diào)用addChildTree方法添加到我們的root。

最后返回了我們的樹根。

這個(gè)addChildTree方法，我們暫時(shí)只需知道，它的作用是給當(dāng)前節(jié)點(diǎn)添加一顆子樹，稍后給出其實(shí)現(xiàn)。

可以看出，這段代碼很明顯的使用了分治算法策略。

即，將我們的問(wèn)題分解成多個(gè)子問(wèn)題，子問(wèn)題使用相同的解決方法（createByJSON），待子問(wèn)題解決完之后，將子問(wèn)題合并（addChildTree），即可解決我們的原問(wèn)題。

操作二：添加一顆子樹

Ycc.Tree.prototype.addChildTree = function (tree) {
   if(tree.$parentID) return console.error("sub tree's parent has exist! can't add!",tree);
   tree.$parentID = this.$id;
   this.children.push(tree);
   return this;
};

添加子樹，實(shí)質(zhì)上只是添加一個(gè)節(jié)點(diǎn)ID的引用，即ID和parentID之間的關(guān)聯(lián)關(guān)系。

上面代碼中，第2行判斷了樹根，第3~4行就是在操作它們的關(guān)聯(lián)關(guān)系。

操作三：獲取樹的最大深度

樹的最大深度是指，從樹根開始向下，總共有多少層級(jí)。

比如，我們文章開頭，對(duì)于公司示例，因?yàn)橛锌赡苡械拇蟛块T不劃分小部門，這個(gè)最大深度是指公司最多劃分了幾層。

對(duì)于文件夾示例，因?yàn)橛械奈募A可能為空，這個(gè)最大深度是指文件夾最多能點(diǎn)到哪兒。

實(shí)現(xiàn)代碼如下：

Ycc.Tree.prototype.getDepth = function () {
   var self = this;
   var dep = 1;
   if(self.children.length>0){
      for(var i=0;i<self.children.length;i++){
         var subDep = self.children[i].getDepth();
         dep = subDep+1>dep?subDep+1:dep;
      }
   }
   return dep;
};

這個(gè)地方也用到了分治策略。

第4行判斷有沒(méi)子級(jí)，第5~7行求出子級(jí)的最大深度，將其加1與當(dāng)前最大深度做比較，取最大值即為我們所求的最大深度。

操作四：樹的遍歷

我總共寫了四種遍歷方法。分別是：普通遍歷 左子樹優(yōu)先遍歷 右子樹優(yōu)先遍歷 按層級(jí)向下遍歷。

這里貼一個(gè)普通遍歷，感興趣的可以看看其他的遍歷方式。

Ycc.Tree.prototype.itor = function (option) {
   var self = this;
   function each(cb) {
      if(cb.call(self,self)) return true;
      if(self.children.length>0){
         for(var i=0;i<self.children.length;i++){
            if(self.children[i].itor().each(cb)) return true;
         }
      }
      return false;
   }
}

地址為：https://github.com/lizhiqianduan/ycc/blob/develop/src/Ycc.Tree.class.js

總結(jié)

對(duì)于程序員，樹結(jié)構(gòu)是經(jīng)常遇到的，我們的HTML文檔就是一棵樹，xml文件也是一棵樹。

各個(gè)省市縣也可以構(gòu)成一顆樹，淘寶京東的欄目分類也是一棵樹，任何有嵌套結(jié)構(gòu)的數(shù)據(jù)都可以構(gòu)成一棵樹。

所以，掌握樹相關(guān)的算法是很有必要的。

最后附一個(gè)示例，是我實(shí)現(xiàn)的一個(gè)模擬windows的文件管理器，點(diǎn)開鏈接看看吧。

http://www.lizhiqianduan.com/products/ycc/examples/tree/

?