Our primary topic for this week was the introduction of binary trees. This is a special type of object, and one that ties closely to the concept of recursion. Binary trees are defined recursively in terms of parents and children, filling in levels of the tree from root through branches down to leaves. This type of data structure can be a useful one for search and sort algorithms, as well as being more practical than a linked list (in most cases) for relating pieces of data to one another, especially since most of the linked lists we've used have only been able to refer to itself and a "next" value, and I don't think it would be possible to construct a type of linked list such that it would refer to anything more than two values (previous and next).
With trees on the other hand, referring to the parent and children provides a possibility of at least 3 references for a node with 2 children, and if we were to construct a tree that allowed for more than 2 children an even larger web of references would be possible.
Furthermore, traversal of trees is best accomplished recursively. We have looked at inorder, preorder, and postorder traversals of binary trees, and it's been fairly easy to see the potential applications of each. Postorder seems like it would be the least used, although still relevant depending on the case. What is important to realize is that as much as we are learning new things about computer science, we are also learning new ways to look at, think about, and process the things we already know how to do.
No comments:
Post a Comment