4

我想用 Java 表示线程注释。这看起来类似于reddit.com上的评论方式

hello
   hello
      hello
      hello
   hello
   hello
      hello

如上例所示，响应以适当的缩进嵌套在 HTML 中，以反映它们与先前评论的关系。

在 Java 中表示这一点的有效方法是什么？

我在想某种树数据结构是合适的。

但是，是否有一个特别能最有效地最小化树遍历的方法？

如果我对每条评论都进行投票，这将很重要。因为每次投票后都需要对树进行重新排序——这在计算上可能是一项昂贵的操作。

顺便说一句，如果有人知道 Java 中有一个开源的现有实现，那也会有所帮助。

4

3 回答 3

10

我会使用链表的级别。

message1
    message2
        message3
        message4
    message5
    message6
        message7

每个节点都有一个指向它的指针：

- forward sibling  (2->5, 3->4, 5->6,                   1/4/6/7->NULL).
- backward sibling (4->3, 5->2, 6->5,                   1/2/3/7->NULL).
- first child      (1->2, 2->3, 6->7,                   3/4/5/7->NULL).
- parent           (2->1, 3->2, 4->2, 5->1, 6->1, 7->6,       1->NULL).

在每个级别中，消息将按投票计数（或您想要使用的任何其他分数）在列表中排序。

这将为您移动事物提供最大的灵活性，并且您可以message2仅通过更改父级和该级别的链接来移动整个子树（例如，）。

例如，saymessage6获得大量选票，使其比message5. 更改是（调整下一个和上一个兄弟指针）：

  • message2 -> message6
  • message6 -> message5
  • message5 -> NULL.

要得到：

message1
    message2
        message3
        message4
    message6
        message7
    message5

如果它一直持续到获得的票数超过message2，则会发生以下情况：

  • message6 -> message2
  • message2 -> message5

AND的第一个子指针message1设置为message6（它是message2），仍然相对容易获得：

message1
    message6
        message7
    message2
        message3
        message4
    message5

仅当分数更改导致消息变得大于其上兄弟或小于其下兄弟时才需要重新排序。您无需在每次更改分数后重新排序。

于 2009-04-17T06:14:53.040 回答
4

树是正确的（使用 getLastSibling 和 getNextSibling），但是如果您正在存储/查询数据，您可能希望存储每个条目的沿袭，或者通过前序遍历存储编号：

http://www.sitepoint.com/article/hierarchical-data-database/2/

对于丢失确切数量的子节点，您可以留下间隙以尽量减少重新编号。不过，我不确定这是否会比每次遍历树快得多。我想这取决于你的树长得有多深。

也可以看看：

SQL - 如何存储和导航层次结构？ http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html（此方案也称为 Celko 树）

于 2009-04-17T06:11:47.353 回答
0

如果我对每条评论都进行投票，这将很重要。因为每次投票后都需要对树进行重新排序——这在计算上可能是一项昂贵的操作。

对我来说，这听起来像是一个过早的优化，甚至可能是一个错误的优化。

您的树数据结构对于表示您的数据来说听起来是合乎逻辑的。我说坚持下去。只有在检测到和测量性能问题并且可以与替代方案进行比较时，才可以稍后对其进行优化。

于 2009-04-17T06:09:55.937 回答