如何在JavaScript中將2D數組轉換爲樹（對象）？

我具有表示在此格式的樹中的二維數組：如何在JavaScript中將2D數組轉換爲樹（對象）？

[["Food", 0], ["Dairy", 1], ["Milk", 2], ["Low-fat", 3], ["Butter", 2], ["Cheese", 2], ["Vegetables", 1], ["Spinach", 2], ["Meat", 1], ["Fish", 2], ["Salmon", 3], ["Poultry", 2]]

每個項目（節點）是一個陣列，其中它的第一個元素是名稱，第二個是的水平（深度）節點。

我需要將此二維數組轉換爲嵌套的JavaScript對象，其中每個節點對象由名稱（字符串）和子對象（數組）組成。結果應該是根對象（這裏是「食物」），其他所有項目都是其子項。輸入數組總是會有序的，所以可以假定第一個元素是root。

有關迭代或遞歸的最好方法是什麼？

來源

2011-10-25 EmilyT

你怎麼知道在哪個對象下放置節點？沒有辦法知道「牛奶」和「黃油」是否與你擁有的結構一起處於「乳製品」之下。 –

@ Xeon06：每個節點都在最後一個遇到較低深度的節點下，所以'Milk'，'Butter'和'Cheese'都在'Dairy'下; 「菠菜」是「蔬菜」的獨生子;等等。 –

「牛奶」，「黃油」和「奶酪」都是二級。最後一級是「乳製品」，因此是他們的父母。「魚」也是2級，但是在更接近1級的「肉」之後。因此，一般來說，較高級別的節點是所有較低級別節點的父級節點。具有相同級別編號的下一個節點是其兄弟。 – EmilyT

遞歸是沒有必要的。我覺得這樣的事情是你在找什麼：

function tree_from_list(list) { 
    var list_node = list.shift(); 
    var depth = list_node[1]; 
    var root = {name: list_node[0], children: []}; 
    var tree_node; 
    var cur_nodes = []; 
    cur_nodes[depth] = root; 
    while (list.length > 0) { 
     list_node = list.shift(); 
     tree_node = {name: list_node[0], children: []}; 
     depth = list_node[1]; 
     if (cur_nodes[depth - 1] === undefined) 
      throw 'invalid list!'; 
     cur_nodes[depth - 1].children.push(tree_node); 
     cur_nodes[depth] = tree_node; 
    } 
    return root; 
} 
var list = [["Food", 0], ["Dairy", 1], ["Milk", 2], ["Low-fat", 3], ["Butter", 2], ["Cheese", 2], ["Vegetables", 1], ["Spinach", 2], ["Meat", 1], ["Fish", 2], ["Salmon", 3], ["Poultry", 2]]; 
var tree = tree_from_list(list);

來源

2011-10-25 19:23:47 Ben

謝謝，本！正是我在找什麼。 – EmilyT

不客氣：] – Ben

這裏的大多是沒有意義的（效率較低）遞歸解決方案：

function mktree(lis, lvl) { 
    var i, el, c, itemlis = []; 
    for (i = 0; el = lis[i++];) { 
     if (lvl !== el[1]) 
      break; 
     var item = {}; 
     [item[el[0]], c] = mktree(lis.slice(i), lvl + 1); 
     i += c - 1; // skip ahead 
     itemlis.push(item); 
    } 
    return [itemlis, i]; 
} 

function lis_to_tree(arr) { 
    return mktree(arr, 0, 0)[0][0]; 
} 

var arr = [["Food", 0], ["Dairy", 1], ["Milk", 2], ["Low-fat", 3], ["2%", 3], 
      ["Butter", 2], ["Cheese", 2], ["Vegetables", 1], ["Spinach", 2], 
      ["Meat", 1], ["Fish", 2], ["Salmon", 3], ["Poultry", 2]]; 
var tree = lis_to_tree(arr);

（請注意，這依賴於解構賦值跳過元素）

我稱之爲「毫無意義」，因爲它本質上是試圖模仿迭代，它保持已經處理的元素的數量，以便它可以在列表中跳過。我沒有說完全是沒用，因爲我仍然發現遞歸版本比它的迭代版本更容易閱讀。

來源

2011-10-25 21:22:18

如何在JavaScript中將2D數組轉換爲樹（對象）？

回答

相關問題