The Final Project is to develop a simple database system. The database is to handle multiple records, each composed of several fields. The database will store its information to a file, addition and deletion of records, field modifications, and it will allow users to sort records based on the selected keys, and produce reports (output) according to predefined criteria.

Some definitions:

A database is a collection of information, or data, that you can organize, update, sort, search through, and print as needed. A database does not just hold information; you use a database to organize and analyze information so that you understand its significance.

A database file consists of one or more records. Each record holds all the information about one subject item. In C++, the class data typeprovides an efficient way to represent and manipulate records.

Each piece of information in a record is called a field. Fields store the data that has been entered or calculated. In C++ parlance, fields are nothing more than the member variables defined for a particular class.

Given the requirements as a rough specification, you're supposed to design the class and implement the database. So you can consider the requirements below as an outcome from a meeting with a client. You are in full control of the choice of data structures (except the main data structure of AVL tree, more detail below), algorithms, internal file format, and detailed user interface scheme.

You're designing and implementing a database for an address book. Users should be able to browse, search their contacts, by any field (last name, first name, zip code etc.) from the database, and organize their chosen contacts to their liking and print out a report. Each contact information includes followings:

Unique ID number. ID is a 9 digit number

First name

Middle name (or initial)

Last name

Company name

Home phone

Office phone

Email

Mobile number

Street address

City

State

Zip code

Country

List of affiliates (such as family members or associates name). Each affiliate has first name, and last name. They may have one individual mobile phone number and one email. Note that all affiliates will share the rest of the contact info, and you need to make sure that the shared info is not duplicated. The total number of affiliates is unknown.

Requirements

Database overall management

Use a text based menu for users to choose available features. Program should have a main menu at the beginning and sub menus depending on the task.

You should allow users to read and write data to a text-based database file. The format of the text-based database file is following:

All information is stored in ASCII text format.

Records are divided by a | character

Each field is distinguished by a new line.

Submit a sample data file with at least 50 records. (Let's post at least 10 contacts (not necessarily real personal info, imaginary contacts) on the final project Q&A and share)

When reading from a data file, your program must test the input file to ensure that data is of valid format (basic error detection).

The database is primarily organized with the ID# as a key. You have to use AVL tree for the base data structure.

Each component of the overall program should be fairly modular.

Each menu item, for example, should be a separate function. The menu feature should be handled by a separate function and not by main( ).

Program should be fairly fault tolerant of user input (both when the user is entering data, and making menu choices). Provide appropriate user prompts and on-screen directions

Split the program into multiple files based on the roughly categorized functionality.

Data Retrieval and Modification

Users should be able to search records based on the field information in two modes: exact and contains. For example, search contacts by last name "Smith", search contacts with an email domain name that contains "ucdenver", etc. So in the search sub menu, users have to pick the search mode and field. Of course users should type in the search item.

Quite often, search may generate a relatively big output. Users should be able to search again within the search result (secondary search) or start all over again from scratch (new search).

Since the entire data is structures in a AVL tree with the ID# key, any search (except using ID#) should traverse the entire tree.

Users should be able to delete a record. So, in the delete record sub menu, users should be able to search and pick a delete candidate record. After deletion, the AVL tree should be rebalanced.

Users should be able to modify fields in a record, with the same condition above.

Users should be able to insert new records. There should be no restriction to the number of records in the database. So, in other words, you should not consider a fixed array for the record data structure.

Users can modify records, so the user should be able to write back to file (overwrite to current file or to a new file name similar to "save as").

Output Generation

Output generation is responsible for the re-organizing the final result to a user's liking by displaying appropriate fields and sorted records. The final output is a report in ASCII-text format.

After a series of data retrieval and modification, finally there is a list of contacts to be an output. Users should be able to further organize the contact and convey them to the output by choosing only the fields they want to print in desired order. So users should be able to pick fields to be finally shown in the output. And users should be able to sort the final output contacts by selecting a field as a key.

Users should be able to perform a secondary sorting with the second sort key (e.g., sort by company name, and then last name).

Output file generation in text file format.

Users should be able to generate a report output in ASCII text format. Note that this output file is different from the database file in ASCII text format.

Keep in mind that an output may not include all fields and records.

Submission Guideline

You need to submit following items (all zipped together):

Source code with reasonable comments

Makefile that works (and is tested) on the csegrid.

A final report that includes:

Summary of provided functions. This should be matched with the requirements

Design document that shows the overall program structures, and the explanation of key algorithms. A description of user interface scheme is required to explain the menu items at top level and items in sub menus and how to navigate through menus. A detailed instruction and sample skeleton is available from Design Document.

Accurate status of the program, what's done, and what's not completely implemented.

Accurate status of testing on the csegrid.

The final report should be in MS Word, or PDF format.

Note: You must use the following AVL code for your AVL tree. You may not use every function associated with this code. You should not need to change this code, but you will need to read it to see something that is included that may need to be added.

avlnode.cpp

avlnode.h

avltree.cpp

avltree.h

bstnode.cpp

bstnode.h

bstree.cpp

bstree.h

itemtype.h

and then a driver file to show you how to use these files:

avltest.cpp

Grading Criteria

Submitting a working program that provides all of the required features will result in a maximum grade of 80%.

Documentation explained above will result in 20% of the grade.

Any or all of the following will result in point deductions of up to 5% foreachinfraction.Poor and/or inconsistent programming style. This includes the following:

Improper use of indentation.

Overuse of global variables.

Failure to keep functions modular and reusable (possibly applicable to other programs).

Insufficient comments.

Insufficient menu prompts

Program is not reasonably( not absolutely) fault tolerant.

Test to ensure that your program cannot be crashed or sent into an infinite loop by a user who is not following directions.

Include a reasonable input file integrity check. Rejecting any non-conforming file is fine. You need to provide a sample database file with at least 50 records.

Partial credit may be awarded.

You may get partial credit for non-working modules (functions) by explaining (in the separate document) where you think the problem lies.

Up to 10% could be lost for each required feature that is not provided.

Submitting a program that does not compile on csegrid.ucdenver.pvt may result in a deduction of at least 30%. Additional points will be lost for each required feature that is not adequately addressed.

Q & A

Q: What's the input file format?

A: Something like this

ID# First name Middle name Last name Company name Home phone Office phone Email Mobile number Street address City State Zip code Country Affiliate name 1; (this can be family members, office affiliates, etc.) Affiliate name 2, own phone number, own email; Affiliate name 3; Affiliate name 4, own phone number, own email; (number of affiliates are unknown)

(each affiliate is delimited by ;. In case an affiliate has its own phone number and own email, those are delimited by comma , . )

|

next record starts here.

First name Middle name Last name....

For this final project, we can reasonably assume that every record has every field information. But just in case, for instance someone does not have a mobile number, fill up the field with "NULL" string.

Q: Assignment states that "A database file consists of one or more records." Does it mean that database is not allowed to be empty (zero records)?

A: Well, if there's no record, then it's not a database either. Allowing it as a database or not is a matter of a program design decision. You may think that you can create a database file first (building the structures) and add records one by one. But until it gets the first record, it doesn't serve as a database, except it has record structures. So I assume that there should be at least one record to make a database. You can make your program to take a database file with at least a record as an input parameter. Otherwise, it simply stops running.

Q: The following requirement seems backwards: Records are divided by a | characterEach field is distinguished by a new line. Shouldnt it be: FIELDS are divided by a | characterEach RECORD is distinguished by a new line.

A: No. If you put the entire record in one line, it could be very long and the word-wrap in a window would make the document very hard to read on typical text editors. Technically, there's nothing wrong with your scheme, though. But having a special character at the end of contact list (which is the end of the record) may make the programming a little easier.

Q: Should the final report be one document or a series of documents?

A: One MS word or pdf document.

Q: Do we need to give our users an ability to search on any field of the contacts? Should we also give the ability to search on everything including affiliates?

A: Yes, search (both exact and contain) function should be equally applied to all fields including affiliates. If your search function finds a target in the list of affiliates, assume that all main contact info is shared except for those people who have their own phone numbers and emails. For example, you're searching for a person with last name "Smith". The main database may not include someone with "Smith" but "Smith" could be found from affiliates of one or multiple records.

Q: Do we have to provide an infinite number of sub-searches? The assignment describes a requirement that we need to allow 1 sub-search. Do we have to have allow an infinite number of them?

A: Sub-searches, either it's the first level or further refined, should be same. Once you get the first search done, the current search result becomes another dataset from which you should be able to perform the first sub-search. Then the result of this routine should be in a same format just like the original search. So given the same format of dataset, you should be able to run the exactly same sub-searches, more like a recursion.

Q: The project says: Users should be able to search records based on the field information in two modes: exact and contains. For example, search contacts by last name "Smith", search contacts with an email domain name that contains "cudenver", etc. So in the search sub menu, users have to pick a search mode and field, as well as the search key. What a contact company is "first level technology" and the user typed "first technology" . Does "first level technology" contain "first technology" or not? Or, to be considered contained it has to be ether "first level" or "level technology" or "first level technology"?

A: I consider "first level technology" does not contain "first technology" since we're operating a string matching, not word by word containment relations.

Q: When a user modifies a record, can s/he change the number of affiliates on a particular contact? or only existing fields can be modified? Can the user delete a particular affiliate from the contact record?

A: Yes to both questions. Normally it's a super-user's job but for this project we consider all users have the privileges.

Q: what's the format of the report that to be displayed on the screen?

A: Table format with the column/row alignment is fine.

Q: When a user deletes records what happens to the affiliates?

A: Delete a record means delete an entire contact information including all affiliates.

Here are the code were given:

avlnode.cpp:

/* Filename: avlnode.cpp Programmer: Br. David Carlson Reference: Data Structures with C++, by Ford and Topp Date: October 12, 1997 This file defines the constructor for the class AVLNodeClass, which is set up in avlnode.h. */ #include "avlnode.h" /* Given: Item Data item to place in Info field. LeftPtr Pointer to place in Left field. RightPtr Pointer to place in Right field. BalanceValue Value to place in Balance field. Task: This is the constructor. It's job is to create a new object containing the above 4 values. Return: Nothing directly, but the implicit object is created. */ AVLNodeClass::AVLNodeClass(const ItemType & Item, AVLNodeClass * LeftPtr, AVLNodeClass * RightPtr, int BalanceValue): // call BSTNodeClass constructor, initialize field: BSTNodeClass(Item, LeftPtr, RightPtr), Balance(BalanceValue) { #ifdef DEBUG cout  
avlnode.h:
 
/* Filename: avlnode.h Programmer: Br. David Carlson Reference: Data Structures with C++, by Ford and Topp Date: October 12, 1997 Modified: June 9, 1999 to create AVLNodePtr type. This is the header file to accompany avlnode.cpp. It sets up the class AVLNodeClass as shown below. */ #ifndef AVLNODE_H #define AVLNODE_H #include "bstnode.h" class AVLNodeClass: public BSTNodeClass { private: int Balance; public: // constructor: AVLNodeClass(const ItemType & Item, AVLNodeClass * LeftPtr = NULL, AVLNodeClass * RightPtr = NULL, int BalanceValue = 0); friend class AVLClass; friend class AVLTableClass; // may not get to implementing this }; typedef AVLNodeClass * AVLNodePtr; #endif 
 
avltree.cpp:
 
/* Filename: avltree.cpp Programmer: Br. David Carlson Reference: Data Structures with C++, by Ford and Topp. Date: October 12, 1997 Revised: June 9, 1999 to use the type AVLNodePtr, to supply code for a copy constructor, and also to change each C-style cast to a reinterpret_cast. This file implements the functions of the AVLClass as set up in avltree.h. */ #include "avltree.h" /* Given: Item A data item to insert in a new node. LeftPtr A pointer to place in Left field of the new node. RightPtr A pointer to place in the Right field. BalanceValue A value to put in Balance field of the node. Task: To create a new node filled with the above 4 values. Return: A pointer to the new node in the function name. */ AVLNodePtr AVLClass::GetNode(const ItemType & Item, AVLNodeClass * LeftPtr, AVLNodePtr RightPtr, int BalanceValue) { AVLNodePtr NodePtr; #ifdef DEBUG cout  (Root)); Root = NULL; Count = 0; } /* Given: Current A pointer to a node in the implicit AVLClass object. Task: To wipe out all nodes of this subtree. Return: Nothing directly, but the implicit AVLClass object is modified. */ void AVLClass::ClearSubtree(AVLNodePtr Current) { // Use a postorder traversal: if (Current != NULL) { ClearSubtree(reinterpret_cast  (Current->Left)); ClearSubtree(reinterpret_cast  (Current->Right)); FreeNode(Current); } } /* Given: Tree An AVL tree. Task: To copy Tree into the current (implicit) AVL tree object. Return: Nothing directly, but the implicit AVL tree is modified. */ void AVLClass::CopyTree(const AVLClass & Tree) { #ifdef DEBUG cout  (Tree.Root)); Count = Tree.Count; } /* Given: Current Pointer to the current node of the implicit AVL tree. Task: To make a copy of the subtree starting at node Current. Return: A pointer to the root node of this copy. */ AVLNodePtr AVLClass::CopySubtree(const AVLNodePtr Current) { AVLNodePtr NewLeftPtr, NewRightPtr, NewParentPtr; // Once this section works, leave this out as it gives too much output: //#ifdef DEBUG // cout Left == NULL) NewLeftPtr = NULL; else NewLeftPtr = CopySubtree(reinterpret_cast  (Current->Left)); if (Current->Right == NULL) NewRightPtr = NULL; else NewRightPtr = CopySubtree(reinterpret_cast  (Current->Right)); NewParentPtr = GetNode(Current->Info, NewLeftPtr, NewRightPtr, Current->Balance); return NewParentPtr; } /* Given: ParentPtr A pointer to the node at which to rotate left. Task: To do a left rotation at the node specified above in the implicit AVL tree object. Return: ParentPtr Points to the new root node of the rotated subtree. Note that the implicit AVL tree is modified. */ void AVLClass::SingleRotateLeft(AVLNodePtr & ParentPtr) { AVLNodePtr RightChildPtr; #ifdef DEBUG cout Info  (ParentPtr->Right); ParentPtr->Balance = Balanced; RightChildPtr->Balance = Balanced; ParentPtr->Right = RightChildPtr->Left; RightChildPtr->Left = ParentPtr; ParentPtr = RightChildPtr; } /* Given: ParentPtr A pointer to the node at which to rotate right. Task: To do a right rotation at the node specified above in the implicit AVL tree object. Return: ParentPtr Points to the new root node of the rotated subtree. Note that the implicit AVL tree is modified. */ void AVLClass::SingleRotateRight(AVLNodePtr & ParentPtr) { AVLNodePtr LeftChildPtr; #ifdef DEBUG cout Info  (ParentPtr->Left); ParentPtr->Balance = Balanced; LeftChildPtr->Balance = Balanced; ParentPtr->Left = LeftChildPtr->Right; LeftChildPtr->Right = ParentPtr; ParentPtr = LeftChildPtr; } /* Given: ParentPtr A pointer to the node at which to double rotate left. Task: To do a double left rotation at the node specified above in the implicit AVL tree object. Return: ParentPtr Points to the new root node of the rotated subtree. Note that the implicit AVL tree is modified. */ void AVLClass::DoubleRotateLeft(AVLNodePtr & ParentPtr) { AVLNodePtr RightChildPtr, NewParentPtr; #ifdef DEBUG cout Info  (ParentPtr->Right); NewParentPtr = reinterpret_cast  (RightChildPtr->Left); if (NewParentPtr->Balance == LeftHeavy) { ParentPtr->Balance = Balanced; RightChildPtr->Balance = RightHeavy; // patched to fix bug in book } else if (NewParentPtr->Balance == Balanced) { ParentPtr->Balance = Balanced; RightChildPtr->Balance = Balanced; } else { ParentPtr->Balance = LeftHeavy; RightChildPtr->Balance = Balanced; } NewParentPtr->Balance = Balanced; RightChildPtr->Left = NewParentPtr->Right; NewParentPtr->Right = RightChildPtr; ParentPtr->Right = NewParentPtr->Left; NewParentPtr->Left = ParentPtr; ParentPtr = NewParentPtr; } /* Given: ParentPtr Pointer to the node at which to double rotate right. Task: To do a double right rotation at the node specified above in the implicit AVL tree object. Return: ParentPtr Points to the new root node of the rotated subtree. Note that the implicit AVL tree is modified. */ void AVLClass::DoubleRotateRight(AVLNodePtr & ParentPtr) { AVLNodePtr LeftChildPtr, NewParentPtr; #ifdef DEBUG cout Info  (ParentPtr->Left); NewParentPtr = reinterpret_cast  (LeftChildPtr->Right); if (NewParentPtr->Balance == RightHeavy) { ParentPtr->Balance = Balanced; LeftChildPtr->Balance = LeftHeavy; // patched to fix bug in book } else if (NewParentPtr->Balance == Balanced) { ParentPtr->Balance = Balanced; LeftChildPtr->Balance = Balanced; } else { ParentPtr->Balance = RightHeavy; LeftChildPtr->Balance = Balanced; } NewParentPtr->Balance = Balanced; LeftChildPtr->Right = NewParentPtr->Left; NewParentPtr->Left = LeftChildPtr; ParentPtr->Left = NewParentPtr->Right; NewParentPtr->Right = ParentPtr; ParentPtr = NewParentPtr; } /* Given: ParentPtr Pointer to parent node, whose subtree needs to be updated to an AVL tree (due to insertion). ReviseBalance Indicates if we need to revise balances. Assume: Subtree rooted at this parent node is left heavy. Task: To update this subtree so that it forms an AVL tree. Return: ParentPtr Points to the root node of the updated subtree. ReviseBalance Indicates if we need to revise balances. Note that the implicit AVL tree is modified. */ void AVLClass::UpdateLeftTree(AVLNodePtr & ParentPtr, bool & ReviseBalance) { AVLNodePtr LeftChildPtr; #ifdef DEBUG cout Info  (ParentPtr->Left); if (LeftChildPtr->Balance == LeftHeavy) { // left subtree is also left heavy SingleRotateRight(ParentPtr); ReviseBalance = false; } else if (LeftChildPtr->Balance == RightHeavy) { // right subtree is also right heavy DoubleRotateRight(ParentPtr); ReviseBalance = false; } } /* Given: ParentPtr Pointer to parent node, whose subtree needs to be updated to an AVL tree (due to insertion). ReviseBalance Indicates if we need to revise balances. Assume: Subtree rooted at this parent node is right heavy. Task: To update this subtree so that it forms an AVL tree. Return: ParentPtr Points to the root node of the updated subtree. ReviseBalance Indicates if we need to revise balances. Note that the implicit AVL tree is modified. */ void AVLClass::UpdateRightTree(AVLNodePtr & ParentPtr, bool & ReviseBalance) { AVLNodePtr RightChildPtr; #ifdef DEBUG cout Info  (ParentPtr->Right); if (RightChildPtr->Balance == RightHeavy) { // right subtree is also right heavy SingleRotateLeft(ParentPtr); ReviseBalance = false; } else if (RightChildPtr->Balance == LeftHeavy) { // right subtree is also left heavy DoubleRotateLeft(ParentPtr); ReviseBalance = false; } } /* Given: Tree Pointer to node of implicit AVL tree. This node is the root of the subtree in which to insert. NewNodePtr Pointer to the new node to be inserted. ReviseBalance Indicates if we need to revise balances. Task: To insert the new node in the subtree indicated above. Return: Tree Pointer to the root node of the subtree. ReviseBalance Indicates if we need to revise balances. Note that the implicit AVL tree object is modified. */ void AVLClass::AVLInsert(AVLNodePtr & Tree, AVLNodePtr NewNodePtr, bool & ReviseBalance) { bool RebalanceCurrentNode; #ifdef DEBUG if (Tree == NULL) cout Info Info Info Balance = Balanced; ReviseBalance = true; // tell others to check balances due to new node } else if (NewNodePtr->Info Info) { AVLInsert(reinterpret_cast  (Tree->Left), NewNodePtr, RebalanceCurrentNode); if (RebalanceCurrentNode) { if (Tree->Balance == LeftHeavy) // now 1 node worse than this UpdateLeftTree(Tree, ReviseBalance); else if (Tree->Balance == Balanced) // was balanced, now 1 extra { Tree->Balance = LeftHeavy; ReviseBalance = true; } else // was right heavy, due to extra node on left now balanced { Tree->Balance = Balanced; ReviseBalance = false; } } else ReviseBalance = false; } else { AVLInsert(reinterpret_cast  (Tree->Right), NewNodePtr, RebalanceCurrentNode); if (RebalanceCurrentNode) { if (Tree->Balance == LeftHeavy) // extra node on right balances it { Tree->Balance = Balanced; ReviseBalance = false; } else if (Tree->Balance == Balanced) // now 1 node heavy on right { Tree->Balance = RightHeavy; ReviseBalance = true; } else // was right heavy, now off by 2 on right, must fix: UpdateRightTree(Tree, ReviseBalance); } else ReviseBalance = false; } } /* Given: Nothing. Task: This is the default constructor for creating the implicit AVL tree object. Return: Nothing directly, but the implicit AVL tree object is created. */ AVLClass::AVLClass(void) { // just use the automatic BSTClass default constructor #ifdef DEBUG cout  (Root), NewNodePtr, ReviseBalance); Count++; } 
 
avltree.h:
 
/* Filename: avltree.h Programmer: Br. David Carlson Reference: Data Structures with C++, by Ford and Topp. Date: October 12, 1997 Revised: June 9, 1999 to use the type AVLNodePtr. This is the header file to accompany avltree.cpp. It sets up the class AVLClass as shown below. Note that the following functions are not overwritten, so that in any reference to them, these mean functions of the BSTClass: SubtreeFind, PrintSubtree, NumItems, Empty, Find, Print. */ #ifndef AVLTREE_H #define AVLTREE_H #include "avlnode.h" #include "bstree.h" const int LeftHeavy = -1; const int Balanced = 0; const int RightHeavy = 1; class AVLClass: public BSTClass { private: AVLNodePtr GetNode(const ItemType & Item, AVLNodePtr LeftPtr = NULL, AVLNodePtr RightPtr = NULL, int BalanceValue = 0); void CopyTree(const AVLClass & Tree); AVLNodePtr CopySubtree(const AVLNodePtr Current); void SingleRotateLeft(AVLNodePtr & ParentPtr); void SingleRotateRight(AVLNodePtr & ParentPtr); void DoubleRotateLeft(AVLNodePtr & ParentPtr); void DoubleRotateRight(AVLNodePtr & ParentPtr); void UpdateLeftTree(AVLNodePtr & ParentPtr, bool & ReviseBalance); void UpdateRightTree(AVLNodePtr & ParentPtr, bool & ReviseBalance); void AVLInsert(AVLNodePtr & Tree, AVLNodePtr NewNodePtr, bool & ReviseBalance); void FreeNode(AVLNodePtr NodePtr); void ClearTree(void); void ClearSubtree(AVLNodePtr Current); public: AVLClass(void); AVLClass(const AVLClass & Tree); ~AVLClass(void); AVLClass & operator= (const AVLClass & Tree); void Insert(const ItemType & Item); // Some sort of Remove method could also be added, but it would // take effort to remake the AVL tree after the deletion of a node. }; #endif 
 
bstnode.cpp:
 
/* Filename: bstnode.cpp Programmer: Br. David Carlson Date: October 10, 1997 Modified: August 8, 1998. This file implements the class functions for the BSTNodeClass, which is declared in bstnode.h. Since no code is needed for the constructor, only the GetInfo function is found here. */ #include "bstnode.h" /* Given: Nothing other than the implicit object. Task: To look up the Info field of the object. Return: A copy of this data in TheInfo. */ void BSTNodeClass::GetInfo(ItemType & TheInfo) const { TheInfo = Info; // assumes assignment works on this type } 
 
bstnode.h
 
/* Filename: bstnode.h Programmer: Br. David Carlson Date: October 10, 1997 Revised: August 8, 1998 Revised: June 9, 1999 to use protected, not private, data fields. This is so that a derived class can directly access them. An alternate solution would be to make any derived class (such as AVLNodeClass) a friend of this class. This file was also revised to make AVLClass a friend of this class, so that it would have easy access to the data fields. This is the header file to accompany bstnode.cpp. It provides the BSTNodeClass shown below as well as the BSTNodePtr type. */ #ifndef BSTNODE_H #define BSTNODE_H #include "itemtype.h" class BSTNodeClass { protected: ItemType Info; BSTNodeClass * Left, * Right; public: BSTNodeClass(const ItemType & Item, BSTNodeClass * LeftPtr = NULL, BSTNodeClass * RightPtr = NULL): Info(Item), Left(LeftPtr), Right(RightPtr) { }; void GetInfo(ItemType & TheInfo) const; friend class BSTClass; friend class AVLClass; }; typedef BSTNodeClass * BSTNodePtr; #endif 
 
bstree.cpp
 
/* Filename: BSTree.cpp Programmer: Br. David Carlson Date: October 10, 1997 Modified: August 8, 1998. Modified: June 9, 1999 so that ClearTree only tries to do any work if the root pointer is non-null. This file implements the functions for the BSTClass as set up in the header file bstree.h. */ #include "bstree.h" /* Given: Nothing, Task: This is the constructor to initialize a binary search tree as empty. Return: Nothing directly, but it creates the implicit BSTClass object. */ BSTClass::BSTClass(void) { Root = NULL; Count = 0; } /* Given: Nothing (other than the implicit BSTClass object). Task: This is the destructor. It's job is to wipe out all data storage used by this binary search tree. Return: Nothing directly, but the implicit BSTClass object is destroyed. */ BSTClass::~BSTClass(void) { ClearTree(); } /* Given: Nothing (other than the implicit BSTClass object). Task: To clear out all nodes of the implicit binary search tree. Return: Nothing directly, but the implicit BSTClass object is modified to be an empty binary search tree. */ void BSTClass::ClearTree(void) { if (Root != NULL) { ClearSubtree(Root); Root = NULL; Count = 0; } } /* Given: Current A pointer to a node in the implicit BSTClass object. Task: To wipe out all nodes of this subtree. Return: Nothing directly, but the implicit BSTClass object is modified. */ void BSTClass::ClearSubtree(BSTNodePtr Current) { // Use a postorder traversal: if (Current != NULL) { ClearSubtree(Current->Left); ClearSubtree(Current->Right); FreeNode(Current); } } /* Given: Item A data item to place into a new node. LeftPtr The pointer to place in the left field of the node. RightPtr The pointer to place in the right field of the node. Task: To create a new node containing the above 3 items. Return: A pointer to the new node. */ BSTNodePtr BSTClass::GetNode(const ItemType & Item, BSTNodePtr LeftPtr, BSTNodePtr RightPtr) { BSTNodePtr NodePtr; NodePtr = new BSTNodeClass(Item, LeftPtr, RightPtr); if (NodePtr == NULL) { cerr  0) return false; else return true; } /* Given: Item A data item to be inserted. Task: To insert a new node containing Item into the implicit binary search tree so that it remains a binary search tree. Return: Nothing directly, but the implicit binary search tree is modified. */ void BSTClass::Insert(const ItemType & Item) { BSTNodePtr Current, Parent, NewNodePtr; Current = Root; Parent = NULL; while (Current != NULL) { Parent = Current; if (Item Info) Current = Current->Left; else Current = Current->Right; } NewNodePtr = GetNode(Item, NULL, NULL); if (Parent == NULL) Root = NewNodePtr; else if (Item Info) Parent->Left = NewNodePtr; else Parent->Right = NewNodePtr; Count++; } /* Given: Item A data item to look for. Task: To search for Item in the implicit binary search tree. Return: A pointer to the node where Item was found or a NULL pointer if it was not found. */ BSTNodePtr BSTClass::Find(const ItemType & Item) const { return SubtreeFind(Root, Item); } /* Given: Current A pointer to a node in the implicit binary search tree. Item A data item to look for. Task: To search for Item in the subtree rooted at the node Current points to. Return: A pointer to the node where Item was found or a NULL pointer if it was not found. */ BSTNodePtr BSTClass::SubtreeFind(BSTNodePtr Current, const ItemType & Item) const { if (Current == NULL) return NULL; else if (Item == Current->Info) return Current; else if (Item Info) return SubtreeFind(Current->Left, Item); else return SubtreeFind(Current->Right, Item); } /* Given: NodePtr A pointer to the root of the subtree to be printed. Level Integer indentation level to be used. Task: To print (sideways) the subtree to which NodePtr points, using an indentation proportional to Level. Return: Nothing. */ void BSTClass::PrintSubtree(BSTNodePtr NodePtr, int Level) const { int k; if (NodePtr != NULL) { PrintSubtree(NodePtr->Right, Level + 1); for (k = 0; k Info Left, Level + 1); } } /* Given: Nothing (other than the implicit object). Task: To print (sideways) the implicit binary search tree. Return: Nothing. */ void BSTClass::Print(void) const { PrintSubtree(Root, 0); } 
 
bstree.h
 
/* Filename: bstree.h Programmer: Br. David Carlson Date: October 10, 1997 Modified: August 8, 1998. Modified: June 9, 1999 to make AVLClass a friend of BSTClass. This is the header file to accompany bstree.cpp. It provides the BSTClass as shown below. */ #ifndef BSTREE_H #define BSTREE_H #include "bstnode.h" class BSTClass { private: BSTNodePtr GetNode(const ItemType & Item, BSTNodePtr LeftPtr = NULL, BSTNodePtr RightPtr = NULL); void FreeNode(BSTNodePtr NodePtr); void ClearTree(void); void ClearSubtree(BSTNodePtr Current); BSTNodePtr SubtreeFind(BSTNodePtr Current, const ItemType & Item) const; void PrintSubtree(BSTNodePtr NodePtr, int Level) const; // The following data fields could be made protected instead of // private. This would make them accessible to the derived AVLClass // without making AVLClass a friend of BSTClass. BSTNodePtr Root; int Count; public: BSTClass(void); ~BSTClass(void); int NumItems(void) const; bool Empty(void) const; void Insert(const ItemType & Item); // Some sort of Remove method could also be added, but // it would require effort to remake the binary search tree // after the deletion of a node. BSTNodePtr Find(const ItemType & Item) const; void Print(void) const; friend class AVLClass; }; #endif 
 
itemtype.h
 
/* Filename: itemtype.h Programmer: Br. David Carlson Date: October 10, 1997 Modified: June 26, 2000 to use modern headers. This header file defines ItemType for use in bstnode.h. It also should be set up to define DEBUG if you want debugging output statements to be compiled. */ #ifndef ITEMTYPE_H #define ITEMTYPE_H #include  using namespace std; // Comment off the following line to omit debugging output statements: #define DEBUG // Customize the following as needed: typedef char ItemType; #endif 
 
and then a driver file to show you how to use these files:
 
avltest.cpp
 
/* Filename: avltest.cpp Programmer: Br. David Carlson Reference: Data Structures with C++, by Ford and Topp Date: October 10, 1997 Modified: June 9, 1999 to use AVLNodePtr type and also to change each C-style cast to a reinterpret_cast. Modified: June 26, 2000 to use modern headers. (See itemtype.h in particular.) Modified: April 21, 2001 to add the Pause function. Last Modified: December 23, 2001 This program inserts some hard-coded data (chars) into an AVL tree. It then tests the following functions by calling them and reporting the results on the screen: Find, NumItems, the overloaded = operator, the copy constructor, and Print. To compile this program in Visual C++, make sure that the project contains: avltest.cpp, bstnode.cpp, bstree.cpp, avlnode.cpp, avltree.cpp, bstnode.h, bstree.h, avlnode.h, avltree.h, and itemtype.h. In itemtype.h leave DEBUG defined if you want extra debugging output, or comment it off to omit such output. Tested with: Microsoft Visual C++ 6.0 Microsoft Visual C++ .NET g++ under Linux */ #include "avltree.h" void Pause(void); int main(void) { AVLClass AVLTreeA, AVLTreeB; AVLNodePtr Result; AVLTreeA.Insert('F'); AVLTreeA.Insert('B'); AVLTreeA.Insert('W'); AVLTreeA.Insert('M'); AVLTreeA.Insert('E'); AVLTreeA.Insert('A'); AVLTreeA.Insert('C'); cout  (AVLTreeA.Find('E')); if (Result == NULL) cout  (AVLTreeA.Find('D')); if (Result == NULL) cout  (AVLTreeB.Find('E')); if (Result == NULL) cout  (AVLTreeC.Find('W')); if (Result == NULL) cout