How to make a tree with multiple Object types in Java?

Question

I am trying to use a tree structure in Java, but I need it to hold different types in its data field. The format of my question is very similar to this this question, but I couldn't find an answer to my problem based on the answers to that question.

The following is my simple TreeNode class. I have only included the skeleton of my code.

public class TreeNode<Character> {
    public Character data;
    public TreeNode<Character> parent;
    public TreeNode<Character> leftChild;
    public TreeNode<Character> rightChild;

    // basic methods, code omitted for simplicity
    public TreeNode(Character data) {...}
    public TreeNode<Character> addLeftChild(Character data) {...}
    public TreeNode<Character> addRightChild(Character data) {...}
}

I have another custom class public class NFA, and I would like to be able to store data in my tree in the following fashion:

    root
  /      \
NFA     Character
       /        \
    Character   Character

and so on...

What can I change in the class to make it so the tree supports Character and NFA? Should I use public class TreeNode<Object> and then somehow cast Object as Character or NFA in every method?

I have seen other examples using an Iterator, but I after reading the Java docs I am still unsure of how to implement this.

For reference, here is a skeleton of NFA. Character is the generic java.lang.Character class.

public class NFA {
    public int numStates;
    public ArrayList<Character> alphabet;
    public ArrayList<Transition> transitionFunction;
    public int startState;
    public ArrayList<Integer> endStates;

    // constructors
}

This person did so: http://stackoverflow.com/questions/43905036/why-cant-i-write-my-binary-tree-inside-a-file — Glen Pierce, May 13 '17 at 01:38
@GlenPierce that technically works, and thank you for the solution, but is there a cleaner way then adding a second data field (one for Character and one for NFA)? If I do that then the tree will take up more memory and have a lot of mostly unused bits. — wcarhart, May 13 '17 at 01:41

score 3 · Accepted Answer · answered May 13 '17 at 01:44

3

I think it is better to create different types of nodes that implement TreeNode object

Example:

public class NFANode implements TreeNode {

}

public class charNode implements TreeNode {

}

And your tree has a relation to TreeNode only.

answered May 13 '17 at 01:44

ahmed eshra

79
3

I think this will work better than my solution, UNTIL you need to access certain class-specific features of the nodes, but you might be able to recast them to their original class should that be the case (assuming you can reliably determine which node is which class at runtime). – Glen Pierce May 13 '17 at 01:56
1

Now that I think about it, my solution has a similar flaw. Having one tree with multiple data types is hard. – Glen Pierce May 13 '17 at 01:59

score 0 · Answer 2 · answered May 13 '17 at 01:47

0

Use of generics could solve this problem for you like so:

public class TreeNode<T Extends ClassThatIsACharacterAndAnNFA> {
    public T data;
    public TreeNode<T> parent;
    public TreeNode<T> leftChild;
    public TreeNode<T> rightChild;

    // basic methods, code omitted for simplicity
    public TreeNode(T data) {...}
    public TreeNode<T> addLeftChild(T data) {...}
    public TreeNode<T> addRightChild(T data) {...}
}

This obviously assumes that NFA and Character Extend from the same class, in this case: ClassThatIsACharacterAndAnNFA.

answered May 13 '17 at 01:47

Glen Pierce

4,401
5
31
50

Unfortunately, Character and NFA do not extend from the same class – wcarhart May 13 '17 at 01:49
Are you severely resource constrained or something? Are these classes huge memory hogs? Is this Tree gigantic? You seem unusually concerned about the memory footprint of this class. – Glen Pierce May 13 '17 at 01:51
I don't believe I'm necessarily unusually concerned about memory. It's just that every node will only have 1 `NFA` _or_ 1 `Character`. Why would I have a solution that requires every single node to contain both data types, when I will only ever be using one for each node? – wcarhart May 13 '17 at 01:56
1

Upon careful consideration, go with the Interface option from @ahmed eshra. I think it will solve your problem in the way you are seeking. You'll have to implement each method from the Interface in each class, but you'll achieve the goal of reduced footprint that you're seeking. I encourage you to accept that answer. – Glen Pierce May 13 '17 at 02:03
1

I appreciate the help, you can have my +1 kind sir – wcarhart May 13 '17 at 02:04

How to make a tree with multiple Object types in Java?

2 Answers2