Week 8 SLOG：the Summary of Tree

Tree is an abstract data type. First of all, a tree is a set of nodes with directed edges between some pair of nodes and an edge connects a parent node and a child node. Following this, the path is a sequence of nodes n1, n2...nk where there is an edge from ni to ni+1 and the length of a path is the number of edges on it. 

In addition, it has many different parts such as leaf, internal node, subtree, height and depth.  Firstly, leaf is a node with no child. Secondly, internal node is a node with one or more children. Thirdly, subtree is a tree formed by any nodes and its descendants, and the edges connecting them. Fourthly, height is the maximum path length +1. Finally, depth equals to height of the whole tree minus the height of the tree rooted at that rode.

Initializing the class Tree:

class Tree:
    ''' Represent a Bare-bones Tree ADT'''

    def __init__(self, value=None, children=None):
        ''' (Tree, object, list) -> NoneType

        Create Tree(self) with content value and 0 or more children.
        '''

        self.value = value

        self.children = children.copy() if children else []

For the height of the tree, here is the code of it:

def height(t):
    ''' (Tree) -> int
    
    Return height of Tree t,

    >>> tn2 = Tree(2, [Tree(4), Tree(5), Tree(7), Tree(8)])
    >>> tn3 = Tree(3, [Tree(6), Tree(10)])
    >>> tn1 = Tree(1, [tn2, tn3])
    >>> height(tn1)
    3
    '''
    if not t.children:
        return 1
    else:
        return max([height(c) for c in t.children]) + 1

Furthermore, we can also analyze the tree from different sides, so we initializing the class BTNode:

class BTNode:
    '''Binary Tree node.'''

    def __init__(self, data, left=None, right=None):
        ''' (BTNode, object, BTNode, BTNode) -> NoneType

        Create BTNode (self) with data and children left and right.
        '''
        self.data, self.left, self.right = data, left, right

And here is the method of parenthesize:
def parenthesize(b):
    ''' (BTNode) -> str

    Parenthesize the expression rooted at b, so that float data is not parenthesized,
    but each pair of expressions joined by an operator are parenthesized.

    Assume:  -- b is a binary tree
             -- interior nodes contain data in {'+', '-', '*', '/'}
             -- interior nodes always have two children
             -- leaves contain float data

    >>> b = BTNode(3.0)
    >>> print(parenthesize(b))
    3.0
    >>> b = BTNode('+', BTNode('*', BTNode(3.0), BTNode(4.0)), BTNode(7.0))
    >>> print(parenthesize(b))
    ((3.0*4.0)+7.0)
    '''
    if b.right is None and b.left is None:
        return b.data
    else:
        return ("(" + str(parenthesize(b.left)) + b.data 
                + str(parenthesize(b.right)) + ")")

What's more, below is the method to find the longest path in the tree:

def list_longest_path(node):
    ''' (BTNode) -> list

    List the data in a longest path of node.

    >>> list_longest_path(None)
    []
    >>> list_longest_path(BTNode(5))
    [5]
    >>> list_longest_path(BTNode(5, BTNode(3, BTNode(2), None), BTNode(7)))
    [5, 3, 2]
    '''
    if node is None:
        return []
    else:
        if node.left is None and not node.right is None:
            return [node.data] + list_longest_path(node.right)
        elif node.left is None and node.right is None:
            return [node.data]
        elif node.right is None and not node.left is None:
            return [node.data] + list_longest_path(node.left)
        else:
            left = list_longest_path(node.left)
            right = list_longest_path(node.right)
            if len(left) < len(right):
                return [node.data] + right
            else:
                return [node.data] + left