使用 parent 和 children 节点按日期排序的平面数组构建树数组（又名如何排序讨论）

Question

使用 JavaScript 从基于数字引用 ID 的平面数组构建树数组的解决方案有很多。但是我找不到任何创建树数组的解决方案，其中排序基于字母数字 ID 和日期。

我有一些讨论消息存储在平面数组中（见下文）。我需要从中创建一个树数组，所有 children 按日期排序。这样整个讨论（包括最初的消息以及对讨论线程中各种消息的回复）都按照正确的消息顺序排列，就像它们最初发布的那样。

这里是数组的一个例子。

nodes = [
    {id: 'B', references: "A", date: "2020-12-30T11:00:01-01:00"},        
    {id: 'J', references: "F", date: "2020-12-30T11:00:06-01:00"},
    {id: 'D', references: "A", date: "2020-12-30T11:00:07-01:00"},
    {id: 'A', references: "", date: "2020-12-30T11:00:00-01:00"}, // initial post has no reference
    {id: 'E', references: "C", date: "2020-12-30T11:00:03-01:00"},
    {id: 'F', references: "E", date: "2020-12-30T11:00:04-01:00"},
    {id: 'C', references: "A", date: "2020-12-30T11:00:02-01:00"},
    {id: 'I', references: "G", date: "2020-12-30T11:00:09-01:00"},
    {id: 'G', references: "A", date: "2020-12-30T11:00:08-01:00"},
    {id: 'H', references: "G", date: "2020-12-30T11:00:09-02:00"},
    {id: 'K', references: "F", date: "2020-12-30T11:00:05-01:00"},
];

目标是可视化地打印一个有序的讨论树，所以看起来像这样：

A
_ B
_ C
_ _ E
_ _ _ F
_ _ _ _ K
_ _ _ _ J
_ D
_ G
_ _ I
_ _ H

我正在寻找 JavaScript 解决方案。

更新：

我发现，下面的代码将创建正确的树：

数组中的所有条目按天 pre-sorted

let arr = [
{id: 'A', references: "", date: "2020-12-30T11:00:00-01:00"},
{id: 'B', references: "A", date: "2020-12-30T11:00:01-01:00"},
{id: 'C', references: "A", date: "2020-12-30T11:00:02-01:00"},
{id: 'E', references: "C", date: "2020-12-30T11:00:03-01:00"},
{id: 'F', references: "E", date: "2020-12-30T11:00:04-01:00"},
{id: 'K', references: "F", date: "2020-12-30T11:00:05-01:00"},
{id: 'J', references: "F", date: "2020-12-30T11:00:06-01:00"},
{id: 'D', references: "A", date: "2020-12-30T11:00:07-01:00"},
{id: 'G', references: "A", date: "2020-12-30T11:00:08-01:00"},
{id: 'I', references: "G", date: "2020-12-30T11:00:09-01:00"},
{id: 'H', references: "G", date: "2020-12-30T11:00:09-02:00"},
];

function unflatten(arr) {
var tree = [],
mappedArr = {},
arrElem,
mappedElem;

// First map the nodes of the array to an object -> create a hash table.
for(var i = 0, len = arr.length; i < len; i++) {
arrElem = arr[i];
mappedArr[arrElem.id] = arrElem;
mappedArr[arrElem.id]['children'] = [];
}


for (var id in mappedArr) {
if (mappedArr.hasOwnProperty(id)) {
mappedElem = mappedArr[id];
// If the element is not at the root level, add it to its parent array of children.
if (mappedElem.references) {
mappedArr[mappedElem['references']]['children'].push(mappedElem);
}
// If the element is at the root level, add it to first level elements array.
else {
tree.push(mappedElem);
}
}
}
return tree;
}

var tree = unflatten(arr);
console.log(tree);
document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " "))

结果：

 [
 {
  "id": "A",
  "references": "",
  "date": "2020-12-30T11:00:00-01:00",
  "children": [
   {
    "id": "B",
    "references": "A",
    "date": "2020-12-30T11:00:01-01:00",
    "children": []
   },
   {
    "id": "C",
    "references": "A",
    "date": "2020-12-30T11:00:02-01:00",
    "children": [
     {
      "id": "E",
      "references": "C",
      "date": "2020-12-30T11:00:03-01:00",
      "children": [
       {
        "id": "F",
        "references": "E",
        "date": "2020-12-30T11:00:04-01:00",
        "children": [
         {
          "id": "K",
          "references": "F",
          "date": "2020-12-30T11:00:05-01:00",
          "children": []
         },
         {
          "id": "J",
          "references": "F",
          "date": "2020-12-30T11:00:06-01:00",
          "children": []
         }
        ]
       }
      ]
     }
    ]
   },
   {
    "id": "D",
    "references": "A",
    "date": "2020-12-30T11:00:07-01:00",
    "children": []
   },
   {
    "id": "G",
    "references": "A",
    "date": "2020-12-30T11:00:08-01:00",
    "children": [
     {
      "id": "I",
      "references": "G",
      "date": "2020-12-30T11:00:09-01:00",
      "children": []
     },
     {
      "id": "H",
      "references": "G",
      "date": "2020-12-30T11:00:09-02:00",
      "children": []
     }
    ]
   }
  ]
 }
]

https://jsfiddle.net/jarosciak/73xuk25q/3/

有更好的主意吗？

Answer 1

以下是我最终使用的代码：

window.addEventListener('load', (event) => {

obj = [
{id: 'A', references: "", date: "2020-12-30T11:00:00-01:00", subject: "Title #1", body: "Message Body #1"},
{id: 'B', references: "A", date: "2020-12-30T11:00:01-01:00", subject: "Title #2", body: "Message Body #2"},
{id: 'C', references: "A", date: "2020-12-30T11:00:02-01:00", subject: "Title #3", body: "Message Body #3"},
{id: 'E', references: "C", date: "2020-12-30T11:00:03-01:00", subject: "Title #4", body: "Message Body #4"},
{id: 'F', references: "E", date: "2020-12-30T11:00:04-01:00", subject: "Title #5", body: "Message Body #5"},
{id: 'K', references: "F", date: "2020-12-30T11:00:05-01:00", subject: "Title #6", body: "Message Body #6"},
{id: 'J', references: "F", date: "2020-12-30T11:00:06-01:00", subject: "Title #7", body: "Message Body #7"},
{id: 'D', references: "A", date: "2020-12-30T11:00:07-01:00", subject: "Title #8", body: "Message Body #8"},
{id: 'G', references: "A", date: "2020-12-30T11:00:08-01:00", subject: "Title #9", body: "Message Body #9"},
{id: 'I', references: "G", date: "2020-12-30T11:00:09-01:00", subject: "Title #10", body: "Message Body #10"},
{id: 'H', references: "G", date: "2020-12-30T11:00:09-02:00", subject: "Title #11", body: "Message Body #11"},
]

obj.sort(function(a, b){
    return (a.references == null ? 0 : a.references) - (b.references == null ? 0 : b.references);
});

var tree = document.getElementById("tree");
for (var i = 0; i < obj.length; ++i)
  {
        var msg_draft = "<b>" + obj[i].id + "</b><br>" + obj[i].subject + "<br>(" + obj[i].date + ")<br>" + obj[i].body;
    if ((obj[i].references == null) || (obj[i].references == ""))
      {
        createTreeElement("li", obj[i].id, msg_draft , tree);
      }
    else
      {
         var treeChildNode = document.getElementById("t" + obj[i].references).getElementsByTagName("ul");
        if (treeChildNode.length)
          {
            createTreeElement("li", obj[i].id, msg_draft , treeChildNode[0]);
          }
        else
          {
            createTreeElement("ul", obj[i].references, "", document.getElementById("t" + obj[i].references));
            createTreeElement("li", obj[i].id, msg_draft , document.getElementById("t" + obj[i].references).getElementsByTagName("ul")[0]);
          }
      }
  }

function createTreeElement(name, id, text, parent)
{
  var node = document.createElement(name);
  node.id = "t" + id;
  node.innerHTML = text;
  parent.appendChild(node);
}
});

<ul id="tree"></ul>

另外，将平面数组排序为树形数组的结果；及其最终的 HTML 表示，如果有人想玩它，可以在这个 JS Fiddle 中看到： https://jsfiddle.net/jarosciak/jd6hLvr4/

使用 parent 和 children 节点按日期排序的平面数组构建树数组（又名如何排序讨论）

Building a tree array from flat array with parent and children nodes sorted by date (aka how to sort a discussion)

javascript

sorting

nntp