The tree abstract data type

Now that we have some idea of the tree, we can define the tree ADT. A tree ADT can be defined in multiple ways. We will check out two. In an imperative setting, that is, when trees are mutable, we can define a tree ADT as having the following operations:

  • Get the root node
  • Given a node, get its children

This is all that is required to have a model for a tree. We may also include some appropriate mutation methods.

The recursive definition for the tree ADT can be as follows:

  • A tree is an ordered pair containing the following:
    • a value
    • a list of other trees, which are meant to be it's subtrees

We can develop a tree implementation in exactly the same way as it is defined in the functional tree ADT:

public class FunctionalTree<E> {
    private E value;
    private LinkedList<FunctionalTree<E>> children;

As defined in the ADT, the tree is an ordered pair of a value and a list of other trees, as follows:

    public FunctionalTree(E value, LinkedList<FunctionalTree<E>> children) {
        this.children = children;
        this.value = value;
    }

    public  LinkedList<FunctionalTree<E>> getChildren() {
        return children;
    }

    public E getValue() {
        return value;
    }

    public void traverseDepthFirst(OneArgumentStatement<E> processor){
        processor.doSomething(value);
        children.forEach((n)-> n.traverseDepthFirst(processor));
    }

}

The implementation is quite simple. The depth-first traversal can be achieved using recursive calls to the children, which are indeed subtrees. A tree without any children needs to have an empty list of children. With this, we can create the functional version of the same tree that we had created for an imperative version:

public static void main(String [] args){
    LinkedList<FunctionalTree<Integer>> emptyList = LinkedList.emptyList();

    FunctionalTree<Integer> t1 = new FunctionalTree<>(5, emptyList);
    FunctionalTree<Integer> t2 = new FunctionalTree<>(9, emptyList);
    FunctionalTree<Integer> t3 = new FunctionalTree<>(6, emptyList);

    FunctionalTree<Integer> t4 = new FunctionalTree<>(2, emptyList);
    FunctionalTree<Integer> t5 = new FunctionalTree<>(5, emptyList.add(t1));
    FunctionalTree<Integer> t6 = new FunctionalTree<>(9, 
         emptyList.add(t3).add(t2));
    FunctionalTree<Integer> t7 = new FunctionalTree<>(6, emptyList);
    FunctionalTree<Integer> t8 = new FunctionalTree<>(2, emptyList);

    FunctionalTree<Integer> t9 = new FunctionalTree<>(5,
         emptyList.add(t6).add(t5).add(t4));
    FunctionalTree<Integer> t10 = new FunctionalTree<>(1,
         emptyList.add(t8).add(t7));

    FunctionalTree<Integer> tree = new FunctionalTree<>(1,
         emptyList.add(t10).add(t9));

At the end, we can do a depth-first traversal to see if it outputs the same tree as before:

    tree.traverseDepthFirst(System.out::print);
}
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset