There are many real-world examples that can be represented by the tree data structure. For example, locations on a map can be represented by a tree, where the children of a location node are locations further away. A computer file system is sometimes referred to as a directory tree because directories and files can be represented as nodes. The tree we use in the examples throughout this lesson represents a simple filesystem.
The tree data structure used in this lesson is implemented in tree.py. The only class in this file is called TreeNode
and can be used to create node objects that link to each other to create a tree.
class TreeNode: def __init__(self, value): self.value = value self.children = []
The class variables that make up the tree are the same ones we’ll need for the algorithm. They are:
self.value
is the node value and can be any value capable of being tested with the==
conditional operator.self.children
is a list of uniqueTreeNode
objects. This list is what creates the tree structure that we’ll be working with.
The TreeNode
class has a __str__
method that creates a visual representation of the tree structure when a node is printed to the console.
In main.py, a sample tree has been created with a root node, sample_root_node
. This is the tree we will use to test the search implementation.
Instructions
In main.py, print the defined root node, sample_root_node
, to take a look at the tree structure.
Under the print()
statement, define a variable goal_path
and assign it the value, None
.
This variable will be used to hold the return value of the breadth-first search.
Now test goal_path
to check if it is empty:
- Create an
if
statement with the conditiongoal_path is None
. - Inside the
if
body, printNo path found
. - Add an
else
statement and inside that body, printPath found
.
Now print the path elements:
- Inside the
else
body, create afor
loop with a loop variablenode
and iterates throughgoal_path
- Inside the
for
loop body, printnode.value