Week 6: Binary Tree and Usage of Some Built-in Functions

   This week, I learned something about recursive structures. Binary tree is a kind of recursive structure. Generally, it has one node, left tree and right tree. Left tree and right tree can be either none or another tree. It is where the recursive structure from. Tree-list is one way to represent a tree. And it can also be represented as a class. To traversal a tree, we have pre-order(node, left, right), in-order(left, node, right) and post-order(left, right, node). I did not know the usefulness until I went through some examples in use of tree structure in the reading material. For instance, we can use a tree expression to translate a mathematical expression like '(3 + 7)  * 9' (see the graph above). Also use a binary tree to deal with a series of recursive questions is quite benefit. We can let the node be a question. If the answer is 'yes', read the right tree and if the answer is 'no', read the left tree. And we can create another tree to create more question recursively. See how to think like a computer scientist - Tree , it is very interesting. I have scanned the handout for assignment 2. It is also about recursive structure. In my opinion, translating a regular expression to a tree representation is quite helpful when dealing with problems like matching strings.
    Another thing I get this week is some use of built-in functions. They makes code shorter and the program more efficient. See Built-in Functions .
          1. all(iterable)

    Return True if all elements of the iterable are true (or if the iterable is empty).

2. any(iterable)

    Return True if any element of the iterable is true. If the iterable is empty, return False.

3. filter(function, iterable)

    Construct an iterator from those elements of iterable for which function returns true. iterable may be either a sequence, a container which supports iteration, or an iterator. If function is None, the identity function is assumed, that is, all elements of iterable that are false are removed.

4. map(function, iterable, ...)

    Return an iterator that applies function to every item of iterable, yielding the results. If additional iterable arguments are passed, function must take that many arguments and is applied to the items from all iterables in parallel. With multiple iterables, the iterator stops when the shortest iterable is exhausted. For cases where the function inputs are already arranged into argument tuples, see itertools.starmap().

5. repr(object)

    Return a string containing a printable representation of an object.

6. zip(*iterables)

    Returns an iterator of tuples, where the i-th tuple contains the i-th element from each of the argument sequences or iterables. The iterator stops when the shortest input iterable is exhausted. With a single iterable argument, it returns an iterator of 1-tuples. With no arguments, it returns an empty iterator.

                         >>> x = [1, 2, 3]
                         >>> y = [4, 5, 6]
                         >>> zipped = zip(x, y)
                         >>> list(zipped)
                         [(1, 4), (2, 5), (3, 6)]
                         >>> x2, y2 = zip(*zip(x, y))
                         >>> x == list(x2) and y == list(y2)
                         True

 

    We wrote some equivalent code during the lab using non-built-in functions. But use of built-in functions as well as built-in modules is of great importance to program in python.

 

Reference: http://openbookproject.net/thinkcs/python/english3e/trees.html

                  http://docs.python.org/3.3/library/functions.html