6.2: Coding Drill: List of Binary Trees
This exercise uses both binary trees and linked lists. It first builds a binary tree to represent text. The nodes of the tree represent the words of the text. In this representation, the alphabetical order of the words is used to determine whether a word is placed using the right branch or the left branch of a node. For example, if the first word begins with an f and the second word begins with an s, then the second word would be stored as the right descendant of the node for the first word. Once the structure of the binary tree is defined, functions can be created that operate on the binary tree structure. To test your code, this example uses Lincoln's Gettysburg Address. Two links in left hand column ("Gettysburg Address" and "Gettysburg, just the words") help you visualize the input data and the resulting binary tree. Note that binary trees are useful for storing data in a manner that facilitates searching that data. For this reason, data is put into the binary tree in a specific order. Note also, that some of the illustrations on this page may use C instead of C++. However, this link is intended to help you come up with a plan for solving the problem; use your knowledge of C++ learned in this course to code the problem. In summary, to solve the problem: 1) understand the requirements of the problem (i.e. what you have to do); 2) design a solution to solve the problem, including a data structure and procedures or functions that operate on the data structure; 3) code your design in C++; and 4) test your code using the "Gettysburg Address" found on the linked page above. Once the binary tree representation of the text is built, the next part of the assessment is to create a linked list that will visit the nodes of the binary tree, i.e. walk the tree in such a way that you visit the nodes in the order in which the test is read, e.g. "Four score and seven years ago, our forefathers..." The binary tree representation stores the words of the text using an alphabetical order. The link list represents the reading order of the words as they appear in the text.