Summary
The structure of a tree can itself be “information” with which to associate data that it stores. This is typically in the form of hierarchical data, but it can also be thought of as a “subtree” having more in common than another “subtree” in another part of the tree. Explore various ways of doing tree traversals on a set of data stored by your own implementation of a tree.
Skills Expected
Linked Structures
Tree ADT
Tree Traversals
Assignment Description
Create a binary tree data structure used to keep track of data (e.g. an int).
Implement the following traversal functions:
Pre-Order Traversal
Post-Order Traversal
In-Order Traversal
Grading Criteria
Implementation
[3 Points] Binary Tree (Doesn’t have to be sorted) data structure
[6 Points] Pre-Order Traversal
[6 Points] Post-Order Traversal
[6 Points] In-Order Traversal
Demonstration (Driver)
Three different trees to traverse (containing at least 10 items each)
[2 Points] A “left-unbalanced” tree to traverse
[2 Points] A “right-unbalanced” tree to traverse
[2 Points] A “symmetrical” tree to traverse
On each of the three different trees to traverse, demonstrate:
[1 Point] Pre-Order Traversal
[1 Point] Post-Order Traversal
[1 Point] In-Order Traversal
[3 Points Extra Credit] Breadth-first search (and demonstration)
