AQA A-Level Computer Science Summary - Fundamentals of Algorithms

🪜
Fundamentals of Algorithms
Last edited time @November 12, 2023 1:40 PM

Status Done

Graph and tree traversal
There are two ways of traversing a graph.

Depth first → A method for traversing a graph that starts at a chosen bode an
explores as far as possible along each branch away from the starting node
before backtracking.

breadth first → A method for traversing a graph that explores nodes closes to
the starting node first before progressively exploring nodes that are further
away. A queue 📦 Fundamentals of data structures is used to keep track of
the nodes to visit.

These can be best visualised using a tree which can be seen below:




A depth first traversal of a tree




Fundamentals of Algorithms 1

, A breadth first traversal of a tree


Traversing a binary tree
traversal → The process of reading data from a tree or graph by visiting all of
the nodes. Recursive algorithms are used.
Pre-order traversal → A method of traversing a tree by outputting the node,
traversing the left child, and then the right child.


void PreOrderTraversal(Node n)
{
Console.WriteLine(n.Data);

if (n.LeftChild != 0)
PostOrderTraversal(n.LeftChild);

if (n.RightChild != 0)
PostOrderTraversal(n.RightChild);
}




In-order traversal → A method of traversing a tree by traversing the left child,
outputting the node and the traversing the right child.


void InOrderTraversal(Node n)
{
if (n.LeftChild != 0)
PostOrderTraversal(n.LeftChild);


Console.WriteLine(n.Data);

if (n.RightChild != 0)
PostOrderTraversal(n.RightChild);
}




Fundamentals of Algorithms 2