Tree

A tree is a specific type of graph having a root node and branches with (ultimately) leaf nodes. Can also be described as a linked list with nodes having multiple successors. Another (more abstract) definition could be a set containing sets (as there are no cycles). A tree can also be refered to as a hiearchy.

Examples

• Family Tree
• File Hiearchy
• HTML DOM Tree
• AST (compilers)
• JSON
• Text Processing
• DB Engines (B-TREE)
• BS-TREE
• AVL Trees
• Kd-Trees (graphics)
• Prefix-Trees

java.til.TreeSet java.util.TreeMap java.util.PriorityQueue

Terms

• Ancestor
• Decendant(s)
• Degree
• Siblings
• Depth

Algorithmic Tree Traversals

• Breadth-first traversal (level by level)
• Depth-first traversal (branch by branch)
  • Pre-Order (LISP)
  • Post-Order
  • Infix Order