0

I'm having a similar problem as in this question: Array of generic nodes Java

However, making the nested Node class static solves the one problem but creates another for me. I've written a Binary Tree, and each time a Node's pointer isn't supposed to point to anything (e.g. a leaf node's left and right pointers, or the root's parent pointer), it actually points to a special "nil" node, which contains no relevant data. Nil is a member variable of the Binary Tree.

When I create a node, the constructor makes all pointers point to nil. However, if I make the Node class static so I can create an array of nodes (which I need to do for a particular method), I get an error for each pointer that says "Cannot make a static reference to the non-static field nil." But if I change nil to be static, I get an error for it which says "Cannot make a static reference to the non-static type T." (My nodes hold parameterized type objects.)

Here's my Node class:

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

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

This is the nil designation and the Binary Tree constructor, which creates the nil node and makes it the root:

protected static Node<T> nil;

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

How do I allow myself to create an array of nodes without running into these static vs non-static issues?

wames
  • 11
  • 2
  • 2
    Is there any reason you aren't simply using `null` when a pointer isn't supposed to point to anything? Also, the `left`, `right` and `parent` fields should probably be of type `Node` rather than the raw type `Node`. – Ted Hopp Jul 03 '19 at 23:35
  • Why is the nil *field* static? Yes, the class may need to be static, but that does not mean that the field `nil` does too. – Hovercraft Full Of Eels Jul 03 '19 at 23:36
  • I'm following a textbook in an online course (Open Data Structures by Pat Morin). Sometimes this guy has some really convoluted code, so it wouldn't surprise me if the nil node is unnecessary. – wames Jul 03 '19 at 23:38
  • @HovercraftFullOfEels Because `nil` is referenced from a static context (in the static nested `Node` constructor). – Andreas Jul 03 '19 at 23:39
  • @Andreas: then that is some crazy code – Hovercraft Full Of Eels Jul 03 '19 at 23:39
  • 1
    @HovercraftFullOfEels I agree, but if you want to write code without using `null` values, then that's how. See e.g. [Are null references really a bad thing?](https://softwareengineering.stackexchange.com/q/12777/202153) I personally disagree. Replacing `null` with `nil` doesn't really make the code less error-prone when only used inside the implementation of class. Eliminating `null` from the API, by e.g. using [`Optional`](https://docs.oracle.com/javase/8/docs/api/java/util/Optional.html), is a different story. – Andreas Jul 03 '19 at 23:43

1 Answers1

2

First, never use raw generics, so specify <T> on the Node fields:

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

Next, to initialize nil, you need a difference constructor:

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

Now you can initialize nil as a non-static object, to keep type-safety:

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

Though, rather than creating a nil object for every tree, create a static method:

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

@SuppressWarnings({ "cast", "unchecked" })
protected static <T> Node<T> nil() {
    return (Node<T>) NIL;
}
Andreas
  • 154,647
  • 11
  • 152
  • 247
  • Yeah, I noticed my mistake with the raw generics. I had been adding and deleting so much to try to make things work, I missed it when I posted here. – wames Jul 04 '19 at 00:03
  • This works for creating the nil node, but when using the other constructor to create the other nodes, I still can't point to the nil node for the reasons stated above. Your suggestion is to point them to themselves, but then I have to change my implementation in all my methods to fix the pointers after I create a new node. Is this what I need to do? Will this even work if I point to the nil node after the new node has been constructed? – wames Jul 04 '19 at 17:10