java - Java:实现树及其节点的并行层次结构
问题描述
为了练习数据结构,我正在实现自己的树库。我从 BST 开始,接下来我将要实现 AVL 树、红黑树,也许还有更多。AVL 和 RBT 也是 BST 树,因此一些类层次结构相当明显。我遇到的问题是所有这些树都有其他类型的节点——AvlNode 有平衡因子标志,RgbNode 有颜色标志,BstNode 不需要任何额外的信息(尽管所有节点都需要对父、子和值的引用) . 所以我有一个节点层次结构和一个树层次结构。我可以给 BstNode 一些标志属性并在扩展类中使用它,但这肯定不是一个好方法。
问题是如何处理例如 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 类的方法,但这不是什么大问题。
解决方案
我会做这样的事情:
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);
}
...
}
推荐阅读
- codenameone - 带有约束 Numeric 的 TextInput 使应用程序崩溃 - cn1
- abap - 数据库视图的连接条件中列的子字符串
- plesk-onyx - 在 plesk onyx 上将别名升级为主域
- javascript - 如何延迟我的 javascript 代码,直到加载 JSON 文件?
- angular - 如何在角度材料中使用输入类型文件
- javascript - Angular - 为什么单击复选框会触发更改事件绑定到的父选择器的更改事件?
- sql - 如果仅在结果的一列上应用
- python - 读取和删除行格式文本文件 Python
- php - PHP MySQL 数据组
- java - 使用条件更新 Firebase 中的字段