A tree has a root value and a sequence of branches. Each branch of a tree is a tree. A tree with no branches is called a leaf. Any tree contained within a tree is called a sub-tree of that tree (such as a branch of a branch). The root value of a sub-tree of a tree is called a node (or node value) in that tree.
The data abstraction for a tree consists of the constructor tree and the selectors root and branches.
In creating a tree, this first thing I want to do is decide on the underlying data structure I will use to model the tree. In this case, I am defining a tree as it's root and branches, all modeled using python lists.
In [9]:
def is_tree(tree):
"""Determine whether this is an instance of an acceptable tree.
Return boolean
"""
# all trees must be of type tree and have atleast one element
if type(tree) != list or len(tree) < 1:
return False
for branch in branches(tree):
if not is_tree(branch):
return False
return True
def tree(root, branches=[]):
"""
Tree constructor
Attributes
----------
root: singleton list
branches: list
"""
for branch in branches:
assert(is_tree(branch)), 'branches must be trees'
return [root] + list(branches)
def root(tree):
return tree[0]
def branches(tree):
return tree[1:]
In [15]:
aTree = tree(5, [tree(1), tree(2)])
In [16]:
aTree
Out[16]:
In [ ]: