前言
筆者所做的一個專案需要做一個前端的樹形選單，后端回傳的資料是一個平行的list，list中的每個元素都是一個物件，例如list[0]的值為{id: 1, fid: 0, name: 一級選單}，每個元素都指定了父元素，生成的選單可以無限級嵌套，一開始找的插件需要手動將生成好的樹形陣列傳進去才能使用（盡管后來找到了一個UI框架，可以直接傳list進去，只需要指定id和fid），但是當時思索了好久都沒能正確寫出來，故在空下來的時候認真想了一下，整理成筆記，以便后期查閱，
準備作業
因為是前端處理，所以本文實作語言為js，
如下，有一個平行的list串列和一個不在list中的根節點root：
var s = [
{ id: 1, fid: 0, name: "第一級選單1" },
{ id: 2, fid: 0, name: "第一級選單2" },
{ id: 3, fid: 1, name: "第二級選單1.1" },
{ id: 4, fid: 1, name: "第二級選單1.2" },
{ id: 5, fid: 2, name: "第二級選單2.1" },
{ id: 6, fid: 3, name: "第三級選單1.1.1" },
{ id: 7, fid: 3, name: "第三級選單1.1.2" },
{ id: 8, fid: 4, name: "第三級選單1.2.1" },
{ id: 9, fid: 4, name: "第三級選單1.2.2" },
{ id: 10, fid: 6, name: "第四級選單1.1.1.1" },
{ id: 11, fid: 6, name: "第四級選單1.1.1.2" },
{ id: 12, fid: 9, name: "第四級選單1.2.2.1" },
{ id: 13, fid: 9, name: "第四級選單1.2.2.2" },
{ id: 14, fid: 0, name: "第一級選單3" }
]
var root = { id: 0, fid: 0, name: "根選單" };
需要整理成類似于下面的樣子，如果該節點沒有子節點，就沒有node屬性：
{
id: xx,
fid: xx,
name: xx,
node: [
id: xx,
fid: xx,
name: xx,
node: [...]
]
}
需要一個打亂list順序的shuffle演算法，該演算法會對原陣列進行影響：
function shuffle(a) {
var len = a.length;
for (var i = 0; i < len; i++) {
var end = len - 1;
var index = (Math.random() * (end + 1)) >> 0;
var t = a[end];
a[end] = a[index];
a[index] = t;
}
};
使用JSON序列化來實作陣列的深度拷貝：
function deepCopy(arr) {
return JSON.parse(JSON.stringify(arr));
}
使用一個簡單的方式來初步判斷結果是否正確：
function check(node) {
return JSON.stringify(node).match(/選單/g).length;
}
使用遞回
【思路】
對于這種問題，因為不知道到底要回圈多少層，所以使用遞回能夠以一種很方便的方式來解決，
【步驟】
1. 遍歷當前串列，找出fid為傳入的父元素的id的節點，并掛到父元素的node上；
2. 每找到一個節點就從當前串列洗掉這個元素（不然遞回怎么終止）；
3. 對于每一個子節點，重復如上步驟，將子節點當成下一層的父節點繼續查找該節點的子節點，
可以看到，時間復雜度最壞為O(n!)，
【實作】
function arr2tree(arr, father) {
// 遍歷陣列，找到當前father的所有子節點
for (var i = 0; i < arr.length; i++) {
if (arr[i].fid == father.id) {
// 這里是有子節點才需要有node屬性（也就是說有node里絕不會為空list）
if (!father.node) {
father.node = [];
}
var son = arr[i];
father.node.push(son);
arr.splice(i, 1); // 洗掉該節點，當list為空的時候就終止遞回
i--; // 由于洗掉了i節點，所以下次訪問的元素下標應該還是i
}
}
// 再對每一個子節點進行如上操作
if (father.node) { // 需要先判斷有沒有子節點
var childs = father.node;
for (var i=0; i<childs.length; i++) {
arr2tree(arr, childs[i]); // 呼叫遞回函式
}
// 用于按名稱進行排序，如果不強調順序可以去掉
father.node.sort(function (a, b) {
return a.name > b.name;
})
}
}
【檢驗】
shuffle(s); // 打亂陣列
var arr = deepCopy(s); // 拷貝一份，避免對原陣列進行修改
arr2tree(arr, root);
console.log(check(root)); // 預期輸出15
console.log(root); // 手工檢查輸出是否正確
不使用遞回
【思路】
當資料量大的時候，使用遞回及其容易因為記憶體溢位而無法運行，有沒有不使用遞回的方式呢？能不能夠直接就用回圈來搞定呢？能不能邊遍歷這個元素，就直接把這個元素放到正確的位置上，這樣就可以省好多事情，可以用一個哈希表（字典/物件）來儲存這些元素，鍵（屬性名）就是元素的id，這樣就可以直接判斷當前遍歷的元素的父元素在不在哈希表里面了，
忽然，筆者想到了一個特性——參考，js中的物件都是參考的，哪怕我已經把a物件push進一個list中了，我在后面對a物件進行的任何修改都會在list中反映出來，也就是說，我把a元素掛到對應的父元素f上了，當我在后面找到a元素的子元素b時，我把該子元素b掛到a上，f中掛載的a也會一樣有b元素，
【步驟】
1. 新建一個物件temp用于存放臨時資訊，遍歷串列，將當前訪問元素a加到temp中（屬性名為物件id，屬性值為該物件）；
2. 在temp中查找是否有a的子節點，有的話就將子節點掛到a上；
3. 在temp中查找是否有a的父節點，有的話就將a掛到父節點上；
可以看到，時間復雜度為O(n^2^)，空間復雜度也不會太高，該方法不會對原陣列進行修改，
【實作】
function arr2tree2(arr, root) {
var temp = {};
temp[root.id] = root;
for (var i = 0; i < arr.length; i++) {
// 插入一個新節點，后面對該節點的修改都會同步到該節點的父節點上
temp[arr[i].id] = arr[i];
// 查找是否有子節點
var keys = Object.keys(temp);
for (var j = 0; j < keys.length; j++) {
if (temp[keys[j]].fid == arr[i].id) {
temp[arr[i].id].node ? "" : temp[arr[i].id].node = [];
temp[arr[i].id].node.push(temp[keys[j]]); // 將該子節點掛到當前節點的node上
}
}
// 查找是否有父節點
if (temp[arr[i].fid]) {
temp[arr[i].fid].node ? "" : temp[arr[i].fid].node = [];
temp[arr[i].fid].node.push(arr[i]); // 將當前節點掛到父節點的node上
}
}
return temp;
}
【檢驗】
shuffle(s); // 打亂陣列
var result = arr2tree2(s, root);
console.log(check(result[root.id])); // 預期輸出15
console.log(result[root.id]); // 手工檢查輸出是否正確
總結
平時筆者所做的專案大多也不涉及到演算法，平時秉承的也是能用回圈解決的就用回圈解決，可以看到，演算法對于程式員而言還是很重要的，本文也只是個人的想法，歡迎一起探討，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/171268.html
標籤：JavaScript
上一篇：前端之js