CAB301 - Algorithms and Complexity
School of Computer Science, Faculty of Science
A tree is a collection of nodes connected by directed edges.
Various implementations, but in CAB301, each node:
Key
FirstChild
FirstSibling
public class Node { public int Key; public Node FirstChild; public Node FirstSibling; }
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).
Queue
ALGORITHM // Empty queue while do while do
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).
Stack
ALGORITHM // Empty stack while do while do if