Chapter 12 - Graph and Tree Traversal Flashcards
What is implementation?
Creating code to produce a programmed solution.
What is an array?
A set of data items of the same grouped together with the same identifier.
What are the two ways of traversing a graph?
Depth first or Breadth first.
How do you traverse a graph depth first?
A method for traversing a graph that starts at chosen node and explores as far as possible along each branch away from the starting node before backtracking to visit unvisited nodes.
How do you traverse a graph breadth first?
A method for traversing a graph that explores nodes closest to the starting node first before progressively exploring nodes that are further away. A queue is used to keep track of the nodes to visit.
What is a queue?
A data structure where the first item added is the first item removed.
What is pre-order?
A method traversing a tree by visiting the root, traversing the left subtree and traversing the right subtree.
What is in-order?
A method of traversing a tree by traversing the left subtree, visiting the root and traversing the right subtree.
What is post-order?
A method of traversing a tree by traversing the left subtree, traversing the right subtree and visiting the root.
What is binary search?
A technique for searching data that works by splitting datasets in half repeatedly until the search data is found.
Define recursion.
A technique where a function can call itself in order to complete a task.
