最有效的数据结构来表示Java中的线程注释？

Question

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

hello
   hello
      hello
      hello
   hello
   hello
      hello

如上例所示,响应嵌套在HTML中,并带有适当的缩进,以反映它们与先前注释的关系.

用Java表示这个的有效方法是什么？

我认为某种树数据结构是合适的.

但有没有一个特别是最有效的最小化树遍历？

如果我对每条评论进行投票,这将非常重要.因为在每次投票之后树需要重新排序 - 计算上可能是昂贵的操作.

顺便说一下,如果有人知道Java中的这个开源现有实现,那也会有所帮助.

Answer 1

我会使用链接列表的级别.

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通过更改父级和该级别的链接来移动整个子树(例如).

例如,说message6获得大量投票,使其更受欢迎message5.更改是(调整下一个和上一个兄弟指针):

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

要得到:

message1
    message2
        message3
        message4
    message6
        message7
    message5

如果它继续获得更多的选票message2,则会发生以下情况:

• message6 -> message2
• message2 -> message5

和第一个子指针message1设置为message6(它是message2),仍然相对容易,得到:

message1
    message6
        message7
    message2
        message3
        message4
    message5

只有当分数变化导致消息变得超过其上层兄弟或低于其下级兄弟时,才需要重新排序.每次分数变更后,您无需重新订购.