Javascript嵌套树排名

Question

我花了很多时间思考某个问题，但我找不到满意的解决方案，它正在成为我的一个阻塞问题。
情况如下。

我正在编写一个管理动态树结构(非二进制)的小型 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"}]}]; 

我有几个密切相关的问题(第一个是核心，其他问题由它产生):

1. 似乎不可能以直接的方式(从上到下)对节点进行排名。插入/删除节点会搞砸排名。
2. 其次，因此，当给定两个节点(开始/结束)时，我找不到实现间隔(节点数组)检索的好方法。这在树形菜单上的 shift-select 范围内:

1. 另一个结果是，在进行随机选择并将它们添加到临时数组时(使用命令键 - 目的是按照与检索到的顺序相同的顺序拖/放)，我无法保持节点的正确顺序。由于我无法为节点分配排名，因此无法维护它们的顺序。

最明显的解决方案是展平 json 数组并在每次操作时重新索引所有节点(这显然有效)，但我相当肯定这总体上是一个相当糟糕的主意(效率低下)。

我想到的另一个想法是根据算法(使用索引、级别等)为每个节点分配一定的“权重”。但是我找不到正确的方法来计算重量。此外，它并没有解决问题，因为插入/删除随机节点似乎仍然需要重建索引。

这是我当前的代码:https://gist.github.com/kimgysen/9d066bdf095b853c4d0e67517a76777d

如有任何帮助或意见，我们将不胜感激......

注意:我不希望任何人通读整个代码，这更像是我遇到的概念性编程问题。如果有的话，我对概念性解决方案感到满意。

Answer 1

这是我的解决方案:

       [ {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"},
       ]; 

插入一个节点

如果需要在'headline'之前插入一个名为'new_node'的新节点。

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

1. 找到id为'headline'的元素。
2. 将其 p_id 和 l_id 复制到 new_node。

3. 将“标题”的 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"},
   

删除节点

删除“标题”。

1. 保存标题的l_id，并删除该元素。
2. 找出所有p_id为'headline'的元素，删除。
3. 找到'l_id'为'headline'的元素，将其l_id改为headline的。

这个解决方案源自“层级类别模型”，每个元素都可能有 child ， child 又可能有 child 。除此之外，“父节点”中的每个元素都需要知道他的直接兄弟节点。我认为这是一个“链表”结构。

这是 hierarchical categories model 的幻灯片