Java Array of Generic Nodes in a Binary Tree, can't create nil node

Question

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?

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<T> rather than the raw type Node. — Ted Hopp
– Ted Hopp, Commented Jul 3, 2019 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
– Hovercraft Full Of Eels, Commented Jul 3, 2019 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
– wames, Commented Jul 3, 2019 at 23:38
@HovercraftFullOfEels Because nil is referenced from a static context (in the static nested Node constructor). — Andreas
– Andreas, Commented Jul 3, 2019 at 23:39
@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? 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, is a different story. — Andreas
– Andreas, Commented Jul 3, 2019 at 23:43

Andreas · Accepted Answer · 2019-07-03 23:49:05Z

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

edited Jul 3, 2019 at 23:49

answered Jul 3, 2019 at 23:37

Andreas

160k13 gold badges164 silver badges262 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

wames Over a year ago

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 Over a year ago

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?

Collectives™ on Stack Overflow

Java Array of Generic Nodes in a Binary Tree, can't create nil node

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related