TREES TREES TREES

Hello everyone,

I’m back with yet another blog post. Hope my other posts have been interesting and you guys had fun reading them. This week we have our second assignment due for CSC148 and on top of that I have a term test for my other class on the same day as the CSC148 assignment. Fortunately, I have been studying earlier of the test that now I can focus on the assignment with my group, which we also started earlier. Unfortunately, we have not been able to crack the minimax strategy. Minimax is a strategy which allows the player who uses the strategy to choose the best possible move such that he wins. Sounds simple, right? Well it is not as simple as it sounds, we have been working on it for such a long time; however, no avail yet.

Minimax why won’t you work??? Too much confusion. Well I can only hope that we can somehow get minimax to work before the deadline and submit a proper running code. *Fingers crossed*

Last week we were introduced to the Trees which are another abstract data type (ADT). This tree object can be compared to our real-life trees, because similarly they also have root, from which children’s may branch form. In class we defined trees as a set of nodes with directed edges between pair of nodes. The edge connects parent node to a child node. Furthermore, a node can contain value and the nodes with do not have any children are known as leafs. It is also important to note that a node can only have one parent and obviously the exception is root, which does not have any parent.

This is an example of a binary tree, which is a special kind of tree in sense that the number of children in a binary tree are restricted to a maximum of 2. Therefore each node has a branching factor also known as arity (max number of children) is 2. The children are known as left and right child, very convenient. In this tree, can you guess what root may be? That’s correct, it is indeed 2. What about the leafs? Right again, the leafs are 2, 5, 11 and 4.

Trees have several uses and few such uses include representation of hierarchical relationships, a directory structure or even relationships in arithmetic expression. Tree traversal is used to achieve various things because during traversal each node is visited and at the node the programmer can perform a specified action. Furthermore, the order of traversal can also be decided from the following 3 standard methods:

-        inorder – visit the node in between visiting its two children; thus, visit the left sub tree inorder, the node itself and then finally visit the right sub tree inorder.

In our tree example, for in order traversal we will visit in the following order 2,7, 5,6, 11, 2, 4, 9 and 5.

-         preorder – visit the node before its children; therefore, visit the node itself, then left subtree in preorder and finally right sub tree in preorder.

-         postorder – visit the node after its children; therefore, the left sub tree in postorder, right sub tree in postorder and then finally the node itself.

Try working on the preorder and postorder traversal of the tree in the image above. If you need more information on trees, post in the comment section below and I will be more than happy to discuss further. I also stumbled upon Thomson blog, which I feel is also very descriptive in explaining the concept of trees.