Trees!

First, the mathematical definition of a Tree. A Graph is any set of vertices and a set of edges that connect vertices. A cycle is a path in a graph such that you can arrive back at a vertex without re-using any edges. A connected graph, is a graph where a path exists between all possible pairs of vertices. Finally, any connected graph that has no cycles is a Tree.

Well, that's not very interesting. Here's an example.

This is known as a decision tree. You see that a single node is at the top ("Does it move?"). This is the root. The root has two branches, to "No, should it?" and "Yes, should it?" Each of nodes also has two branches, one to "No/Yes, No problem," and the other to "No/Yes, WD-40/Duct Tape."

Some definitions:

  1. Node: An element of the tree.
  2. Root: The single element at the top of the tree.
  3. Parent: The node A directly above a node B is B's parent. Nodes each have only one parent.
  4. Child: If A is B's parent, then B is A's child.
  5. Sibling: Two nodes are siblings if they have the same parent.
  6. Ancestor: Parent, or parent's parent, or...
  7. External Node: A node with no children.
  8. Leaf: Same as an External Node.
  9. Internal Node: A node with at least one child.
  10. Subtree: A portion of a tree that is, itself, a tree.
  11. Depth: The depth of a node is the number of edges that have to be traversed to encounter the root.
  12. Height: The height of a tree is the maximum depth of a node in the tree. An empty tree (where the root is null) has a height of -1.
  13. Branching Factor: Maximum allowed number of children for a node in a tree.

So what does this look like in Java? We'll write this for a binary tree, or a tree where each node has up to two children, with some methods that might be useful.

public class Tree {
  private class Node {
    private Node parent, left, right;
    private Object data;

    public Node(Object data) {
      this.data=data;
      parent = left = right = null;
    }

    //Assorted setters and getters

    public int depth() {
      return depth(this);
    }
    private int depth(Node n) {
      if (n==null)
        return -1;
      return 1 + depth(n.getParent());
    }
  }

  private Node root;

  //Constructors, some other methods

  public int height() {
    return height(root);
  }
  private int height(Node n) {
    if (n==null)
      return -1;
    int l = height(n.getLeft());
    int r = height(n.getRight());
    if (l > r)
      return 1+l;
    return 1+r;
  }
}