Tree Algorithms
wb_incandescentOverview
This module explores the exciting world of binary trees and their related algorithms for building, modifying, walking, searching, and sorting.
list Tree Reference
The following pages are extractions from "Introduction to Algorithms" by Cormen, Leisserson, Rivest, and Stein; MIT Press;(c)2009. These reprints are made under Educational Fair Use terms for noncommercial reuse in an educational context.
Cover of source text
list Exercise 1: Binary tree walks
Build the tree steps:
 Choose a topic/category of people, things, or events about which you can construct nodes keyed by a string and whose value is data of any kind. This example creates nodes representing nuclear power facilities in the US whose keys are the plant name and values are the megawatts of electrical energy generated. Explore the wikipedia entry.
 On cards or scraps of paper, generate about a dozen nodes: print the key on the front, and the value on the back.
 Shuffle your cards thoroughly
 Build a binary tree using the shuffled deck of nodes: place the first node as the root of your binary search tree. Then place the next card on the stack: if it comes before the root, place as the root's left child node; if it follows the root node in sort order, place it as the right child.
 Continue placing nodes and assembling your binary tree
Traverse the tree steps:
 Review the inorder tree traversal algorithm on the resources tab of this module.
 Diagram your recursive method calls on one sheet of paper, and record your theoretical program output on another sheet: simulate calling the inordertraversal(root r) on your root node and carefully move through the tree, tracking each nested method call on the stack.
 Prove that an inorder traversal of a correctly built binary search tree produces output in correct sort order!
Submission
Generate images of all your work. Visit our cloud drive root >> modtrees >> {create a folder with your public name and node topic}
Upload your images and rename them to sensible things.
Screen shots of inclass treebuilding exercise
list Building a tree in C++
Video of class session with instructor demo of traversal algorithm encoding
list Groups! Insert & Delete TreeNodes
Objective
Devise using pseudocode algorithms for inserting nodes in a binary search tree and deleting nodes in a binary search tree.
Translate the pseudocode into C++ code and squash bugs
Google doc group workspace
Open the tree algorithms google doc and navigate to your group's section using the table of contents.
Groupwork procedure
 Navigate in the google doc to your group number's section
 Introduce yourselves and share a personal connection to trees
 Start with the insertion algorithm: choose a recorder and a facilitator, the other members are "thinkers" for this algorithm
 Proceed through the subsections for insertion: declare the algorithms goals and outputs; write the pseudocode; compile a storage requirement list; hack out the C++
 Change roles for the deletion algorithm and work through the subsections.
list BST project specs
objective 
Model a treebased data structure in C++ and interact with that tree in various ways  
required organs 
Manually built treeInorder traversal 

insert/delete 
InsertWrite a function which, given a tree's root and a node to insert, locates the correct spot in the tree for the given node, and wires it up appropriately to parent/child DeleteWrite a function that given a tree's root and a node to delete, locates that node and removes it from the tree, correcting any linking necessary to preserve the remaining branches. 

optional: display tree structure 
Choose an appropriate walk algorithm that will allow you to easily display the nodes of a given tree onto the console as a vertically oriented diagram of connected nodes. Use clever characters to to the drawing of the linking lines. 

optional: array encoding 
As a challenge exercise, write a function that can encode your tree in one or more twodimensional arrays instead of node objects. Write a function to decode the arrays back into TreeNode objects. 

documentation 
Include comments above each method describing its key functionality. Include comments above or a the end of each unclear/important line of code. You should write all the code for your program, copying nothing from any other resource. If you use somebody else's code closelyi.e. using its essential structure but changing variable namesinclude a citation in your comments. 

work products 
For all project outcomes, please satisfy these criteria in preparation for building a professional work portfolio.
