AS/A Computer Science: Fundamentals of data structures

Trees

A tree is an abstract data structure that is a special type of graph. To be a tree, a graph must have the following qualities:

Be connected and undirected
Have no cycles

A cycle is where there is a path from one node back to itself without going through any node twice.

Rooted trees

A rooted tree is a special type of tree with the following properties:

A root node with no parent node only child nodes
Each subsequent node has connections to one parent node and their own child nodes

Rooted tree terminology

Node: A single piece of data in the tree e.g. any letter
Edge: A connection between nodes
Root: The only node with no parent e.g. A is the root above
Child: Nodes that have an incoming edge from a node above e.g. E is a child of B
Parent: A node is a parent of all the nodes it connects to with outgoing edges below e.g. C is parent of F, G nd H
Subtree: A subtree is any parent node and all the connected child nodes beneath e.g. the part of the graph including B, D, E, I, J and K is a subtree
Leaf node: A node that has no children e.g. J is a leaf node

Binary trees

A binary search tree is a special type of rooted tree where each node has a maximum of two children. To construct a binary tree you need to follow these steps:

Have one piece of data act as the root node
For each new item the root node becomes the current node
If the new item is above the current node move right, if this branch is empty place the item here
If it is below the current node move left, if that branch is empty place it here
Continue down the tree repeating the last two steps until an unfollowed branch is found

The tree above is the binary tree we get to represent: Jim, Bob, Sam, Tom, Tim, Art, Joe, Dan. We start with Jim as the root node.

Bob comes before Jim so is attached as the left node.

Sam comes after Jim so is attached as the right node to the root.

Tom comes after Jim so we move to Sam. Tom comes after Sam so is attached as the right node of Sam.

Tim comes after Jim so we move to Sam. Tim comes after Sam so we move to Tom. Tim comes before Tom so is attached as the left node to Tom.

Art is less than Jim so we move to Bob. Art is less than Bob so we attach it as the left node to Bob.

Joe is greater than Jim so we move to Sam. Joe comes before Sam so is attached as a left child to Sam.

Dan is less than Jim so we move to Bob. Dan is greater than Bob so is attached as a right node to Bob.

Traversing trees

There are three ways of traversing a binary tree:

Pre order traversal
In order traversal
Post order traversal

Pre-order traversal

Starting at the root node we move left encountering each node as we pass its left side. So with pre-order traversal we encounter Jim, then Bob, Art, Dan, Sam, Joe, Tom, and finally Tim.

In-order traversal

Starting at the root node we move left encountering each node as we pass directly under it. So with in-order traversal we encounter Art, then Bob, Dan, Jim, Joe, Sam, Tim, and finally Tom.

Post-order traversal

Starting at the root node we move left encountering each node as we pass directly under it. So with post-order traversal we encounter Art, then Dan, Bob, Joe, Tim, Tom, Sam, and finally Jim.

Implementing a binary tree

A binary tree can be implemented as a 2D array where each array in the array of arrays is a node and contains the array position of its left child, the node data, and the array position of its right child. A node value of -1 is used to indicate there is no child.

Knowledge check

Questions:

Correct:

Question text