These lecture notes are based on chapter 9 in ``Data Structures, Algorithms, & Software Principles in C'' by Thomas Standish.

Trees

Tree terminology comes from

• family tree - parent, child, ancestors, descendants
• geometry - left, right, top, bottom
• biology - roots, leaves, branches
• computer science/math (graph theory) - edge, node, levels, path, internal nodes

Some basic definitions

• root - node with no parent, only one root in a tree
• leaves - nodes with no children
• level - the path length or distance from root to node is the level of the node
• within the tree
• depth (height) - largest distance from root to a leaf
• branching factor - maximum number of children at any node, e.g., branching factor of 2 means a binary tree
• breadth - number of nodes at a level

Tree property: There is exactly one path from the root R to each descendant of R (note: there is only one root).

Lots of specialised trees

• binary trees
• binary search trees
• AVL-trees
• red-black trees
• 2-3 trees
• tries

Binary Trees

most important kind - used to model yes/no, on/off, higher/lower, i.e., binary decisions

Recursive Definition: A binary tree is either the empty tree or a node that has left and right subtrees that are binary trees.

Empty trees are represented as boxes in the diagram below (but we will almost always omit the boxes).

Traversing Binary Trees

• preorder
  1. visit node
  2. traverse left subtree
  3. traverse right subtree
• inorder
  1. traverse left subtree
  2. visit node
  3. traverse right subtree
• postorder
  1. traverse left subtree
  2. traverse right subtree
  3. visit node

In the example tree from the previous diagram, the traversals will visit

• preorder - 1 2 3 5 4 6
• inorder - 2 3 1 4 5 6
• postorder - 3 2 4 6 5 1

Below is an example expression tree.

• inorder - ((((4 / 2) * 7) + (3 - 1))
• preorder - + * / 4 2 7 - 3 1
• postorder - 4 2 / 7 * 3 1 - +

Linked Representation of Binary Trees

A typical tree structure in C

typedef struct node {
   value_type value;
   struct *node left;
   struct *node right;
} binary_tree_type;

Assumption is that empty trees will be null pointers.

Preorder traversal code, a recursive technique.

/* preorder traversal of a tree, a recursive technique */
void preorder(binary_tree_type *tree) {
  if (tree == NULL) return;
  visit(tree);
  preorder(tree->left);
  preorder(tree->right);
}

Preorder traversal code, a stack technique.

/* preorder traversal of a tree, implemented using a stack */
void preorder(binary_tree_type *tree) {
  stack_type *stack;

  stack = create_stack();
  push(tree, stack);
  while (!empty(stack)) {
    tree = pop(stack);
    visit(tree);
    push(tree->left, stack);
    push(tree->right, stack);
    }
}