Java - Polymorphism and object class design

Question

I'm trying to practice generics and polymorphism. I have a Node class as follows:

public class Node<T> {
    public T name;
    public Node[] children;
}

Then a generic Tree class:

public class Tree<T> {
    public Node<T> root;
}

Now, I'm trying to implement a binary tree. A binary tree is a tree, thus satisfying is a rule of polymorphism. I'm struggling with how to enforce that nodes in binary trees can have a maximum of two children.

Should I extend node class to Binary node and children array is always initialized to size 2? If BinaryTree extends Tree, how do I place the restriction on the children member variable?

It's like I am trying to make:

BinryTree extends Tree
BinaryTreeNode extends Node

Where Node is a member variable in Tree and BinaryTreeNode is a member variable in BinaryTree. What would be a proper design?

Give it a field for each of the "left" and "right" children. Aside from anything, this would avoid the issue of a raw-typed array. — Andy Turner
– Andy Turner, Commented Apr 13, 2020 at 16:01
I was thinking to have left to return children[0] and right to return children[1]. Trying to see if I can maintain some type of class-hierarchy. — rohan
– rohan, Commented Apr 13, 2020 at 16:05
Your BinaryTree may extend Tree but it doesn't need to instantiate Node instances. Consider creating a custom BinaryTreeNode that extends Node. The BinaryTreeNode will handle limiting itself to two children. Note that BinaryTreeNode may need to override some behavior of its parent to limit access to the internal array. — vsfDawg
– vsfDawg, Commented Apr 13, 2020 at 16:23

Uri Loya · Accepted Answer · 2020-04-13 16:39:02Z

2

What about:

public class Node<T> {
public T name;
public Node[] children;
public Node(int numOfChildren) { children = new Node[numOfChildren]; }
}

If you would like the node to hold 2 nodes call the constructor with 2, That way children will hold up to 2 nodes. Also it would be better to use encapsulation and make children private and provide accessibility with getters and setters:

public class Node<T> {
public T name;
private Node[] children;

public Node(int numOfChildren) { children = new Node[numOfChildren]; }

public Node[] getChildren() { return children; }
}

edited Apr 13, 2020 at 16:39

answered Apr 13, 2020 at 16:05

Uri Loya

1,4312 gold badges21 silver badges40 bronze badges

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

3 Comments

rohan Over a year ago

Tree class is also using Node and hoping to be more generic and be able to create Trees other than BinaryTree as well.

rohan Over a year ago

I was thinking around the same lines; however, this doesn't restrict BinaryTree to have a node with more than 2 children nodes.

Martijn Van Loocke Over a year ago

The concept here is right. I would create an abstract class Node and Tree with protected constructors that accept the number of children as parameter. Then have implementations of those classes BinaryTree and BinaryNode.

rohan · Accepted Answer · 2020-04-13 19:34:10Z

Here is what I ended up with from the above suggestions. Node class:

public abstract class Node<T> {
    protected T value;
    protected Node[] children;
}

BinaryTreeNode

public class BinaryTreeNode<T> extends Node {
    public BinaryTreeNode() {
        children = new BinaryTreeNode[2];
    }

    public BinaryTreeNode(T value) {
        this.value = value;
        children = new BinaryTreeNode[2];
    }

    public void setValue(T value) {
        this.value = value;
    }

    public T getValue() {
        return (T)value;
    }

    public BinaryTreeNode left() {
        return (BinaryTreeNode)children[0];
    }

    public BinaryTreeNode right() {
        return (BinaryTreeNode) children[1];
    }

    public void setLeft(BinaryTreeNode<T> leftNode) {
        children[0] = leftNode;
    }

    public void setRight(BinaryTreeNode<T> rightNode) {
        children[1] = rightNode;
    }
}

Tree Class:

public abstract class Tree<T> {
    public Node<T> root;
}

BinaryTree:

public class BinaryTree<T> extends Tree<T> {

    public BinaryTree() {
        root = new BinaryTreeNode<>();
    }

    public void visit(Node node) {
        System.out.println(node.value);
    }

    public void inOrderTraversal(BinaryTreeNode node) {
        if(node != null) {
            inOrderTraversal(node.left());
            visit(node);
            inOrderTraversal(node.right());
        }
    }
}

I apologize for lengthy comment. Thankful for any feedback on improving design.

Collectives™ on Stack Overflow

Java - Polymorphism and object class design

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related