Lab 2, CSC 202

8.12

Lab 2, CSC 202🔗

To solve a problem, one often considers different ways to represent the relevant data. In some instances, the data might reasonably be placed in a sequence or the data might naturally dictate a hierarchy. This lab introduces the basic structure of and operations on two of the most common data structures: a linked list and a binary tree.

1 Linked List🔗

A linked list is either

Empty; or
A pair containing some value and the rest of the list

One realization of this definition in Python is the following data definition.

MyList: TypeAlias = Union[None,Pair]

@dataclass(frozen=True)
class Pair: first: Any rest: MyList

One can use instances of this class to create a list of the numbers 7 ,4 ,2 ,19 ,42 (in this order) as follows.

Pair(7, Pair(4, Pair(2, Pair(19, Pair(42, None)))))

This explicit form is useful at this point to emphasize the structure of the data. Working with longer lists, say of millions of elements, will require building a list incrementally, and we will get there.

A note about the quotes around 'Pair' here: the types MyList and Pair both depend on each other. That is, they are "mutually recursive" types. MyPy supports such definitions, but Python, for historical reasons, requires a hack here. Specifically, the "forward" reference (that is, the use of MyPair that occurs before the definition of MyPair) must be written with quotes around it. Is this a hack? Yes, it sure is.

1.1 Operations🔗

In the file named "list_ops.py", write a data definition for a NumList, refining the data definition to restrict it to contain "int"s only.

Next, follow the design recipe (data definitions if necessary, signature, purpose statement, header, test cases, fill in body) to design the following functions. Your test cases must use the unittest module; place your test cases in a single TestCase class at the bottom of the file.

Note: Your goal is not to just implement these operations so that they pass some test cases. Pay particular attention to the structure of the data, the similarities between the functions that you are writing, and how the code is structured in a manner similar to the data (especially when written recursively, and even more so for binary trees).

Finally, none of these functions require mutation. Don’t use mutation to solve any of these problems. That is: don’t change the value of a field or of a variable.

length: Define a function named length that takes a linked list and returns the number of values in the list.
sum Define a function named sum that takes a linked list of numeric values and returns the sum of the values in the list.
count_greater_than Define a function named count_greater_than that takes a linked list and a threshold value, and that returns the number of values in the list strictly greater than the threshold (e.g., the number of values in the sample list above that are greater than 10).
find Define a function named find that takes a linked list and a value to find, and that returns the position within the list where the given value appears (where the first value in a non-empty list is at position 0). If the given value does not appear in the list, return None. (Hint: this function is easier with an accumulator.)
sub_one_map Define a function named sub_one_map that takes a linked list, and returns a new linked list where each number is smaller by one.
insert Define a function named insert that accepts a NumList in ascending, sorted order and a new number, and returns a new list containing the new number in the proper location.

2 Binary Tree🔗

A binary tree is either

Empty; or
A node containing some value, a left subtree, and a right subtree

One realization of this definition in Python is the following data definition:

BinTree: TypeAlias = Union[None,'BTNode']

@dataclass(frozen=True)
class BTNode: val: Any left: BinTree right: BinTree

One can use instances of this class to create the pictured tree as follows.

TreeNode(4,

TreeNode(9,

TreeNode(19, None, None),

TreeNode(2, TreeNode(103, None, None), None)

TreeNode(42, None, TreeNode(7, None, None))

)

This explicit form is useful at this point to emphasize the structure of the data. Working with larger trees, say of millions of elements, will require building the tree incrementally (and defining how/where elements are added to the tree); as with lists, we will get there.

2.1 Operations🔗

In a file named tree_ops.py, develop the class definition for a binary tree of numbers, add it to the appropriate section, and implement each of the following operations. Follow the design recipe (data definitions if necessary, signature, purpose statement, header, test cases, fill in body) to design these functions. Your test cases must use the unittest module; place your test cases in a single TestCase class at the bottom of the file.

size Define a function named size that takes a binary tree and returns the number of the elements in the tree.
num_leaves Define a function named num_leaves that takes a binary tree and returns the number of the leaves (i.e., those nodes with both subtrees empty) in the tree.
sum Define a function named sum that takes a binary tree of numeric values and returns the sum of the values in the tree.
height Define a function named height that accepts a binary tree and returns its height, which is the length of the longest path from root to node. The binary tree "None" has height zero.
has_triple Define a function named has_triple that returns true exactly when a tree node (anywhere in the tree) with value n contains an immediate child node with value 3n.
sub_one_map Define a function named sub_one_map that returns a new tree where each value is smaller by one. Yes, this is just like the list function.