Computer Programming II

Lab 6 - Binary Search Tree

Program Due: Last day of class (But you should do it earlier!)

PROBLEM: You are to write a program in C++ to create binary search trees. Search trees are described in your textbook. You must read in a body of text from a file. Use a text file such as a readme.txt, or a short story, article, term paper, etc. Or you might try pulling some text file down from the Internet. The file should have at least 100 unique words in it. Read it in and break it down to words and store each of the words in a tree. Eliminate all punctuation and ignore case. Any repeated words should be counted, without new nodes being added.

After reading in the file and building the tree, print out the postorder, inorder and preorder traversals of the tree. Print the words in columns, 4 per line. Your traversals should print out the word for each node and the word count for that node.

For the entire tree, give the depth of the complete tree and the node count. Calculate the total number of nodes possible if the tree were fully fleshed out. Now, using the node count, report on the percentage of possible nodes for a tree of this depth that are used by your tree.

Last, allow the user to type in sentences and spellcheck them using your tree with a recursive binary search for each word.

Small Example:

Infix Traversal:

ate:1 cat:1 dog:1 leashed:1

rabid:1 the:2 whole:1

Depth of tree: 4

Total used nodes: 7

Total possible nodes: 15

Percentage of nodes used:47%

IMPLEMENTATION: You must first create a binary ADT class with a string value field for each node in the tree. This ADT should include all three traversal functions (inorder, postorder, preorder), depth, nodecount, addnode, search, create, destroy (traversal with deletes) empty and full.

Design: Hand in your design with your program. No separate design document is required.