Java: 实现树及其节点的并行层次结构

Question

为了练习数据结构，我正在实现自己的树库。我从 BST 开始，接下来我将要实现 AVL 树、红黑树等等。 AVL 和 RBT 也是 BST 树，所以一些 class 层次结构相当明显。我遇到的问题是所有这些树都有其他类型的节点——AvlNode 有平衡因子标志，RgbNode 有颜色标志，BstNode 不需要任何额外信息（尽管所有节点都需要对父节点、子节点和值的引用） .所以我有一个节点层次结构和一个树层次结构。我可以给 BstNode 一些标志属性并在扩展 classes 时使用它，但这肯定不是一个好方法。

问题是如何处理这样一个事实，例如 Bst.findNode() 将 return BstNode 但在 Avl 中我需要 AvlNode 尽管 findNode() 方法在两者中都是相同的（除了 return 类型）。

我在规划层次结构方面需要帮助，或者如果那些并行层次结构（作为代码味道）通常不是一个好主意，我需要一个解决方法，因为我不知道如何以正确的方式做到这一点。

BstTree Class:

public class BstTree<T extends Comparable> implements Iterable
{
    private BstNode<T> root;

    public void addValue(T value)
    {
        BstNode node = new BstNode(value);
        addNode(node);
    }

    public void addNode(BstNode<T> node)
    {
        ...
    }

    public boolean removeNode(T value)
    {
       ...
    }


    public BstNode findNode(T value)
    {
        ...
    }
    //other less significant methods
}

BstNode class:

public class BstNode<T extends Comparable>
{
    private static int lastId = 0;
    private int id;
    private T value;
    private BstNode parent = null;
    private BstNode leftChild = null;
    private BstNode rightChild = null;

    public BstNode(T value) {
        this.id = ++lastId;
        this.value = value;
    }

    public boolean isGreaterThan(BstNode n)
    {
        //...
    }

    public boolean hasLeftChild()
    {
        //...
    }

    public boolean hasRightChild()
    {
        //...
    }

    public boolean hasParent()
    {
        //...
    }

    public boolean isLeaf()
    {
        //...
    }

    public boolean hasOnlyOneChild()
    {
        //...
    }

    public BstNode getOnlyChild(BstNode node)
    {
        ...
    }

    public boolean isLeftChildren()
    {
        ...
    }

    public BstNode getConsequentNode()
    {
        ...
    }
}

我猜上面的职责分离可能不是很完美，如果错了我可能会得到一些从Node到Tree的方法class不过这个东西问题不大

Answer 1

我会这样做：

public abstract class BstTree<T extends Comparable,N extends BstNode<T,N>> {
    private N root;
...

    public void addValue(T value)
    {
        N node = newNode(value);
        addNode(node);
    }

    public abstract N newNode(T value);

    public void addNode(N node)
    {
        // ...
    }
}

public class BstNode<T extends Comparable,N extends BstNode<T,N>>
{
    private T value;
    private N parent = null;
    private N leftChild = null;
    private N rightChild = null;

    public BstNode(T value) {
        this.value = value;
    }

    public N getOnlyChild(N node)
    {
        // ...
    }
...
}

public class AVLTree<T extends Comparable> extends BstTree<T,AVLNode<T>> {
    ...
    @Override
    public AVLNode<T> newNode(T value) {
        return new AVLNode<>(value);
    }
}

public class AVLNode<T extends Comparable> extends BstNode<T,AVLNode<T>> {
    ...

    public AVLNode(T value) {
        super(value);
    }

    @Override
    public AVLNode<T> getOnlyChild(AVLNode<T> node) {
        return super.getOnlyChild(node);
    }
    ...
}

Java: 实现树及其节点的并行层次结构

Java: Implementing parallel hierarchy of trees and its nodes

java

tree

binary-tree