rewrite: tree

    Tree is kind of basic data structure which is used for storing data.  Each tree only has one root and each non-root nodes has exactly one parent.  There are directed edges between some pairs of nodes.  In addition the number of edges in a sequence of nodes, called path, is the length of the this path.  In the following, there are some codes of tree class.

        First of all, it is the initialized of class tree, but it does not store any data or built a structure of a tree.  In addition, there are two different ways to build a tree to store data.  
        1. Using recursion method to build a tree under a root.
        2. Build a bunch of trees and  make them up in one tree.
     
       Obviously, the second method is inefficient.  Thus I will introduce the first method in the following article.  Here is the code of a game-state tree.

def grow(self):
        ''' (GameStateNode) -> NoneType

        Grow the tree of all possible game state nodes that can be reached
        starting from this one.

        Assume that the game is finite (and so the tree will be finite).
       
        >>> a0 = SubtractSquareState('p1', current_total = 0)
        >>> b1 = SubtractSquareState('p2', current_total = 1)
        >>> a2 = SubtractSquareState('p1', current_total = 2)
        >>> b3 = SubtractSquareState('p2', current_total = 3)
        >>> a4 = SubtractSquareState('p1', current_total = 4)
        >>> b0 = SubtractSquareState('p2', current_total = 0)
        >>> a0_node = GameStateNode(a0)
        >>> b1_node = GameStateNode(b1)
        >>> b1_node.children = [a0_node]
        >>> a2_node = GameStateNode(a2)
        >>> a2_node.children = [b1_node]
        >>> b3_node = GameStateNode(b3)
        >>> b3_node.children = [a2_node]
        >>> b0_node = GameStateNode(b0)
        >>> a4_node = GameStateNode(a4)
        >>> a4_node.children = [b0_node, b3_node]
        >>> root = GameStateNode(SubtractSquareState('p1', current_total = 4))
        >>> root.grow()
        >>> root.__eq__(a4_node)
        True
        '''
        if self.value.possible_next_moves != []:
            for move in self.value.possible_next_moves():
                new_gamestate = self.value.apply_move(move)              
                node = GameStateNode(new_gamestate)
                self.children.append(node)
            for item in self.children:
                item.grow()

    According to the doctext, I use the second method to build the tree. As I said see before, it is quite inefficient, but it just use to check the following code is right.  In the code, we need to build a different trees as the children of the root by using recursion, which is more efficient than the second method.

Link List

    Link list likes tree what we learn before.  However there are quite different between them.  Link list only have one node of one root which is unlike tree, having 2 or 3 nodes.
    Firstly, we need a class, which likes a tree class, to record a value that before of after a value.

    Secondly, we can create a link list class.  In the __init__ function, we create two variable to record a link list in the following method.

    

    Following, it is the method that use to append a value before a value.

    Lastly, it is the method that use to append a value after a value.

def append(lnk, value):

        ''' (LinkedList, object) -> NoneType

        Insert a new node with value at back of lnk.

        >>> lnk = LinkedList()

        >>> lnk.append(5)

        >>> lnk.size

        1

        >>> print(lnk.front)

        5 ->|

        >>> lnk.append(6)

        >>> lnk.size

        2

        >>> print(lnk.front)

        5 -> 6 ->|

        '''

        new_node = LLNode(value)

        if lnk.back:

            lnk.back.nxt = new_node

            lnk.back = new_node

        else:

            lnk.back = lnk.front = new_node

        lnk.size += 1

Tree

    Tree is kind of basic data structure which is used for storing data.  Each tree only has one root and each non-root nodes has exactly one parent.  There are directed edges between some pairs of nodes.  In addition the number of edges in a sequence of nodes, called path, is the length of the this path.  In the following, there are some codes of tree class.
    First of all, it is the initialized function of tree class.

    Secondly, there are some method about tree class.  

    It is the method about counting leaves(nodes with no children).  In this method, we use a recursion to guarantee to get the basic nodes of the tree.

    It is the method about counting internal nodes (node with one or more children).  In this method, we use a recursion to find out all the nodes which does not have children from the root to the basis.  

Stack

    Stack is a kind of data type, which is last-in-first-out(LIFO) structure.  Basically, it can be achieved through two methods of list.  As the following, there are some codes demonstrating how it works.
    First of all, we need to initial a new stack.  In other word, we need to create a new empty list.

    Secondly, we can push any element into the stack through using a list method, list.append().

 

    Finally, if we need to delete the top element from stack, we can achieve by using list.pop() method.

    By and large, any elements push into the stack will be on the top of the stack, which will be removed firstly as well.  What's more, all of the operation can be achieved by two list method, list.pop() and list.append().

Object-Oriented Programming

    Python is a kind of Oriented-Object Programming, which is a programming paradigm which is built on the concepts of class, inheritance, object.
    Class is a collection of the features, properties of an object.  For example, tree is a broad definition, containing all the features of tree, such as color, size and shape.
    Object is an example of class.  For instance, tree define all the characteristics of tree around the world, and Tina is a specific example tree, which has its unique shape of leaves and unique color of leaves.  The difference between class and object likes the relationship of the set of Z and "1" in math.
    Inheritance is a concept that there is a sub-class in a class.  For example, tree is a wide definition and may has its sub-class, such as pine tree and maple tree.  Tina may be a sort of pine tree which inherits properties and behaviors of its parent class and may have its own properties and behaviors.
    Message passing means that object implement a function through receiving a message or dealing message.  It likes a series of reactions when leaves fall.
    By and large, Oriented-Object Programming collects and save all the information and operations into the program.

Recursive Function Exercise

What I wrote last is how to solve problems about recursive function.  In this week, I will write some exercises about recursive function.

count_elements(‘snork’)

count_elements([2, 1, 3])

The answer for the first one is 1, because ‘snork’ is not a list.  For the second one, the answer is 1.  Since [2, 1, 3] is a list, the function will run sum([count_elements(x) for x in L]) and will return sum([1 ,1, 1]) which is 3.

nd(‘ox’)

nd([])

The answer for the first one is 0, because ‘ox’ is not a list.  For the second one, since [] is a list though it is an empty list, the function will run 1 + max([nd(x) for x in (L+ [‘ox'])]) and L will become ['ox'].  Since 'ox' is not a list, which will let L become [0].  Then the function will return 1 eventually.

After doing these exercises, solving recursive function becomes much easier.

Recursive Function

What professor taught to us this week was recursive function, which is brand new for me.  In the lecture, I could master the example that professor provided, sum_list function.  What we need to for the solution of this function just sums sublists and main list up.  However, when I did the exercise in the lab3 handout in the tutorial time, I just lost myself.  I did not know what I should do with that kind of problems.

         Therefore, I asked from help Ta and she just drew a graph and demonstrated to me how the function works steps by steps.  For example, find the solution for nm ([1, 3, 7, 5, 2]).

According to Ta’s method, firstly we need to determine L is a list or not.  In this question, L is a list, therefore, the function will return max([nm(x) for in [1, 3, 7, 5, 2]]).  Next step, let us consider the elements in the list L.  Since all of the elements in list (1, 3, 7, 5 and 2) are not a list.  Therefore, the function will return (1, 3, 7, 5 and 2).  Finally, the function will return max([1, 3, 7, 5, 2]), which is 7.  Thus the solution for this question is 7.

         This approach helps me a lot in solving recursive function.  Through this method, I can find out all the steps that the function works.

Why geeks need to know how to write?

Dating back to the ancient time, writing is not only the one of the most important methods for people to communicate with others who is far away from, but also is a tool for litterateur to express their opinions or mood.  More importantly, this culture is inherited to the modern society.  Writing daily experience on Facebook or blog and publishing literature writings on magazine becomes an inevitable part of people life.

Writing, a vital communication approach, expresses opinions, thoughts and suggestion of one people.  For example, in daily life, people is willing to spend an hour to write a journal on Facebook and share with their friends every day.  In business, people write 20 pages of paper to present a project to their bosses.  Therefore, writing is a necessary skill for everyone. 

By and large, writing plays a significant role of people, which is used to interchanging their opinions or mood with others in life.  For every geek, writing is a necessary skill for expressing their thoughts to others.  If someone does not know how to writing, he/she never can express his/her ideas, which means that even you are a genius, no one could learn about you.