Title: More Tree Theory
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

More Tree Theory

- Tree structures are great examples where we want to use Recursion.
- From the previous set of notes, we implemented a subset of the functionality in the normal TreeSet. In this set of notes, I want to generalize the notion of Tree datastructures somewhat.
- I have added some specialized routines to our MyTreeSet to illustrate some of the things we may want to do. Although the TreeSet functionality doesn't need any of these routines, some of the other problems that we may want to solve could use this additional functionality.

MyTreeSet.java with updates

import java.util.Iterator;
import java.util.LinkedList;

class Node<T>
{
    T value;
    Node<T> right;
    Node<T> left;
    Node<T> parent;

    Node(T value)
    {
        this.value = value;
        right = left= parent = null;
    }
}

public class MyTreeSet<T extends Comparable<T> > {
    private Node<T> root = null;
    private int treeSize = 0;

    public int size()
    {
        return treeSize;
    }

    public boolean add(T value)
    {
        Node<T> next = root;
        Node<T> parent = null;
        int diff;

        while(next != null)
        {
            parent = next;
            diff = value.compareTo(next.value);
            if (diff == 0) // found match and can't add ... must be unique
                return false;
            else if (diff > 0 )
                next = next.right;
            else
                next = next.left;
        }

        // Couldn't be found ... need to insert it.
        Node<T> newNode = new Node<T>(value);
        treeSize += 1;

        if (parent == null)
            root = newNode; // Must be the first Node
        else
        {
            // Create the parent, left/right links

            newNode.parent = parent;
            diff = value.compareTo(parent.value);
            if (diff > 0)
                parent.right = newNode;
            else
                parent.left = newNode;
        }

        return true;
    }

    public boolean contains(T value)
    {
        Node<T> next = root;
        int diff;

        while(next != null)
        {
            diff = value.compareTo(next.value);
            if (diff == 0) // found match
                return true;
            else if (diff > 0 )
                next = next.right;
            else
                next = next.left;
        }
        return false;
    }

    public Iterator<T> iterator()
    {
        return new MyIterator();
    }

    /******* Inner class Iterator *****/
    class MyIterator implements Iterator<T>
    {
        private Node<T> nextNode = null;

        MyIterator()
        {
            // Get the first node in the list
            nextNode = root;
            if (nextNode != null)
                goDownLeftLinks();
        }

        private void goDownLeftLinks()
        {
            while (nextNode.left != null)
                nextNode = nextNode.left;
        }
        private void moveToNext()
        {
            if (nextNode == null) return; // must be done
            if (nextNode.right != null)
            {
                // Need to follow the tree on the right
                nextNode = nextNode.right;
                goDownLeftLinks();
            }
            else
            {
                // We have already processed the left subtree, and there is no right tree.
                // We want to move up to find a parent where our nextNode is the left child
                // of the parent.  Note that nextNode has to be either a left or a right child.
                // So we keep climbing as long as nextNode is a right child.
                Node<T> parent = nextNode.parent;
                while (parent != null && nextNode == parent.right)
                {
                    nextNode = parent;
                    parent = nextNode.parent;
                }
                // if nextNode is null, then we are done.
                nextNode = parent;
            }
        }


        @Override
        public boolean hasNext() {
            if (nextNode== null)
                return false;
            return true;
        }

        @Override
        public T next() {
            T value = nextNode.value;
            moveToNext();
            return value;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Iterator.remove not implemented");

        }

    }
    // ******************  End of Inner class for Iterator
    public void inorder()
    {
        inorder(root);
    }
    private void inorder(Node<T> visit)
    {
        if (visit != null)
        {
            // Visit Left tree first, then node, then right tree
            inorder(visit.left);
            System.out.println(visit.value+ " ");
            inorder(visit.right);
        }
    }

    public void postorder()
    {
        postorder(root);
    }
    private void postorder(Node<T>  visit)
    {
        if (visit != null)
        {
            // Visit left tree, right tree and then the node itself
            postorder(visit.left);
            postorder(visit.right);
            System.out.println(visit.value+ " ");
        }
    }


    public void levelorder()
    {
        LinkedList< Node<T> > linkedList = new LinkedList< Node<T> >();
        linkedList.addLast(root);

        while( ! linkedList.isEmpty())
        {
            Node<T> node = linkedList.removeFirst();
            System.out.println(node.value + " ");
            if (node.left != null)
                linkedList.addLast(node.left);
            if (node.right != null)
                linkedList.addLast(node.right);
        }
    }

    public int depth()
    {
        return depth(root);
    }
    private int depth(Node<T> visit)
    {
        if ( visit == null)
            return 0;

        int leftDepth = depth(visit.left);
        int rightDepth = depth( visit.right);

        if (rightDepth > leftDepth)
            return 1 + rightDepth;  // includes current node
        else
            return 1 + leftDepth;   // includes current node

    }
}



DemoMyTreeSet2.java


import java.util.Iterator;

public class DemoMyTreeSet2 {

    public static void main(String[] args) {
        MyTreeSet<String> myTree = new MyTreeSet<String>();

        String[] arr = {"bee", "amazon", "omega", "abe", "ambition","epsilon", "zeta",
                "aardvark", "alpha", "amber", "ambivalence", "ben", "gamma", "pi"};

        for (int i=0; i < arr.length; i++)
            myTree.add(arr[i]);


        System.out.println("****************** Using the iterator");
        Iterator<String> iter = myTree.iterator();
        while (iter.hasNext())
        {
            System.out.println("Iter: " + iter.next());
        }

        System.out.println("****************** inorder");
        myTree.inorder();

        System.out.println("****************** postorder");
        myTree.postorder();

        System.out.println("****************** levelorder");
        myTree.levelorder();

        System.out.println("****************** Tree depth = " + myTree.depth());



    }

}




- Note that the inorder listing effectively dumps the tree the same way that our iterator dumps the tree.
- Notice that the inorder routine would not have needed the parent link. However, the iterator does need the parent link to provide the required functionality.
- To illustrate why we might want the PostOrder operation, I want to illustrate a technique some compilers use for evaluating expressions. Some compilers will evaluate expressions, by parsing the user's expressions into a tree structure. To get the proper value, we us PostOrder logic to generate the answer. See the example below:

PostOrderEvaluation.java




import java.util.Iterator;

class NodeEval
{
    String value;
    NodeEval right;
    NodeEval left;

    NodeEval(String value, NodeEval left, NodeEval right)
    {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}
public class PostOrderEvaluation {

    static double postorderEvaluation(NodeEval  visit)
    {
        if (visit != null)
        {
            // Visit left tree, right tree and then the node itself
            double leftValue = postorderEvaluation(visit.left);
            double rightValue =postorderEvaluation(visit.right);

            // Now ready to evaluate the Node itself

            double answer;
            if ("+".equals(visit.value))
                answer = leftValue + rightValue;
            else if ("-".equals(visit.value))
                answer =  leftValue - rightValue;
            else if ("*".equals(visit.value))
                answer = leftValue * rightValue;
            else if ("/".equals(visit.value))
                answer = leftValue/rightValue;
            else
            {
                // Should be a number
                answer = Double.valueOf(visit.value.toString());
            }
            System.out.println("postorderEvaluation evaluation: value="+ visit.value +
                    " left="+leftValue + " right="+rightValue + " answer="+answer);
            return answer;
        }
        else
            return 0.0; // Shouldn't happen
    }

    public static void main(String[] args) {

        NodeEval n1, n2, p1, p2, pLeft, pRight, root;

        // See the Figure to see what we are building with a manual approach

        n1 = new NodeEval("5", null, null);
        n2 = new NodeEval("6", null, null);
        p1  = new NodeEval("+", n1, n2);

        n1 = new NodeEval("1", null, null);
        n2 = new NodeEval("2", null, null);
        p2  = new NodeEval("+", n1, n2);

        p1 = new NodeEval("*", p1, p2);

        n1 = new NodeEval("2", null, null);
        n2 = new NodeEval("6", null, null);
        p2 = new NodeEval("*", n1, n2);

        pLeft = new NodeEval("+", p1, p2);

        n1 = new NodeEval("5", null, null);
        n2 = new NodeEval("10", null, null);
        p1 = new NodeEval("+", n1, n2);

        n1 = new NodeEval("7", null, null);
        n2 = new NodeEval("1", null, null);
        p2 = new NodeEval("+", n1, n2);

        pRight = new NodeEval("*", p1, p2);
        root = new NodeEval("/", pLeft, pRight);

        double value = postorderEvaluation(root);

        System.out.println("Final value =" + value);

    }

}


Generalized Tree Data Structures

- Sometimes we need trees that are more flexible than binary trees to represent more complicated relations. Human beings are real good at creating complicated relationships.
- The following is a subset of some Family Tree information. We want to represent this data in such a way that we can discover the relationships hidden in this data.
- I have sketched a data structure. I haven't provided code here but I have worked through this problem before and uncovering the relationships is a fun, challenging task.

Family Tree Data Structure

FamilyTree.java


import java.util.ArrayList;
import java.util.LinkedList;

class FNode<T>
{
    T value;
    FNode<T> father, mother;
    LinkedList< FNode<T> > children = new LinkedList< FNode<T> >();

    FNode (T value, FNode<T> father, FNode<T> mother)
    {
        this.value = value;
        this.father = father;
        this.mother= mother;

        if (father != null)
            father.children.add(this);
        if (mother != null)
            mother.children.add(this);
    }
}

public class FamilyTree<T> {

    // For Nodes that don't have any parents
    private LinkedList<FNode<T> > noParents = new LinkedList<FNode<T> >();

    public boolean add(T child, T father, T mother)
    {
        // TBD
        return true;
    }


    public int getNumGenerations(T startingPerson)
    {
        // startingPerson == null, then get max generations that exist
        // TBD
        return 0;
    }

    ArrayList<T> getGeneration(int generation, T startingPerson)
    {
        // if generation <=  0, then get all generations
        // startingPerson == null, then get max generations that exist
        // TBD
        return null;
    }


    public int getNumAncestorGenerations(T startingPerson)
    {
        // startingPerson == null, then get max generations that exist
        // TBD
        return 0;
    }

    ArrayList<T> getAncestors(int generation, T startingPerson)
    {
        // if generation <  0, then get all generations
        // TBD
        return null;
    }

    ArrayList<String> getRelationships(T person1, T person2)
    {
        // TBD
        return null;
    }

}



Last Updated: July 28, 2014 11:43 AM