Tree traversal

http://en.wikipedia.org/wiki/Tree_traversal
http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search

Tree traversal in various languages
http://rosettacode.org/wiki/Tree_traversal#Java

Algorithms
http://algs4.cs.princeton.edu/home/
Graphs
http://algs4.cs.princeton.edu/40graphs/
Directed Graphs

http://algs4.cs.princeton.edu/42directed/

Java Data Structure: A Generic Tree

http://sujitpal.blogspot.com/2006/05/java-data-structure-generic-tree.html

Generic Node

public class Node<T> {
 
    public T data;
    public List<Node<T>> children;
    public List<Node<T>> parents;

Non-generic node

package dave;

/**
 * Non-generic subclass of Node<String>
 */
public class DaveNode extends Node<String> {
    public DaveNode() {
        super();
    }
}

Walk using stack

 /**
   *   
   * @param element
   * @return set of all nodes
   */
  public List<Node<T>> walk(Node<T> element){
      
      List<Node<T>> out = new ArrayList<Node<T>>();
      
      Queue<Node<T>> q = new LinkedList<Node<T>>();
      q.add(element);
      
      while(!q.isEmpty()){
          Node<T> x = q.poll();
          out.add(x);
          
          for(Node<T> child : x.getChildren()){
              q.add(child);
          }
      }
      
      return out;
      
  }

Walk from bottom up

  /**
   *   
   * @param element
   * @return set of all upper nodes
   */
  public Collection<Node<T>> pathBottomUp(Node<T> element){
      
      Set<Node<T>> out = new LinkedHashSet<Node<T>>();
      
      Queue<Node<T>> q = new LinkedList<Node<T>>();
      q.add(element);
      
      while(!q.isEmpty()){
          Node<T> x = q.poll();
          out.add(x);
          
          for(Node<T> parent : x.getParents()){
              q.add(parent);
          }
      }
      
      return out;
      
  }

Construct tree

package dave;


public class WalkTree {

    public static void main(String[] args) {
        
        DaveTree daveTree = new DaveTree();
        
        DaveNode daveNode = getDaveNode("1");
        
        DaveNode daveNode11 = getDaveNode("1.1");
        DaveNode daveNode12 = getDaveNode("1.2");
        DaveNode daveNode13 = getDaveNode("1.3");
        
        DaveNode daveNode131 = getDaveNode("1.3.1");
        DaveNode daveNode132 = getDaveNode("1.3.2");
        
        daveNode.addChild(daveNode11);
        daveNode.addChild(daveNode12);
        daveNode.addChild(daveNode13);
        
        daveNode12.addChild(daveNode131);
        
        daveNode13.addChild(daveNode131);
        daveNode13.addChild(daveNode132);
        
                
        daveTree.setRootElement(daveNode);
        
        System.out.println(daveTree.toList());
                
        Node<String> root = daveTree.getRootElement();
        
        System.out.println("walk:" + daveTree.walk(root));
        
        System.out.println("pathBottomUp:" +daveTree.pathBottomUp(daveNode131));

    }
    
    private static DaveNode getDaveNode(String profileName){
        
        DaveNode daveNode = new DaveNode();
        
        daveNode.setData(profileName);
        
        return daveNode;
        
    }

}

Program output

[{1,[1.1,1.2,1.3]}, {1.1,[]}, {1.2,[1.3.1]}, {1.3.1,[]}, {1.3,[1.3.1,1.3.2]}, {1.3.1,[]}, {1.3.2,[]}]
walk:[{1,[1.1,1.2,1.3]}, {1.1,[]}, {1.2,[1.3.1]}, {1.3,[1.3.1,1.3.2]}, {1.3.1,[]}, {1.3.1,[]}, {1.3.2,[]}]
pathBottomUp:[{1.3.1,[]}, {1.2,[1.3.1]}, {1.3,[1.3.1,1.3.2]}, {1,[1.1,1.2,1.3]}]