Graph and Tree Traversal (AQA A-Level Computer Science): Flashcards
📚Flashcards
Practise the cards
10 cards from this deck
ShowHide
Practise the cards
10 cards from this deck
Traversal definition
Traversal definition
Visiting every node in a structure in a specific order
Adjacency list
Adjacency list
Each node listed with all nodes directly connected to it
Adjacency matrix
Adjacency matrix
2D array with 1s (edge exists) and 0s (no edge)
Depth first traversal method
Depth first traversal method
Explores far along each path before backtracking
Breadth first traversal method
Breadth first traversal method
Explores all nodes at current distance before moving further
Binary tree definition
Binary tree definition
Tree where each node has at most two children
Pre-order traversal sequence
Pre-order traversal sequence
Visit, left, right
In-order traversal sequence
In-order traversal sequence
Left, visit, right
Post-order traversal sequence
Post-order traversal sequence
Left, right, visit
Recursion base case
Recursion base case
Defines when recursive function stops calling itself