// Tree.java
// This implements a basic generic tree, with labels of type T,
// pointer to the parent node, and a singly linked list of children nodes.
// It provides iterators that loop over children, that loop up to the root,
// and that traverse the tree in prefix and postfix order.
//

class Tree<T>  {
    private T label;
    private Tree<T> parent;
    private Tree<T> nextSibling; // next node on the list of parents's 
                                 //  children
    private Tree<T> firstChild;  // first in the linked list of children

                                 
//  Getters and setters
    public T getLabel() { return label; }  
    public void setLabel(T v) { label = v; }
    public Tree<T> getParent() { return parent;}
    public Tree<T> getNextSibling() { return nextSibling;}
    public Tree<T> getFirstChild() { return firstChild;}
    public Tree<T> getSelf() { return this; }

// Add C to the front of the children of this
    public void addChild(Tree<T> c) {
         c.parent = this;
         if (firstChild == null) 
           firstChild = c;
         else {
             c.nextSibling = firstChild;
             firstChild = c;
            }
    }

// Check if the node is a leaf
    public boolean Leaf() { return firstChild==null; }

public Tree<T> nextPreorder() {
        if (getFirstChild() != null)
            return getFirstChild();
        else {
           Tree<T> a=this;
           while (a.getNextSibling() == null && a.getParent() != null)
               a=a.getParent();
           return a.getNextSibling();
          }
     }
}