更優更簡潔的生成樹和操作樹演算法

06-06

更優更簡潔的生成樹和操作樹演算法

來自專欄前端雜記

之前要寫一個根據數據父子關係生成樹，去網上查了一些實現方法，都感覺太過麻煩，基本上都是深度循環，遞歸之類，碰到數據量大一點，層級深一點的會很麻煩，容錯性也不好。生成樹之後操作樹更是累贅，然後自己想了一個新的演算法。

該生成樹演算法時間複雜度為O(n)，實現代碼無需遞歸，只需要書寫一次循環（其實兩次，但需要寫的只有一次）。對應的操作樹可以幾乎無視數據量和樹的深度。前面有大量初/中級知識講解，大神可以直接拉到最後看完整代碼。

這裡用js舉例，其他有引用類型和基本類型的編程語言也能用。

理解這個樹演算法講解首先要知道一個基礎知識，引用類型和基本類型的區別，給不太了解的朋友簡單講講，知道的可以跳過這步。

引用類型：

var a = { home: "house", floor: 3 }; var b = a; b.TV= true; console.log(a); // {home: "house", floor: 3, TV: true} console.log(b); // {home: "house", floor: 3, TV: true}

只是操作了b，但a也會跟著改變。引用類型的賦值只是賦值地址，你可以理解為a,b是雙胞胎，他們家的地址都是一樣的，b的家裡多了一台電視，那a的家裡一樣會多一台電視。

基本類型：

var a = 1; var b = a; b = 2; console.log(a);// 1 console.log(b);// 2

基本類型不作講解。

原始數據

var table = [ { id: 1, pid: 0, name: "china" }, { id: 2, pid: 1, name: "guangdong" }, { id: 3, pid: 2, name: "shenzhen" }, { id: 4, pid: 2, name: "guangzhou" }, { id: 5, pid: 0, name: "USA" }, { id: 6, pid: 5, name: "AK" } ];

資料庫得出來的數據如上圖，id是每條數據唯一識別號，pid是其父ID。如上面name為guangdong的這條數據，他的唯一識別號是2，他的父親的唯一識別號是1，通過這個就能知道他的父為china。

建children索引

我們想找到某個id下面子節點，也可以通過建索引，但子節點並不是唯一。所以我使用分組操作。在underscore，lodash，和我寫的JCalculator都有groupBy操作，不細講分組如何實現。

var children = jc.groupBy(table,"pid");console.log(JSON.stringify(children, null, 2));

log出來的數據是。然後我們就可以停過children[1]來找到id為1的所有子數據。

{ "0": [ { "id": 1, "pid": 0, "name": "china"}, { "id": 5, "pid": 0, "name": "USA"} ], "1": [ { "id": 2, "pid": 1, "name": "guangdong"} ], "2": [ { "id": 3, "pid": 2, "name": "shenzhen"}, { "id": 4, "pid": 2, "name": "guangzhou"} ], "5": [ { "id": 6, "pid": 5, "name": "AK"} ] }

建id索引

建立children索引同理，考慮到原始數據是數組，假如我每次要根據id使用某條特性的數據，都要整個數組重新循環一次，這樣太麻煩了，而且數據多一點的話也影響性能，所以要索引。

var id = {} table.map(function(row) { var index = row["id"] id[index] = row; }); console.log(JSON.stringify(id, null, 2));

新建一個id對象，以每條id的值作為鍵，存放數據，那我們就可以通過ID號快速找到數據。log出來的數據是。那樣我們就可以通過id[1]找到id為1的數據。

{ "1": {"id": 1,"pid": 0,"name": "china"}, "2": {"id": 2,"pid": 1,"name": "guangdong"}, "3": {"id": 3,"pid": 2,"name": "shenzhen"}, "4": {"id": 4,"pid": 2,"name": "guangzhou"}, "5": {"id": 5,"pid": 0,"name": "USA"}, "6": {"id": 6,"pid": 5,"name": "AK"} }

生成樹

準備工作完成，現在開始生成樹。我能夠通過children這個對象找到某個id的所有子數據，那麼我就可以認為，我循環原始數據table，給個數據增加一個kids屬性，把對應的children索引賦值到這個kids屬性。

table.map(function(row) { var index = row["id"]; if(children[index]) { row.kids = children[index]; } }); console.log(JSON.stringify(id[1], null, 2));

列印出id為1的數據看看，是不是感覺很神奇，因為引用數據類型的特性，不使用遞歸也達到了這樣的效果。

{ "id": 1, "pid": 0, "name": "china", "kids": [ { "id": 2, "pid": 1, "name": "guangdong", "kids": [ { "id": 3, "pid": 2, "name": "shenzhen" }, { "id": 4, "pid": 2, "name": "guangzhou" } ] } ] }

整理代碼

因為生成樹的代碼和建立id索引的代碼有重複部分，這兩塊可以合併在一起。原來的數據沒有root根節點，增加一個根節點。

完整代碼如下：

你看我寫了那麼一大堆講解，其實核心就是那麼幾行代碼。jc.groupBy你們可以自己實現，或者使用lodash或者underscore代替，這裡我的是自己寫的JCalculator的分組，我實現的groupBy應對的場景更加複雜，就不細講，有要求的話，我可以另外開一篇講講。另外，這個樹演算法我也寫進了這個庫，對應更複雜場景。

操作樹

到了這裡，你就可以通過id,children對象以及對應的索引直接操作數據，基本可以無視樹深度，廣度，因為引用數據類型的特性，你修改任何一個地方，id，children,table,root都會相應，很神奇的實現了響應式樹。更改數據信息的時候，最好只通過id,children這兩個作為索引的對象改，直接方便，通過最表層的邏輯就能操作高複雜的樹。不建議操作數據的kids。

最後，這只是一個用到普通循環和引用數據類型特性的演算法，但它卻實現了一個相對複雜功能。關鍵點還是要將知識點用活，別只把引用數據類型特性當做bug去避免。

其他情況就算真的有bug，其本身就是一種特性，bug一個可以被利用。

希望這篇文章對大家有點幫助。