自然界的樹挖函，不需要我來解釋。不過對于計算機中的樹結(jié)構(gòu)浊竟，可難倒了一大片人怨喘。其實津畸，我們?nèi)粘Ｉ钪袝?jīng)常接觸到樹結(jié)構(gòu)。
比如必怜，一個公司的結(jié)構(gòu)劃分肉拓。公司最大的當(dāng)然是老板了，老板將公司劃分為多個大部門梳庆，各個大部門下又劃分為多個小部門暖途，而每個小部門內(nèi)部還可能會劃分為多個小組，組內(nèi)還會根據(jù)工作種類的不同劃分為不同的崗位膏执。這里丧肴，如果需要查詢這個公司總共有多少崗位，你會怎么辦胧后？想想都頭大啊芋浮。
再比如，我們計算機中存儲文件的時候壳快，一個文件夾下面有多個子文件夾纸巷，而這些子文件夾還會有其他子子文件夾，還可能會有更多眶痰。如果我們要找某個文件瘤旨，在不知道它在哪個文件夾的時候，我們會使用計算機的搜索功能竖伯。那么存哲，計算機如何來實現(xiàn)這個功能呢？想想都頭大啊七婴。
這篇文章就來介紹一下我用JS實現(xiàn)的樹結(jié)構(gòu)及其常用操作祟偷。
介紹
了解一點計算機的朋友都知道，樹是由一堆具有相同結(jié)構(gòu)的元素嵌套而來的打厘。它根據(jù)不同的特性分為很多的種類修肠，比如二叉樹，滿樹户盯，紅黑樹嵌施，B樹，B+樹等等等莽鸭。而樹的嵌套結(jié)構(gòu)就決定了吗伤，它相關(guān)的算法多數(shù)可以通過遞歸來解決，比如二叉樹的先序遍歷硫眨、中序遍歷等足淆。
廢話不多說了，直接來看看實現(xiàn)代碼吧。
實現(xiàn)一棵樹
一棵樹最重要的東西就是它的節(jié)點了缸浦，包括當(dāng)前節(jié)點及其子節(jié)點夕冲，另外還需要一個ID來唯一標(biāo)識每一個節(jié)點。所以我這里的節(jié)點如下：
var nodeID = 1;
Ycc.Tree = function() {
/**
* 節(jié)點的自增ID裂逐，不允許修改歹鱼，且每個對象必須唯一
* @type {number}
*/
this.$id = nodeID++;
/**
* 節(jié)點的父節(jié)點ID，不允許修改
* @type {null|Ycc.Tree}
*/
this.$parentID = null;
/**
* 節(jié)點的子節(jié)點列表
* @type {Array}
*/
this.children = [];
/**
* 節(jié)點所攜帶的數(shù)據(jù)
* @type {any}
*/
this.data = null;
};
上面代碼中Ycc為一個全局變量卜高，是我真正做的一個項目名弥姻，可以忽略。
可以看到掺涛，這里除了自己的ID外庭敦，還使用了parentID，這樣在尋找父節(jié)點的時候會非常方便薪缆。
另外秧廉，借助js的靈活性，直接使用children數(shù)組表示當(dāng)前節(jié)點的子節(jié)點拣帽。
如果我告訴你疼电，一棵樹我們就寫完了，你會感到驚訝嗎减拭？
事實確實如此蔽豺，樹是一個集合的概念，集合內(nèi)元素的結(jié)構(gòu)就決定了樹的結(jié)構(gòu)拧粪。只是修陡，如果這樣我們就需要手動的去設(shè)置ID和parentID，以此來保證它們的嵌套可霎。
所以魄鸦，為了豐富一棵樹，我們還需要新增一些便利的方法啥纸，來保證樹的特性号杏，而不用手動去設(shè)置婴氮。
給樹添加常用的操作
操作一：根據(jù)json初始化一棵樹
在js及其他語言中斯棒，最常用的數(shù)據(jù)結(jié)構(gòu)莫過于json了。比如主经，如下結(jié)構(gòu)是示例中的一個json荣暮，我們會根據(jù)它來生成對應(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"
},
]
}
]
}
這里的實現(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行穗酥，新建了一個root，表示這棵樹的根節(jié)點，并在第3行將json中的數(shù)據(jù)附加給節(jié)點砾跃。
第4行判斷節(jié)點是否有子節(jié)點骏啰，如果有子節(jié)點，在第5~7行我們遞歸調(diào)用方法createByJSON來為每一個子節(jié)點創(chuàng)建一顆子樹抽高，并調(diào)用addChildTree方法添加到我們的root判耕。
最后返回了我們的樹根。
這個addChildTree方法翘骂，我們暫時只需知道壁熄，它的作用是給當(dāng)前節(jié)點添加一顆子樹，稍后給出其實現(xiàn)碳竟。
可以看出草丧，這段代碼很明顯的使用了分治算法策略。
即莹桅，將我們的問題分解成多個子問題昌执，子問題使用相同的解決方法（createByJSON），待子問題解決完之后诈泼，將子問題合并（addChildTree）仙蚜，即可解決我們的原問題。
操作二：添加一顆子樹
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;
};
添加子樹厂汗，實質(zhì)上只是添加一個節(jié)點ID的引用委粉，即ID和parentID之間的關(guān)聯(lián)關(guān)系。
上面代碼中娶桦，第2行判斷了樹根贾节，第3~4行就是在操作它們的關(guān)聯(lián)關(guān)系。
操作三：獲取樹的最大深度
樹的最大深度是指衷畦，從樹根開始向下栗涂，總共有多少層級。
比如祈争，我們文章開頭斤程，對于公司示例，因為有可能有的大部門不劃分小部門菩混，這個最大深度是指公司最多劃分了幾層忿墅。
對于文件夾示例，因為有的文件夾可能為空沮峡，這個最大深度是指文件夾最多能點到哪兒疚脐。
實現(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;
};
這個地方也用到了分治策略。
第4行判斷有沒子級邢疙，第5~7行求出子級的最大深度棍弄，將其加1與當(dāng)前最大深度做比較望薄，取最大值即為我們所求的最大深度。
操作四：樹的遍歷
我總共寫了四種遍歷方法呼畸。分別是：普通遍歷 左子樹優(yōu)先遍歷 右子樹優(yōu)先遍歷 按層級向下遍歷痕支。
這里貼一個普通遍歷，感興趣的可以看看其他的遍歷方式蛮原。
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é)
對于程序員采转，樹結(jié)構(gòu)是經(jīng)常遇到的，我們的HTML文檔就是一棵樹瞬痘，xml文件也是一棵樹故慈。
各個省市縣也可以構(gòu)成一顆樹，淘寶京東的欄目分類也是一棵樹框全，任何有嵌套結(jié)構(gòu)的數(shù)據(jù)都可以構(gòu)成一棵樹察绷。
所以，掌握樹相關(guān)的算法是很有必要的津辩。
最后附一個示例拆撼，是我實現(xiàn)的一個模擬windows的文件管理器，點開鏈接看看吧喘沿。
http://www.lizhiqianduan.com/products/ycc/examples/tree/
?
