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. Any 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.

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 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 0;
    return 1 + depth(n.getParent());
  }

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