Trees
Computer Science: OCR A Level, topic 4.2.7
Trees
Unlike other data structures in computer science, trees represent data hierarchically.
Roots and branches
- Trees begin with a ‘root’ node, with one or more ‘branches’ beneath it.
- Each branch, in turn, can have one or more sub-branches connected to it.
Tree construction
- The rules for creating a tree are:
- Each node must only be connected to one ‘parent’ node and one or more ‘children’.
- There should be no connections directly between nodes on the same level of the hierarchy.
Tree traversal
- There are three ways to navigate, or ‘traverse’ a tree data structure:
- Pre-order.
- In-order.
- Post-order.
Pre-order traversal
- Pre-order traversal starts with the root node, then visits each of the other nodes from left to right.
- In the example shown, the nodes are visited in the following order:
- Tiger, Zebra, Lion, Gazelle, Giraffe, Rhino, Hippo, Elephant
In-order traversal
- In-order traversal starts with the nodes in the left subtree, then visits the root node followed by the nodes in the right subtree.
- In this case, the nodes above are visited in the following order:
- Lion, Zebra, Gazelle, Giraffe, Tiger, Elephant, Hippo, Rhino.
Post-order traversal
- Post-order traversal starts by visiting the nodes in the left subtree from bottom to top, then the right subtree bottom to top, before finishing with a visit to the root node. - The nodes in the example above are therefore visited in the following order:
- Lion, Gazelle, Giraffe, Zebra, Elephant, Hippo, Rhino, Tiger.
Test yourself on Trees
In which order would an in-order traversal visiting the nodes in the graph shown?
In which order would an pre-order traversal visiting the nodes in the graph shown?
In which order would an post-order traversal visiting the nodes in the graph shown?