All of the work in this project is my/our own! I/We have not left copies of my code in public folders on university computers. I have not given any of this project to others. I will not give any portion of this project to others taking this class. I realize that the penalty for turning in work that is not my own can range from an "F" in the class to dismissal from Trinity University.
Print Title ______________________________________ Time Required = ______.____ Hrs.
Signature ______________________________________ (pledged)
Print Title ______________________________________ Time Required = ______.____ Hrs.
Signature ______________________________________ (pledged)
__________ {T/F} The Delete tree function works well; it does not call function Delete.
__________ {T/F} The NoNodesAtEachLevel function works well.
__________ {T/F} The DisplayLoadBalanceStatistics function works well.
__________ {T/F} The Delete function works well.
__________ {T/F} I/We Used the Delete and Re-connect Option for Deletion.
__________ {T/F} I/We Used the Bubble Up Algorithm for Deletion.
__________ {T/F} I/We created a
functional ReBalanceTree Function.
void RebalanceTree (long int HeaderNo)
DA_BinTree
# 2 Lab
Delete & DeleteTree
NoNodes At Each Level &
Stats
Individual/ Team
70 Points
1] Write and test DeleteTree and Delete. Uncomment out and test diagnostic levels 30 - 39. Examine the test data and output carefully. You may not call function Delete; use a traversal!
2] You may not use "Lazy Deletion". You must physically remove the nodes from the tree. Extra Credit for an approach that does not extend the size of the tree.
3] I am hoping that all of you go for the extra credit. I have extended the deadlines two days to ensure that. My test module assumes that you are working on the extra credit. Modify levels 30-34 to successfully test for your solution (if necessary).
void TestDA_BinTree4(void);
////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////// // DeleteTree // // // // Purpose : Return all of the nodes in the header to the available pool. // // The header should be as a new, unused, blank header. // // The data from each of the nodes must be in the available pool for // // undelete. // // // // ----------------------------- // // | | 0 | / | // // ----------------------------- // // // // Written By : xxxxxxxxxxxxxxxxx Environment : Windows XXXXXX // // Date : XX/XX/XXXX Compiler : .Net 2008 [C++] // ////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////// // DeleteTreeHelper // // // // Purpose : Recursively deletes a tree by running a post-order traversal. // // // // Written By : xxxxxxxxxxxxxxxxx Environment : Windows XXXXXX // // Date : XX/XX/XXXX Compiler : .Net 2008 [C++] // ////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////// // Delete // // // // Purpose : You may not use lazy deletion. If you use a bubble-up algorithm // // which helps preserve the tree structure, you may earn 100% credit. // // If you use the extend level algorithm, you may earn only 80% // // credit. // // You will have to search the tree. If the node is not on the tree, // // return UNSUCCESSFUL. // // The data from each of the nodes must be in the available pool for // // undelete. // // // // Written By : xxxxxxxxxxxxxxxxx Environment : Windows XXXXXX // // Date : XX/XX/XXXX Compiler : .Net 2008 [C++] // ////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////
4] Modify your three traversals in such a way that they do not display nodes if the Delete flag is true.
5] Make sure that you update the comment box of all functions (down to TestTreeIntegrity). Update the Written By, Environment, and Date.
6] Make sure that when information has been deleted, that it appears in the available pool for un-deletion. The DA_DLList shown below, had the values 1-10 in various headers at one time. All ten of the records were deleted. Note that the update in the header was effective; all #NoNodes =0. Note that any one of the values 1-10 could be recovered from the avail pool.
=========================================================================
| Title | #Nodes | Root |
=========================================================================
3 | No-3 | 0 | 0 |
=========================================================================
2 | No-2 | 0 | 0 |
=========================================================================
1 | No-1 | 0 | 0 |
=========================================================================
0 | | 0 | 0 |
=========================================================================
------------------------------------------------------------------------
| Left | Info |Del| Right|
------------------------------------------------------------------------
10 | 0 | 10 | T | 1 |
------------------------------------------------------------------------
9 | 0 | 2 | T | 2 |
------------------------------------------------------------------------
8 | 0 | 8 | T | 0 |
------------------------------------------------------------------------
7 | 0 | 1 | T | 6 |
------------------------------------------------------------------------
6 | 7 | 3 | T | 4 |
------------------------------------------------------------------------
5 | 0 | 6 | T | 8 |
------------------------------------------------------------------------
4 | 0 | 7 | T | 3 |
------------------------------------------------------------------------
3 | 4 | 9 | T | 5 |
------------------------------------------------------------------------
2 | 9 | 4 | T | 7 |
------------------------------------------------------------------------
1 | 0 | 5 | T | 9 |
------------------------------------------------------------------------
| 0 | 0 | T | 10 |
------------------------------------------------------------------------
Avail = 10
long int TempCounter; long int LevelNo, NoNodes[5001];
1] TempCounter, NoNodes, and LevelNo are declared in the class so that they will be available to all functions.
2] Traverse the tree. NoNodes[1] is to contain the number of nodes at level 1 of the tree {0 if empty, else 1}. NoNodes[2] is to contain the number of nodes at level 2 of the tree {0,l 1, or 2}.
3] Each time you start your
traversal, you will want to make sure that the NoNodes contains all zeros.
Consider InitializeNoNodes().
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//
InitializeNoNodes
//
//
//
// Purpose : Assign 0 to each and every element in Array NoNodes.
//
//
//
// Written By : Dr. Thomas E. Hicks
Environment : Windows XXXXXX //
// Date : XX/XX/XXXX
Compiler : Visual Net [C++] //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
template <class HeaderType, class InfoType>
void DA_BinTree <HeaderType, InfoType> ::InitializeNoNodes()
{
long int
Pos;
for (Pos = 0; Pos <= 5000; Pos ++)
NoNodes[Pos]= 0;
}
4] Just in case you make a
mistake, you will want to examine the values in NoNodes . Consider
DisplayNoNodes().
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//
DisplayNoNodes
//
//
//
// Purpose : Graphical display of the NoNodes array; display at least 6 levels.
//
//
//
// Written By : Dr. Thomas E. Hicks
Environment : Windows XXXXXX //
// Date : XX/XX/XXXX
Compiler : Visual Net [C++] //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
template <class HeaderType, class InfoType>
void DA_BinTree <HeaderType, InfoType> ::DisplayNoNodes(char Message [] )
{
long int
Pos,
NoLevelsToDisplay;
NoLevelsToDisplay = 5000;
while ((NoLevelsToDisplay >= 6) && (NoNodes[NoLevelsToDisplay] == 0))
NoLevelsToDisplay = NoLevelsToDisplay -1;
for (Pos = NoLevelsToDisplay; Pos >= 1; Pos --)
{
printf(" |--------|\n");
printf ("%6ld | %6ld | \n", Pos, NoNodes[Pos]);
}
printf(" |--------|\n\n");
}
5] Write the code for the
traversal.
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//
NoNodesAtEachLevelTraversalDisplay
//
//
//
// Purpose : Display the message, if any. Set the LevelNo to 0.
//
// InitializeNoNodes.
Evoke the recursive NoNodesAtEachLevelHelper //
// helper function.
DisplayNoNodes array.
//
//
//
// Written By : Dr. Thomas E. Hicks
Environment : Windows XXXXXX //
// Date : XX/XX/XXXX
Compiler : Visual Net [C++] //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
template <class HeaderType, class InfoType>
void DA_BinTree <HeaderType, InfoType> ::NoNodesAtEachLevelTraversalDisplay
(long int HeaderNo, char Message[])
{
HeaderType
Header;
}
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//
NoNodesAtEachLevelHelper
//
//
//
// Purpose : Traverse the tree. As you go down the tree you will have to
//
// increment the
LevelNo [LevelNo++]. As you go back up the tree you //
// will have to
decrement the LevelNo[LevelNo--]. It will be during //
// the visit stage
of the traversal that you need to update array //
// NoNodes to
reflect an increase in the number of nodes at that
//
// particular
LevelNo. Hint! [NoNodes[LevelNo]++].
//
//
//
// Written By : Dr. Thomas E. Hicks
Environment : Windows XXXXXX //
// Date : XX/XX/XXXX
Compiler : Visual Net [C++] //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
template <class HeaderType, class InfoType>
void DA_BinTree <HeaderType, InfoType> ::NoNodesAtEachLevelHelper(NodePtr Ptr)
{
DLNode <InfoType>
Node;
}
6] Write the code for DisplayLoadBalanceStatistics() which is to traverse the tree and display
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//
DisplayLoadBalanceStatistics
//
//
//
// Purpose : Call NoNodesAtEachLevelTraversalDisplay; this will fill Array
//
// NoNodes with the
node distribution info for that specific header. //
// Once you have the
distribution, the Array can be used to calculate //
// the needed
statistics for this module. Make sure you display the //
// optional message
and then display:
//
//
//
// No Nodes
........= xxxxxxxxxxxx
//
// No Levels
.......= xxxxxxxxxxxx
//
// Average Search
..= xxxxxx.xx
//
//
//
// Written By : Dr. Thomas E. Hicks
Environment : Windows XXXXXX //
// Date : XX/XX/XXXX
Compiler : Visual Net [C++] //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
template <class HeaderType, class InfoType>
void DA_BinTree <HeaderType, InfoType> ::DisplayLoadBalanceStatistics(long int
HeaderNo, char Message[])
{
long int
LevelNo,
SearchTotal,
NoLevels,
TotalNodes;
// printf ("No Nodes ........= %ld\n", TotalNodes);
// printf ("No Levels .......= %ld\n", NoLevels);
// printf ("Average Search ..= %.2f\n",double(SearchTotal)/TotalNodes);
}
7] Test Diagnostic Levels 17-22. Examine the output carefully and make sure that all work.
8] Set the diagnostic level to 22. Compile your program. It should take it a while to execute.
9] When you are convinced that your program is working correctly, place a copy of this folder (1) in your "To Be Graded Folder" On Ananke (2) on you Y drive and (3) on your personal computer.
10] Change the Written By in all functions, except the three diagnostic Display functions, to you. Update all of the documentation boxes (i.e. Date, Environment, Compiler, Written By).
1] Those Labs labeled "Individual Assignment" are to be done separately by each individual. Using a pen, each individual is to print his/her name at the top of this document in the space provided and sign it. Those Labs labeled "Team Assignment" may be done as a team or individually. Using a pen, each individual on the team is to print print his/her name at the top of this document in the space provided and sign it. Submit only one copy of team assignments!
A] Copy of first page of this lab assignment sheet. Using an ink pen, print your name and sign this lab at the top.
B] Make sure that all of the Documentation is accurate - Your Name - Date - Etc. on anything you coded.
C] Copy folder DA-BinTree-2-First-Last to Ananke when you submit this lab.
D] Nothing will be graded until this lab form is submitted. Staple the pages. Fold the lab Horizontally (like a hot dog) and write your name nice and large on the outside. Place it on the professor desk before the beginning of lecture on the day it is due. All assignments are due the next class period unless otherwise designated on the schedule page.