5

我目前正在实施一个二维范围树。我无法为我的 Node 类提出一个合理的模型（Java 中）。

树中的节点可能具有以下任何内容：中间值、左右子指针、子树、数据指针和/或前一个和下一个指针。

我已将节点分解为三个独立的逻辑部分

  • a) 只有 midRange 值的节点 - 每个节点都有一个 midRange
  • b) 具有左、右和子树点的节点。这表示一个非叶节点。
  • c) 不适用于 next、prev 和 data 指针。这代表一个叶节点。

我尝试应用 Composite 和 Decorator 模式，但无济于事。我尝试制作：

  1. 具有所有可能的 getter/setter 的节点接口，即：getMidRange、getLeft、getRight、setLeft、setRight 等...
  2. 有两个类实现接口：Node2D 和 LinkedNode（叶节点）。Node2D 做了所有事情，除了保留下一个和上一个的链接。而 LinkedNode 只保留下一个和上一个的链接。

它是这样工作的，但是如果有更好的方法将其建模为一组类，我会徘徊吗？

编辑：范围树（简短信息）：在范围树中 - 所有数据都存储在叶节点中，并且树总是平衡的。此外，所有叶子都处于相同的高度。此外，叶子被排序，并通过双向链表链接在一起。最后但并非最不重要的一点是，每个非叶子节点都有一个子树——它也是一个范围树，但叶子按下一个属性排序（如果原始树按x排序，则说y）。

范围树分解

4

1 回答 1

1 
abstract class AbstractNode {
    int midRange;
}

class InnerNode extends AbstractNode {
    AbstractNode left;
    AbstractNode right;
    AbstractNode subtree;
}

class LeafNode extends AbstractNode {
    LeafNode next;
    LeafNode prev;
    Object data;
}
于 2011-02-13T04:24:04.193 回答