JavaScript嵌套樹排名

我花了相當一段時間思考某個問題，但我找不到滿意的解決方案，它對我來說已成爲一個阻塞問題。
情況如下。JavaScript嵌套樹排名

我正在寫管理動態樹結構（沒有二進制）小Javascript庫，並且其中根/節點被表示爲在一個JSON數組對象：

var json = [{ text: "root", children: [ 
       {id: "id_1", text: "node_1", children:[ 
        {id: "id_c1", text: "node_c1"}, 
        {id: "id_c2", text: "node_c2", children: [ 
         {id: "id_c2_c1", text: "node_c2_c1"}, 
         {id: "id_c2_c2", text: "node_c2_c2"}, 
         {id: "id_c2_c3", text: "node_c2_c3"}]}, 
        {id: "id_c3", text: "node_c3"}]}, 
       {id: "id_2", text: "node_2"}]}];

我有幾個問題（第一個是核心，其他核心是由它產生的）：

似乎不可能以直接方式（從上到下）對節點進行排名。插入/刪除節點會使得排名變得糟糕。
次要的，因此，我找不到一個好的方法來實現間隔（節點數組）的檢索，當給出兩個節點（開始/結束）時。這在一個換檔選擇樹形菜單上的範圍：

另一個後果是，我不能維持我的節點時的正確順序隨機選擇並將它們添加到臨時數組中（使用命令鍵 - 用於以與檢索到的順序相同的順序拖放）。由於我無法爲節點分配排名，所以我無法維持其順序。

最明顯的解決方案是扁平化json數組並重新索引每個操作的所有節點（這顯然有效），但我相當肯定這總體上是一個相當糟糕的想法（低效率）。

我想出的另一個想法是根據算法（使用索引，級別等）爲每個節點賦予一定的「權重」。但我無法找到一個正確的方法來計算重量。而且，它不能解決問題，因爲插入/刪除隨機節點似乎仍然需要重建索引。

這裏是我當前的代碼：https://gist.github.com/kimgysen/9d066bdf095b853c4d0e67517a76777d

任何幫助或輸入對此事將不勝感激......

注：我不希望任何人去通過整個代碼，它更我堅持的概念性編程問題。如果有的話，我對概念性解決方案感到滿意。

來源

2016-05-13 Trace

幻燈片我不知道你的意思究竟是什麼，但你並不需要維持一個索引，你可以指望你想通過索引檢索每一次。看看「深度優先預置遍歷」。很明顯，指數會隨着插入而改變;如果你不想這樣做，你就不能使用索引;您可以使用唯一的ID代替。 – Amadan

@Amadan隨着索引我的意思是按特定順序列出節點，並根據它們從頂部的位置給出一個值，以便能夠在整個樹上維護任何節點的順序與另一個節點的順序。不知道我是否清楚。我會檢查你的建議，謝謝。不知何故，我正在尋找一種重新編制索引的方法，但採用更優化的方式，而不是重新索引整個樹。考慮到一棵很大的樹，我不確定這會對性能產生什麼影響。 – Trace

我明白了。對於一棵非常大的樹，我同意，重塑變革更有意義。儘管如此，預先遍歷是以您想要的順序訪問所有節點的方式。 – Amadan

這是我的解決方案：

 [ {id: "root",  p_id: 0,  l_id: 0,   text: "website"}, 
     {id: "header", p_id: "root", l_id: 0,   text: "Parent: root, left: none"}, 
     {id: "nav",  p_id: "header", l_id: 0,   text: "Parent: header, left:none"}, 
     {id: "headline", p_id: "header", l_id: "nav",  text: "Parent: header, left: nav"}, 
     {id: "promotion", p_id: "header", l_id: "headline", text: "Parent: header, left: headline"}, 
     ];

插入一個節點

如果需要 '標題' 之前插入一個名爲 'new_node' 新節點。

{id: "new_node",  p_id: ,  l_id: ,   text: "Parent:header, left:nav"},

查找元素ID是 '標題'。
將其p_id和l_id複製到new_node。

將'標題'的l_id更新爲'new_node'。

{id: "headline", p_id: "header", l_id: "new_node",  text: "Parent: header, left: new_node"} 
{id: "new_node", p_id: "header", l_id: "nav",  text: "Parent: header, left: nav"},

刪除節點

刪除 '標題'。

保存標題的l_id並刪除元素。
查找所有p_id爲'標題'的元素，將其刪除。
找到'l_id'爲'標題'的元素，將其l_id更改爲標題的元素。

該解決方案從「分層分類模型」派生，每個元素可能有孩子，和孩子可以再有孩子。除此之外，「父節點」內的每個元素都需要知道他的直接兄弟。我認爲這是一個「鏈接列表」結構。

這裏是hierarchical categories model

來源

2016-05-13 09:05:54 Jacob

JavaScript嵌套樹排名

回答

相關問題