Tutorial 6: Trees and Algorithms

CAB301 - Algorithms and Complexity

School of Computer Science, Faculty of Science

Tree

A tree is a collection of nodes connected by directed edges.

Various implementations, but in CAB301, each node:

  • Has a piece of data (Key)
  • Reference to its FirstChild
  • Reference to its FirstSibling
public class Node
{
    public int Key;
    public Node FirstChild;
    public Node FirstSibling;
}
CAB301 - Algorithms and Complexity
School of Computer Science, Faculty of Science

Breath First Traversal

Visit all nodes at a given depth before moving to the next depth. Use a Queue to store sibling nodes. Nearer siblings (first in) are visited first (first out).

ALGORITHM
// Empty queue

while do



while do

alt text

CAB301 - Algorithms and Complexity
School of Computer Science, Faculty of Science

Depth First Traversal

Visit all nodes in a branch before moving to the next branch. Use a Stack to store sibling nodes. Deeper siblings (last in) are visited first (first out).

ALGORITHM
// Empty stack

while do

while do

if

alt text

CAB301 - Algorithms and Complexity
School of Computer Science, Faculty of Science