java - Object oriented design, designing a tree

Question

I'm creating a (atypical)tree in Java that will be composed of three classes: node, branch and leaf

Each node stores the branches it is connected to in a HashSet. The branch is supposed to lead to a descendent node or a leaf, but I'm not sure how to code that. Would I just have two separate variables, one Node and one Leaf in the branch class, along with two sets of getters and setters, even though I will never use both? Is there a best practice in this regard?

I was thinking maybe make node and leaf subclasses of the same superclass, but they have absolutely nothing in common in terms of code(i.e. different variable types, functions, etc.).

EDIT: Node references branches and each Branch references a Node or a Leaf

Answer 1

Make the Leaf class with the basic information.

Make the Branch class which holds references to Leafs.

Make the Node class which holds references to Brahces.

Then try look up Recursion and how to use it to make such constructs :)

Here is my go at it. Though not very elegant, it gets the job done.

Here is the Leaf class:

public class Leaf {
    private String text;

    public Leaf(String text) {
        this.text = text;
    }

    public String getText() {
        return text;
    }

    public void setString(String newString) {
        text = newString;
    }

    @Override
    public String toString() {
        return text;
    }
}

And here is the Branch class:

public class Branch<T> {
    private String text;
    private HashSet<T> list;

    public Branch(String text) {
        this.text = text;
        list = new HashSet<>();
    }

    public String getText() {
        return text;
    }

    public void setText(String newText) {
        text = newText;
    }

    public HashSet<T> getHashSet() {
        return list;
    }

    public void setHashSet(HashSet<T> newList) {
        list = newList;
    }

    public String getAllLeaves() {
        StringBuilder sb = new StringBuilder();
        sb.append(text).append("\n");
        for(T t : list) {
            sb.append("\t\t");
            sb.append(t.toString()).append("\n");
        }
        return sb.toString();
    }

    @Override
    public String toString() {
        return text;
    }
}

Lastly the Node class:

public class Node<T> {
    private String text;
    private HashSet<T> list;

    public Node(String text) {
        this.text = text;
        list = new HashSet<>();
    }

    public String getText() {
        return text;
    }

    public void setText(String newText) {
        text = newText;
    }

    public HashSet<T> getHashSet() {
        return list;
    }

    public void setHashSet(HashSet<T> newList) {
        list = newList;
    }
}

Little test program to try it out:

public class TreeConstruct {
    public static void main(String[] args) {
        Leaf l1 = new Leaf("Leaf 1");
        Leaf l2 = new Leaf("Leaf 2");
        Leaf l3 = new Leaf("Leaf 3");
        Leaf l4 = new Leaf("Leaf 4");

        Branch<Leaf> b1 = new Branch("Branch 1");
        Branch<Leaf> b2 = new Branch("Branch 2");

        Node<Branch> n1 = new Node("Node 1");

        b1.getHashSet().add(l1);
        b1.getHashSet().add(l2);
        b1.getHashSet().add(l3);
        b2.getHashSet().add(l4);

        n1.getHashSet().add(b1);
        n1.getHashSet().add(b2);

        System.out.println(printNodeTree(n1));
    }

    public static String printNodeTree(Node<Branch> n) {
            StringBuilder sb = new StringBuilder();
            sb.append(n.getText()).append("\n");
            for(Branch b : n.getHashSet()) {
                sb.append("\t");
                sb.append(b.getAllLeaves());
            }
            return sb.toString();
        }
}

The output will be:

Node 1
        Branch 1
                Leaf 1
                Leaf 3
                Leaf 2
        Branch 2
                Leaf 4

Hope this helps!

Answer 2

I'd probably go with something like this:

  interface BranchDestination {
    boolean isLeaf();
  }

  class Node implements BranchDestination {
    private Set branches;
    public boolean isLeaf() {
      return false;
    }
    ...
  }

  class Leaf implements BranchDestination {
    public boolean isLeaf() {
      return true;
    }
    ...
  }

  class Branch {
    BranchDestination destination;
    ...
  }

Answer 3

I do like the idea of defining an interface for the leaf / node classes, and implement that interface in each. I would define a simple function in that interface (syntax might be wrong below, but it's pseduo-ish code):

interface BranchItem {
    public object[] GetVals();
}

public class Branch
{
   public BranchItem item;
}

public class Leaf implements BranchItem
{
    private object myVal = <your data here>;

    public object[] GetVals() {
      return new object[] { myVal };
    }
}

public class Node implements BranchItem
{
    private myBranches[] = <List of Branches>;

    public object[] GetVals() {

      object[] myArray = new object[];
      foreach (BranchItem b in myBranches)
      {
         myArray.addTo(b.item.GetVals());
      }

      return myArray;
    }
}

When traversing your node, simply iterate over the Branches and call GetVals().

The Leaf class will simply returns it's stored value.

The Node Class will recursively loop over it's branches, calling GetVals() on each and add it to it's own returned array.

This is but a simple implementation. If you want sort order, handle collisions or duplicate data, or anything of that nature it could get more complicated.