Week 6: Trees

(Since it is reading week now, I think it is a good idea to catch up with the slogs I've missed)

This week, we learned about 'trees', a common way to store information. The example the prof gave focus more on the binary tree. Also, as I read through more articles about trees, I came through a paragraph talking about the difference between "data type" and "data structure".

The picture above is the note I made during lecture, it's just some terms for tree.

The harder part I found for this week's lecture was the different way to visit every node.(tree traversal)

1. pre-order traversal: visit root -> pre-order left subtree -> pre-order right subtree

Using the picture above, it would look like:

2 (root) -> 7 (left subtree)-> 2 -> 6 -> 5 -> 11 -> 5(right subtree) -> 9 -> 4 

2. in-order traversal: visit in-order left subtree -> root -> in-order right subtree

The picture above would look like:

2 (left subtree) -> 7 -> 5 -> 6 -> 11 ->2 (root) -> 5 (right subtree)-> 4 ->9

3. post-order traversal: visit post-order left subtree -> post-order right subtree -> root

The picture above would look like:

2 (left subtree) -> 5 -> 11 -> 6 -> 7 -> 4 (right subtree)-> 9 ->5 -> 2 (root)

It seems easy to mix up the three different way, I need to do more practice on this.

The prof also talked about how to write the code for the three traversal using recursion. They were all similar, only returned in different order. Plus he covered briefly about how to write a Tree class, which I believe is in our assignment 2.

Additional to the tree, I also checked the difference between "data type" and "data structure" as I mentioned.

I'm not 100% sure on this yet, so please comment if I've made any mistake.

- data structure is description of a way of organizing data. ex: trees, list, linked-list

- data type is the 'name' of the information that is stored. ex: data type 'integer' contains all the integers, list

- A linked tree(data strcture) is a group of nodes, and the nodes refer to values and other nodes.

(nodes are like id address over here, where every object has an id address. ex: 'apple' has an id3)

- As a data type, a tree has its children and value.

(this is similar to saying that there are no id address, so the object is signed directly without id. notice this is just an example, every object  has an id address with refer to a value)