binary tree and traversal

Week 7 is such a big week with so many contents that without deep understanding of the lectures in this week directly causes poor marks for my term test 2 QAQ.

In this week we did: binary tree, tree traversal, assignment 2 and binary search tree(posted in slog of week 9). At the beginning of the lecture Danny talked a little bit about assignment 2. I liked this assignment so much that right on the morning of Apr 11th I still feel it's the best one I've ever tried to work on . This assignment, which I think, contains some basic contents and thoughts of AI(artificial intelligence). In this assignment we were asked to design a game called Tippy and try to upgrade our strategy for computer in assignment 1. The new strategy we need to write is called Minimax. Based on the condition that player one will always pick a proper move just like computer, Minimax is a strategy that implicitly go through a game tree by implementing recursive function whose base cases are the ending situation(game states) of the game. As a general strategy, Minimax is supposed to be able to work for any kinds of 2p games. The principle of Minimax is to keep applying moves if there's possible move exists until it reaches the very end of the game (a player wins). The player who wins will be given a base score with value of 1 and the other player -1 as he loses the game. According to the concept of zero-sum game (what is good for one player must be bad for the other) and the same level of intelligence of two players, we can multiply the base score by -1 to get the score for another player in the upper states of the game. We repeat this process until we reach the state for computer to pick a move among possible moves. What we need to pick the correct move is to pick the lowest score for its opponent in all the next game states by using function min(). In this way we realize a very basic extent of AI for computer to pick move smartly. This assignment is so interesting that makes me feel like to focus on AI if I'm enrolled in my program.

After a brief mention and some hints for A2 Danny began to introduce a new data structure for the course called binary tree. A binary tree is just a special case of the general tree. Just like its name, a Binary tree only has two children for each node: self.left and self.right. We need to implement class BTNode for our binary tree to have these special attributes. Danny gave us a vivid example as a representation of the binary tree:
     *
   +   6
  3  7
As arithmetic binary expressions can be represented by binary tree, if we evaluate this BT we expect the result of 60(10*6).

To lay the background for BST, We need some basic knowledge about tree traversal first. There were 3 kinds of traversals which we did in the lecture: preorder, postorder and inorder. All of these three kind of traversal require the implementation of recursive function. The difference between these three traversals is the order of the nodes being visited. For preorder traversal we visit the root then the left then the right(root -> left -> right); for inorder we go like: left -> root -> right; for the postorder it's: left -> right -> root. On wikipedia it said all these three traversals are depth-first type and there's another type called breath-first search which contains level-order traversal.

After let us know some basic concepts about BT and tree traversal, Danny moved on to the BST( impression posted in the slog of week 9). In general week 7 was a big week with many quite challenging contents. We need to take time to think about all these data structures to completely understand how they work.