Week 7 - Abstract Data Structures

Throughout the course many Abstract Data Structures have been introduced. In csc108 we used the built in list and dictionary data types. These were simple ways of storing information. In csc148, we have been introduced to many more ways of storing information for use. One of the first was the Stack abstract data structure. A stack can have the top (aka end) item added and removed, but the other items in the stack cannot be modified. This structure seemed to be useful in very specific situations but not useful for most situations I can think of.

The second abstract data structure introduced was the Tree data structure. A Tree structure has a root node  with leaf nodes branching out as the root nodes children. Those leaves can then become roots themselves by adding more leaves to any leaf node. A Tree structure can become very complicated very quickly, depending on the number of children and in turn their children. Using recursion the tree can be traversed going down the roots to the leaves, and back up into the roots until all nodes have been visited.

The most recent abstract structure was the Binary Tree. A binary tree is similar to the tree structure, involving roots and leaves, however a binary tree can only have up to two children. Each root node can have a left and right child. This keeps the binary tree more structured than a regular tree structure. When ordering a binary tree values are ordered by greater than or less than the node. If the value you want to add is greater than the node you are in, move to the right child. If it is less move to the left child. If the left or right child exists then compare your value to the current node and repeat the process. When there is no left or right child then the value becomes the new child. A binary tree structure is a very helpful way to store items when you need to find a particular item quickly. This is because you can compare if the item you are looking for is greater or less than the node you are on, and search through the structure that way.
The class was taught three different ways of visiting each node: in-order, pre-order, and post-order. When visiting in-order, move down to the left child until the left child is empty. Then visit the left child you are on, then back up to the node, then the right child. Then move back up to the next node and continue through the rest of the tree. The method for visiting in pre-order involves visiting the node itself, then the left child, then the right child. This continues through the tree without visiting the same node twice. In post-order the left child is visited, then the right child is visited, then finally the node itself is visited.

This is my summary of the Abstract Data Types covered thus far. Hopefully other students can have a better understanding with this,