Java 二叉树中通用节点数组，无法创建 nil 节点

Question

我遇到了与此问题类似的问题: Array of generic nodes Java

但是，使嵌套 Node 类静态化解决了一个问题，但给我带来了另一个问题。我写了一个二叉树，每次节点的指针不应该指向任何东西(例如叶节点的左指针和右指针，或根的父指针)，它实际上指向一个特殊的“nil”节点，其中不包含相关数据。 Nil 是二叉树的成员变量。

当我创建一个节点时，构造函数使所有指针都指向 nil。但是，如果我将 Node 类设置为静态，以便我可以创建一个节点数组(我需要为特定方法执行此操作)，则每个指针都会出现错误，提示“无法对非静态字段进行静态引用”零。”但是，如果我将 nil 更改为静态，则会收到错误消息“无法对非静态类型 T 进行静态引用”。 (我的节点保存参数化类型对象。)

这是我的 Node 类:

protected static class Node<T>{
    Node left, right, parent;
    T object;

    protected Node(T x) {
        object= x;
        left= nil;
        right= nil;
        parent= nil;
    }
}

这是 nil 指定和二叉树构造函数，它创建 nil 节点并使其成为根:

protected static Node<T> nil;

public BT() {
    nil= new Node<T>(null);
    root= nil;
}

如何允许自己创建节点数组而不遇到这些静态与非静态问题？

Answer 1

首先，切勿使用原始泛型，因此请指定 <T>关于Node字段:

protected static class Node<T> {
    Node<T> left, right, parent;
    T object;

下一步，初始化nil ，你需要一个不同的构造函数:

protected Node() {
    left = this;
    right = this;
    parent = this;
}

现在您可以初始化 nil作为非静态对象，以保持类型安全:

protected Node<T> nil = new Node<>();

不过，而不是创建 nil为每棵树创建一个静态方法:

@SuppressWarnings("rawtypes")
private static Node NIL = new Node();

@SuppressWarnings({ "cast", "unchecked" })
protected static <T> Node<T> nil() {
    return (Node<T>) NIL;
}