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

Question

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

问题是如何处理这样一个事实，例如Bst.findNode()将返回BstNode，但在Avl中，我需要AvlNode，尽管findNode(。

我需要帮助规划层次结构，或者如果这些并行层次结构(作为一种代码气味)通常是个坏主意，我需要一个变通方法，因为我不知道如何以正确的方式进行。

BstTree类：

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类：

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类中获得一些方法，但这不是一个大问题。

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);
}
...
}