12 Trees

Introduction

The tree data structure is used to represent data stored in a hierarchical structure. Trees are a recursive data structure that is either:

Terminology
A tree is either empty or non-empty. Every non-empty tree has a root, which is connected to zero or more subtrees.
The size of the tree is the number of values in the tree.
A leaf is a value with no subtrees.
The height is the largest number of values on a path from the root to a leaf.
Depth number of levels indexed at 0 (sometimes indexed at 1)
The children of a value are all values connected underneath that value.
Branching factor global max of children (divided by interal?)
The descendants of a value are its children and those of those children.
The parent of a tree value is the value it is a child to.
The ancestors of a value are its parent and those of those parents

Implementation

class Tree:
    """A recursive tree data structure.
    
    === Private Attributes ===
    The item stored at this tree's root, or None if the tree is empty.
    _root: Optional[Any]
    The list of all subtrees of this tree.
    _subtrees: list[Tree]
    === Representation Invariants ===
    - If self._root is None then self._subtrees is an empty list.
    This setting of attributes represents an empty tree.

     - Note: self._subtrees may be empty when self._root is not None.
    This setting of attributes represents a tree consisting of just one
    #   node.
    """
    
    def __init__(self, root: Optional[Any], subtrees: list[Tree]) -> None:
        """Initialize a new tree with the given root value and subtrees.
        If <root> is None, this tree is empty.
        Precondition: if <root> is None, then <subtrees> is empty.
        """
        self._root = root
        self._subtrees = subtrees
        
	def is_empty(self) -> bool:
        """Return whether this tree is empty.

        >>> t1 = Tree(None, [])
        >>> t1.is_empty()
        True
        >>> t2 = Tree(3, [])
        >>> t2.is_empty()
        False
        """
        return self._root is None

Recursion On Trees

General Template

def f(self)-> ...:
	if self.is_empty():
		...
	# elif self._subtrees == []: 
	#	return 1	
	else:
		...
		for subtree in self._subtrees: 
			... subtree.f() ...
		...

is_empty

def __len__(self) -> int:
	"""Return the number of items contained in this tree
	>>> t1 = Tree(None, [])
	>>> len(t1)
	0
	>>> t2 = Tree(3, [Tree(4,[]), Tree(1, [])])
	>>> len(t2)
	3
	"""
	if self.is_empty():
		return 0
	else: 
		size = 1 # count the root 
		for subtree in self._subtrees: 
			size += subtree.__len__() # could also do len(subtree) here 
		return size

Traversing a Tree

Print example:

def _str_indented(self, depth: int=10)-> str:
	if self.is_empty():
		return ''
	else:
		s = ' ' * depth + str(self._root) + '\n'
		for subtree in self._subtrees:
			s += subtree._str_indented(depth + 1)
		return s
def __str__(self) -> str:
	return self._str_indented(0)

>>> t1 = Tree(1, [])
>>> t2 = Tree(2, [])
>>> t3 = Tree(3, [])
>>> t4 = Tree(4, [t1, t2, t3])
>>> t5 = Tree(5, [])
>>> t6 = Tree(6, [t4, t5])

6
  4
    1
    2
    3
  5

Mutating Trees

Two fundamental mutating operations: Insertion and Deletion

def delete_item(self, item: Any) -> bool:
    if self.is_empty():
        return False                        # item is not in the tree
    elif self._subtrees == []:
        if self._root != item:              # item is not in the tree
            return False
        else:
            self._root = None               # resulting tree should be empty
            return True
    else:
        if self._root == item:
            self._delete_root()             # delete the root
            return True
        else:
    for subtree in self._subtrees:
        deleted = subtree.delete_item(item)
        
        if deleted and subtree.is_empty():
            # The item was deleted and the subtree is now empty.
            # We should remove the subtree from the list of subtrees.
            # Note that mutating a list while looping through it is
            # EXTREMELY DANGEROUS!
            # We are only doing it because we return immediately
            # afterwards, and so no more loop iterations occur.
            self._subtrees.remove(subtree)
            return True
        elif deleted:
            # The item was deleted, and the subtree is not empty.
            return True
        else:
            # No item was deleted. Continue onto the next iteration.
            # Note that this branch is unnecessary; we've only shown it
            # to write comments.
            pass

    # If we don't return inside the loop, the item is not deleted from
    # any of the subtrees. In this case, the item does not appear
    # in <self>.
    return False

def _delete_root(self) -> None:
    """Remove the root item of this tree.

    Precondition: this tree has at least one subtree.
    """
    # Get the last subtree in this tree.
    chosen_subtree = self._subtrees.pop()

    self._root = chosen_subtree._root
    self._subtrees.extend(chosen_subtree._subtrees)