Week 6: Trees

This week we mainly discussed trees (an abstract data type) and designed methods to work with the trees and their data. The example we did in last weeks lab (with the SearchList) makes more sense; I found that seeing just the nested list representation of a tree was not as useful to me as a graphic or the __repr__ representation for a Tree object that we coded in class. A tree basically is a hierarchical data structure with a “parent” node (the origin node at the very top is called the root node) on top with children (maximum of two children in the binary trees we looked at), and those children may have children as well. The parents/children are connected with edges, and each node (parent or child) can have a value/label associated with it. There is only one unique path between nodes and the height of the tree is the maximum number of edges between the root node and the bottommost one. The traversal methods that we coded were confusing to me at first, but I found out that these methods simply return the data within the tree in a certain order (preorder or postorder).

There is clearly an abundant use of recursion when working with trees, so the examples that we worked on in class helped me practice writing more recursive code. The readings posted on the website also made me realize the uses of trees. I finally finished the first assignment, with the recursive methods to solve the four stool Hanoi problem working at last. Also, my GUI also works properly now. I managed to code the bonus problem, and hopefully I did that right (the tests pass). The assignment was a challenge but it was an interesting problem and it helped me understand recursion better. I've also looked over past term tests and am beginning to review the course material more thoroughly. 

 

Graphic representation of a tree data structure. 

http://www.powayusd.com/pusdtbes/images/tree_example.gif