Week6: Trees

    This week we are introduced to Trees. They have unique properties so that they can build expressions and even make wise "animal tree".

     The tree is similar to linked lists. Start with terminologies, it consists of nodes(the top one is root). The paths between parent and children are called edges; the length of edges is the number of edges. Height is the maximum path length from the leaf(the node that has no children) to root. Likewise, the level of the tree is all the nodes that have same distance to root. The last fancy word is arty or branching factor, which means the maximum children within any node. 

 
    There are basically three ways of traversal for tree expression. They are pre-order(prefix) traversal, in-order(infix) traversal and post-order(postfix) traversal. As we want to print the contents of a tree in specific order, we need to write up functions. For a binary tree, the followings are the examples of the three different orders.

def print_tree(tree):
    if tree is None: return
    print(tree.cargo, end=" ") #cargo is the value
    print_tree(tree.left)
    print_tree(tree.right)

def print_tree_postorder(tree):
    if tree is None: return
    print_tree_postorder(tree.left)
    print_tree_postorder(tree.right)
    print(tree.cargo, end=" ")

def print_tree_inorder(tree):
    if tree is None: return
    print_tree_inorder(tree.left)
    print(tree.cargo, end=" ")
    print_tree_inorder(tree.right)

    The key for pre-order traversal is always print root(cargo) of a TreeList at first and then go into the left subtree which is a recursive call, and print its cargo and the left subtree of it until the tree is None, it exit and return to previous call to execute "print_tree(tree.right)" which is another similar recursive call. In a general view, it will print the root, the entire left subtree and the entire right subtree. For post-order traversal, it print from the left subtree to right subtree, and finally root. Obviously, the in-order traversal prints in an order of left subtree, root and right subtree. These different traversal make Tree neat, functional and well-organized.

    On the other hand, we are learning how to build an expression tree. By giving with a list of string which a mathematical operation expression, we rearranged them in an ordered way according to different priorities of operations. It is important to consider multiplying, addiction, and even parentheses. Another thing to remind, to avoid python quit unexpectedly, we would better write exceptions to raise error.

    Last but not least, the animal tree is something that I found like an interesting and cute game. After the training by ourselves, it learns new knowledge. I would like to put the long code below for appreciation.

def yes(ques):
    ans = input(ques).lower()
    return ans[0] == "y"

def animal():
    # Start with a singleton
    root = Tree("bird")

    # Loop until the user quits
    while True:
        print()
        if not yes("Are you thinking of an animal? "): break

        # Walk the tree
        tree = root
        while tree.left is not None:
            prompt = tree.cargo + "? "
            if yes(prompt):
                tree = tree.right
            else:
                tree = tree.left

        # Make a guess
        guess = tree.cargo
        prompt = "Is it a " + guess + "? "
        if yes(prompt):
            print("I rule!")
            continue

        # Get new information
        prompt  = "What is the animal's name? "
        animal  = input(prompt)
        prompt  = "What question would distinguish a {0} from a {1}? "
        question = input(prompt.format(animal, guess))

        # Add new information to the tree
        tree.cargo = question
        prompt = "If the animal were {0} the answer would be? "
        if yes(prompt.format(animal)):
            tree.left = Tree(guess)
            tree.right = Tree(animal)
        else:
            tree.left = Tree(animal)
            tree.right = Tree(guess)

(from: http://openbookproject.net/thinkcs/python/english3e/trees.html)

    The part I found difficult to understand is that only the leaf refers to an animal, and the other nodes actually contain questions. The function has multiple levels for completion which eventually creates someone we can communicate with.

    Keep working and hope everything runs smoothly(especially my code)!!