Lesson 36 lab exercise BTree

Background:

In previous lessons you stored a data file, (file20.txt), in different data structures:  an array of structures, linked list, and doubly-linked list.  In the linked-list lab, we built the data structure, printed it out, searched for values, and deleted values.  We will solve the same fundamental tasks using a binary tree as the data structure.  You can build the binary tree in this first session, but the rest of the algorithms will be left as program stubs.

Instructions:  

1.   You may assume the following type definitions apply in this lab exercise:

struct treeNode

{

        int  id, inv;

        treeNode  *left, *right;

        treeNode (int, int, treeNode *, treeNode *);

};

treeNode::treeNode (int tempId, int tempInv, treeNode *tempLeft, treeNode *tempRight)

        : id (tempId), inv(tempInv), left(tempLeft), right(tempRight)

{

        // all values initialized using initializer list

}

typedef treeNode*  treePtr;

2.   Build a main menu with the following choices:

(1)     Read a file from disk, build the binary tree

(2)     Print the tree in order

(3)         Search the tree

(4)         Delete from the tree

(5)         Count the nodes in the tree

3.   Start with the source code for the ordered linked-list lab from Lesson 33.  The function readData will require small changes.  The algorithms inside of all the routines will change, but the basic structure of the program will not. 

4.   Complete the code for function insert.  A precondition of the insert routine; the data file will contain no duplicate id values.

5.   Stub the rest of the menu choices.

6.   You may compile and run this program, but you cannot verify if your insert algorithm worked until you learn the material in Lesson 37.  Use a data file as provided by your instructor.

7.   Turn in one final assignment when all the menu choices are completed in Lesson 38.