🪜
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
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
