All of the work in this project is my own!  I 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 Name  __________________________    Time Required = ______.____ Hrs.

                                    Signature   __________________________

                                    Print Name  __________________________    Time Required = ______.____ Hrs.

                                    Signature   __________________________

In  ______________________________________'s folder on Ananke

AVL Direct Access Lab
Individual Assignment
100  Points
Will not be accepted after 5/1/2006 Noon

1] Copy folder DA_AVL_Tree to DA_AVL_Tree2.  I would like you to make sure that file DA_AVLTreee.hpp includes the class definition included below.

 //////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//                                DA_AVLTree.hpp                                //
//                                                                              //
// Purpose    : Direct Access file implementation of the standard binary        //
//              search tree. Duplicates are allowed.                            //
//                                                                              //
// Written By : ???????????????????               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////

#ifndef DA_AVLTREE //======================================================

// ----------------------------------- Includes ----------------------------------

# include "Utilities.hpp"
# include "AVLNode.hpp"
# include "TreeHeader.hpp"
# include "Stack.hpp"  // Optional

// ----------------------------------- Defines -----------------------------------

# define DA_AVLTREE
# define DA_AVLTREE_DIAGNOSTICS_LEVEL 52

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                                 Class DA_AVLTree                             //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////

template <class HeaderType, class InfoType>
class DA_AVLTree
{
public:
DA_AVLTree(char HeaderFileName[], char NodeFileName[],
          long int NoHeaders, long int NoNodes);
DA_AVLTree(char HeaderFileName[], char NodeFileName[]);
~DA_AVLTree(void);
void CreateHeaderNodes(char HeaderFileName[],  long int NoHeaders);
void CreateNodes(char NodeFileName[], long int NoNodes);

NodePtr GetNode(void);
void FreeNode(NodePtr OldNodePtr);
bool Empty (long int HeaderNo);

bool SetRight (long int HeaderNo, InfoType NewInfo, NodePtr FatherPtr);
bool SetLeft (long int HeaderNo, InfoType NewInfo, NodePtr FatherPtr);
bool Inplace (long int HeaderNo, InfoType NewInfo);

bool ValidHeader(long int HeaderNo);
bool ValidNode(long int NodeNo);

void DeleteTree(long int HeaderNo);
void InitializeNoNodes();
void DisplayNoNodes(char Message [] ="");

void NoNodesAtEachLevelTraversalDisplay (long int HeaderNo, char Message[]="");
void NoNodesAtEachLevelHelper(NodePtr Ptr);
void DisplayLoadBalanceStatistics(long int HeaderNo, char Message[]="");

void UpdateBalanceFactors(long int HeaderNo, InfoType NewInfo, NodePtr NewC);
void RotateRight(long int HeaderNo, InfoType NewInfo);
void RotateLeft(long int HeaderNo, InfoType NewInfo);
void DoubleRotateRight(long int HeaderNo, InfoType NewInfo);
void DoubleRotateLeft(long int HeaderNo, InfoType NewInfo);

bool TestAVLIntegrity (long int HeaderNo);
void TestAVLIntegrityHelper(NodePtr Ptr);

void Display (char Message[] = "");
void DisplayNodeFile(char Message[] = "");
void DisplayHeaderFile(char Message[] = "");

void QuickAndDirtyIntegerDisplay(long int HeaderNo, char Message[] = "");
void QuickAndDirtyIntegerDisplayHelper(NodePtr Ptr);
void InorderTraversalDisplay (long int HeaderNo, char Message[] = "");
void InorderHelper(NodePtr Ptr);
void PreorderTraversalDisplay (long int HeaderNo, char Message[] = "");
void PreorderHelper(NodePtr Ptr);
void PostorderTraversalDisplay (long int HeaderNo, char Message[] = "");
void PostorderHelper(NodePtr Ptr);

//private:  // You may add additional info to your class if necessary!

Stack <long int>    //Optional
TreePtrs;    //Optional

FILE
* nfp,
* hfp;

NodePtr
A,
B,
C,
Avail;

long
NoRotateRightRotations,
NoRotateLeftRotations,
NoDoubleRotateRightRotations,
NoDoubleRotateLeftRotations,
TempCounter,
LevelNo,
NoNodes[5001];

InfoType
HighValue;

bool
ValidAVLTree;
};

// ------------------------- Non-Class Functions Prototypes-----------------------
void TestDA_AVLTree1(void);
void TestDA_AVLTree2(void);
void TestDA_AVLTree3(void);
void TestDA_AVLTree4(void);

// -------------------------------- Templated Methods ----------------------------

 

2] You may download the following files if you like

AVL.zip

3] Include the following display and test methods in file DA_AVLTreee.hpp

 // -------------------------------- Templated Methods ----------------------------


//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                                 Display                                      //
//                                                                              //
// Purpose : Display the headers, nodes, and avail in a nice graphical format.  //
//                                                                              //
// Written By : Dr. Thomas E. Hicks               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////

template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::Display(char Message[])
{
DisplayHeaderFile (Message);
DisplayNodeFile ("\n");
printf("Avail = %ld\n\n", Avail);
HitCarriageReturnToContinue();
}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                             DisplayHeaderFile                                //
//                                                                              //
// Purpose : Display the headers in a nice graphical format.                    //
//                                                                              //
// Written By : Dr. Thomas E. Hicks               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::DisplayHeaderFile(char Message[])
{
HeaderType
Header;
long int
RecordNo,
NoRecords;

NoRecords = FileLength (hfp, sizeof(Header));

for (RecordNo = NoRecords - 1; RecordNo >= 0; RecordNo --)
{
ReadRecord(&Header, RecordNo, hfp);
if (RecordNo == NoRecords - 1)
Header.Display (Message, true, true,true,RecordNo);
else
Header.Display ("", false, false, true, RecordNo);
}
}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                             DisplayNodeFile                                  //
//                                                                              //
// Purpose : Display the nodes in a nice graphical format.                      //
//                                                                              //
// Written By : Dr. Thomas E. Hicks               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::DisplayNodeFile(char Message[])
{
AVLNode <InfoType>
NewNode;
long int
RecordNo,
NoRecords;

NoRecords = FileLength (nfp, sizeof(NewNode));
for (RecordNo = NoRecords - 1; RecordNo >= 0; RecordNo --)
{
ReadRecord(&NewNode, RecordNo, nfp);
if (RecordNo == NoRecords -1 )
NewNode.Display (Message, true, true,true,RecordNo);
else
NewNode.Display ("", false, false, true, RecordNo);
}
}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                         QuickAndDirtyIntegerDisplay                          //
//                                                                              //
// Purpose : Display the Numerical integer information in an 8 character field  //
//           ten items to a line. Only works for IntegerListHeader and Integer  //
//           data.                                                              //
//                                                                              //
// Written By : Dr. Thomas E. Hicks               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////

template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::QuickAndDirtyIntegerDisplay(long int HeaderNo,
                                                                        char Message[] )
{
IntegerTreeHeader
Header;

ReadRecord(&Header, HeaderNo, hfp);
Header.Display(Message);
TempCounter = 0;
QuickAndDirtyIntegerDisplayHelper(Header.Root);
printf("\nCount = %ld\n\n", TempCounter);
}

template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::QuickAndDirtyIntegerDisplayHelper(NodePtr Ptr)
{
AVLNode <Integer> 
    Node;

if (Ptr != NILL)
{
ReadRecord(&Node, Ptr, nfp);
QuickAndDirtyIntegerDisplayHelper(Node.Left);

ReadRecord(&Node, Ptr, nfp);
printf("%8ld", Node.Info.Key());
TempCounter++;
if (TempCounter % 10 == 0)
printf("\n");

ReadRecord(&Node, Ptr, nfp);
QuickAndDirtyIntegerDisplayHelper(Node.Right);
}
}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                             InorderTraversal                                 //
//                                                                              //
// Purpose : Display header and the nodes within that header inorder.           //
//                                                                              //
// Written By : Dr. Thomas E. Hicks               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////

template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::InorderTraversalDisplay (long int HeaderNo, char Message[])
{
HeaderType
Header;

puts("\n\n          =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-");
puts("          =-=-=-=-=-=-=-=-=-=-=-=-  Inorder Traversal  -=-=-=-=-=-=-=-=-=-");
puts("          =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n");
ReadRecord(&Header, HeaderNo, hfp);
Header.Display (Message, true, true,true,HeaderNo);
printf("\n\n     --------------------------------");
printf("----------------------------------------\n");

InorderHelper (Header.Root);
}

template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::InorderHelper(NodePtr Ptr)
{
AVLNode <InfoType>
Node;

if (Ptr != NILL)
{
ReadRecord(&Node, Ptr, nfp);
InorderHelper (Node.Left);

ReadRecord(&Node, Ptr, nfp);
Node.Display ("", false, false, true, Ptr);

ReadRecord(&Node, Ptr, nfp);
InorderHelper (Node.Right);
}
}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                             PreorderTraversal                                //
//                                                                              //
// Purpose : Display header and the nodes within that header Preorder.          //
//                                                                              //
// Written By : Dr. Thomas E. Hicks               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////

template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::PreorderTraversalDisplay (long int HeaderNo, char Message[])
{
HeaderType
Header;

puts("\n\n          =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-");
puts("          =-=-=-=-=-=-=-=-=-=-=-=-  Preorder Traversal  -=-=-=-=-=-=-=-=-=-");
puts("          =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n");
ReadRecord(&Header, HeaderNo, hfp);
Header.Display (Message, true, true,true,HeaderNo);
printf("\n\n     --------------------------------");
printf("----------------------------------------\n");

PreorderHelper (Header.Root);
}

template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::PreorderHelper(NodePtr Ptr)
{
AVLNode <InfoType>
Node;

if (Ptr != NILL)
{
ReadRecord(&Node, Ptr, nfp);
Node.Display ("", false, false, true, Ptr);

ReadRecord(&Node, Ptr, nfp);
PreorderHelper (Node.Left);

ReadRecord(&Node, Ptr, nfp);
PreorderHelper (Node.Right);
}
}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                             PostorderTraversal                               //
//                                                                              //
// Purpose : Display header and the nodes within that header Postorder.         //
//                                                                              //
// Written By : Dr. Thomas E. Hicks               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////

template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::PostorderTraversalDisplay (long int HeaderNo,
                                                                       char Message[])
{
HeaderType
Header;

puts("\n\n          =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-");
puts("          =-=-=-=-=-=-=-=-=-=-=-=-  Postorder Traversal  -=-=-=-=-=-=-=-=-=-");
puts("          =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n");
ReadRecord(&Header, HeaderNo, hfp);
Header.Display (Message, true, true,true,HeaderNo);
printf("\n\n     --------------------------------");
printf("----------------------------------------\n");

PostorderHelper (Header.Root);
}


template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::PostorderHelper(NodePtr Ptr)
{
AVLNode <InfoType>
Node;

if (Ptr != NILL)
{
ReadRecord(&Node, Ptr, nfp);
PostorderHelper (Node.Left);

ReadRecord(&Node, Ptr, nfp);
PostorderHelper (Node.Right);

ReadRecord(&Node, Ptr, nfp);
Node.Display ("", false, false, true, Ptr);

}
}


//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                             InitializeNoNodes                                //
//                                                                              //
// Purpose : Set the 5,000 NoNodes array elements to 0.                         //
//                                                                              //
// Written By : Dr. Thomas E. Hicks               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////

template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::InitializeNoNodes()
{
long int
Pos;

for (Pos = 0; Pos <= 5000; Pos ++)
NoNodes[Pos]= 0;
}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                             InitializeNoNodes                                //
//                                                                              //
// Purpose : Graphical display of the NoNodes array; display at least 6 levels. //
//                                                                              //
// Written By : Dr. Thomas E. Hicks               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
template <class HeaderType, class InfoType>
void DA_AVLTree <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");

}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                    NoNodesAtEachLevelTraversalDisplay                        //
//                                                                              //
// Purpose : Set the LevelNo to 0. InitializeNoNodes. Evoke the recursive       //
//           NoNodesAtEachLevelHelper helper function. DisplayNoNodes array.    //
//                                                                              //
// Written By : Dr. Thomas E. Hicks               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////

template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::NoNodesAtEachLevelTraversalDisplay
                                                (long int HeaderNo, char Message[])
{
HeaderType
Header;

printf ("\n");
puts(Message);
ReadRecord(&Header, HeaderNo, hfp);
LevelNo = 0;
InitializeNoNodes();
NoNodesAtEachLevelHelper (Header.Root);
DisplayNoNodes();
}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                        NoNodesAtEachLevelHelper                              //
//                                                                              //
// Purpose : Traverse the tree; increment the LevelNo as you go up and down     //
//           the tree.  [LevelNo++]. Update the NoNodes each time you visit     //
//           the node.  [NoNodes[LevelNo]++].                                   //
//                                                                              //
// Written By : Dr. Thomas E. Hicks               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////

template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::NoNodesAtEachLevelHelper(NodePtr Ptr)
{
AVLNode <InfoType>
Node;

if (Ptr != NILL)
{
LevelNo ++;
ReadRecord(&Node, Ptr, nfp);
if (Node.Left != NILL)
NoNodesAtEachLevelHelper (Node.Left);

NoNodes[LevelNo]++;
ReadRecord(&Node, Ptr, nfp);

ReadRecord(&Node, Ptr, nfp);
if (Node.Right != NILL)
NoNodesAtEachLevelHelper (Node.Right);
LevelNo --;
}
}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                        DisplayLoadBalanceStatistics                          //
//                                                                              //
// Purpose : Call NoNodesAtEachLevelTraversalDisplay. Display the following     //
//          No Nodes ........= xxxxxxxxxxxx                                     //
//          No Levels .......= xxxxxxxxxxxx                                     //
//          Average Search ..= xxxxxx.xx                                        //
//                                                                              //
// Written By : Dr. Thomas E. Hicks               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::DisplayLoadBalanceStatistics(long
                                                     int HeaderNo, char Message[])
{
long int
LevelNo,
SearchTotal,
NoLevels,
TotalNodes;

SearchTotal = 0;
TotalNodes  = 0;
NoLevels = 0;

NoNodesAtEachLevelTraversalDisplay (HeaderNo, Message);
for (LevelNo = 1; LevelNo <= 5000; LevelNo ++)
{
TotalNodes = TotalNodes + NoNodes[LevelNo];
SearchTotal = SearchTotal + NoNodes[LevelNo]*LevelNo;
if ((NoNodes[LevelNo] > 0) && (LevelNo > NoLevels))
NoLevels = LevelNo;
}
printf ("No Nodes ........= %ld\n", TotalNodes);
printf ("No Levels .......= %ld\n", NoLevels);
printf ("Average Search ..= %.2f\n",double(SearchTotal)/TotalNodes);
}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                          UpdateBalanceFactors                                //
//                                                                              //
// Purpose : Walk up the tree adjusting balance factors as you go. Stop the     //
//           walk when setting the father to BF = 0. Stop the walk when you     //
//           get to the root. Stop the walk when you need to rebalance.         //
//           Maintain pointers A, B, and C.                                     //
//                                                                              //
// Written By : ???????????????????               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////




//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                              RotateRight                                     //
//                                                                              //
// Purpose : Perform the Single Right Rotation when the balance factors are     //
//           A = 2 and B = 1.                                                   //
//                                                                              //
// Written By : ???????????????????               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////



//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                              RotateLeft                                      //
//                                                                              //
// Purpose : Perform the Single Left Rotation when the balance factors are      //
//           A = -2 and B = -1.                                                 //
//                                                                              //
// Written By : ???????????????????               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////



//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                              DoubleRotateRight                               //
//                                                                              //
// Purpose : Perform the Double Right Rotation when the balance factors are     //
//           A = 2 and B = -1.                                                  //
//                                                                              //
// Written By : ???????????????????               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////




//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                              DoubleRotateLeft                                //
//                                                                              //
// Purpose : Perform the Double Left Rotation when the balance factors are      //
//           A = -2 and B = 1.                                                  //
//                                                                              //
// Written By : ???????????????????               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////


//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                              TestAVLIntegrity                                //
//                                                                              //
// Purpose : Traverse the tree to make sure that the nodes occur in ascending   //
//           order and that the balance factors are in the range -1, 0, +1.     //
//           Explicitly return true if valid; otherwise false.                  //
//                                                                              //
// Written By : Dr. Thomas E. Hicks               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
template <class HeaderType, class InfoType>
bool DA_AVLTree <HeaderType, InfoType> ::TestAVLIntegrity (long int HeaderNo)
{
HeaderType
Header;
NodePtr
Ptr;
AVLNode<InfoType>
Node;

if (Empty(HeaderNo))
return (true);

ValidAVLTree = true;
ReadRecord(&Header, HeaderNo, hfp);
Ptr = Header.Root;
ReadRecord(&Node, Ptr, nfp);

while(Node.Left != NILL)
{
Ptr = Node.Left;
ReadRecord(&Node, Ptr, nfp);
}

HighValue = Node.Info;
TestAVLIntegrityHelper (Header.Root);
return (ValidAVLTree);
}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                        TestAVLIntegrityHelper                                //
//                                                                              //
// Purpose : Change ValidAVLTree to false if the inorder traversal does not     //
//           continue to increase. Change the ValidAVLTree to false if the      //
//           balance factor is outside the range -1, 0, +1.                     //
//                                                                              //
// Written By : Dr. Thomas E. Hicks               Environment : Windows XP      //
//       Date : XX/XX/XXXX                           Compiler : Visual NET      //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////

template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::TestAVLIntegrityHelper(NodePtr Ptr)
{
AVLNode <InfoType>
Node;

if (Ptr != NILL)
{
ReadRecord(&Node, Ptr, nfp);
TestAVLIntegrityHelper (Node.Left);

ReadRecord(&Node, Ptr, nfp);
if (Node.Info >= HighValue)
HighValue = Node.Info;
else
{
ValidAVLTree = false;
printf ("\nData Out Of Order = Node # %ld\n", Ptr);
}
  if ((Node.BalanceFactor > 1) || (Node.BalanceFactor < -1))
{
ValidAVLTree = false;
printf ("\nInvalid Balance Factor = Node # %ld\n", Ptr);
}
ReadRecord(&Node, Ptr, nfp);
TestAVLIntegrityHelper (Node.Right);
}
}

# endif // DA_AVLTREE =====================================================

3] and include the following in file DA_AVLTreee.cpp

 //////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//                                DA_AVLTree.cpp                                //
//                                                                              //
// Purpose    :  Students shall add the following test module to their          //
//               program. Program main shall call only this module.  Do not     //
//               delete your testing code; it is part of your grade.            //
//                                                                              //
//  Written By : Thomas E. Hicks         Environment : Windows 2003 Server      //
//  Date ......: xx/xx/xxxx              Compiler ...: Visual Studio Net 2005   //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
# include "DA-AVL-Tree.hpp"

# ifdef DA_AVLTREE_DIAGNOSTICS_LEVEL //  --------------------------------

# include "Student.hpp"
# include "StudentTreeHeader.hpp"

# include "Auto.hpp"
# include "AutoTreeHeader.hpp"    

# include "Part.hpp"
# include "PartTreeHeader.hpp"     

# include "Client.hpp"
# include "ClientTreeHeader.hpp"  

# include "Integer.hpp"
# include "IntegerTreeHeader.hpp"

# include "Book.hpp"
# include "BookTreeHeader.hpp"

# include "Athlete.hpp"
# include "AthleteTreeHeader.hpp"

# include "MP3.hpp"
# include "MP3TreeHeader.hpp"

//------------------------------------------------------------------------------//
//------------------------------------------------------------------------------//
//                                                                              //
//                      InitializeTreeHeaderFile Functions                      //
//                                                                              //
// There are several InitializeHeader File Functions below. In a real           //
// interactive system, Header Nodes could be easily filled with GUIs. The       //
// Headers would probably contain a deleted flag and be linked as well. For     //
// our educational applications, we shall link and delete the nodes, knowing    //
// that we could come back and add that functionality to the headers as well.   //
//                                                                              //
// These InitializeHeader File Functions simply enable us to have some          //
// non-garbage data to examine.                                                 //
//------------------------------------------------------------------------------//
//------------------------------------------------------------------------------//


//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//                         InitializeStudentHeaderFile                          //
//                                                                              //
// Purpose    :  Initialize the 6 StudentTreeHeader Headers in file *fp         //
//                                                                              //
// Record[0] - Class Name = ""                  Prof = ""                      //
// Record[1] - Class Name = "Data Abstractions" Prof = "Dr. Hicks"             //
// Record[2] - Class Name = "Algorithm I"       Prof = "Dr. Eggen"             //
// Record[3] - Class Name = "Algorithm II"      Prof = "Dr. Lewis"             //
// Record[4] - Class Name = "Sr Software I"     Prof = "Dr. Pitts"             //
// Record[5] - Class Name = "Graphics"          Prof = "Dr. Howland"           //
// Record[6] - Class Name = "Theory"            Prof = "Dr. Myers"             //
//                                                                              //
//  Written By : Thomas E. Hicks         Environment : Windows 2003 Server      //
//  Date ......: xx/xx/xxxx              Compiler ...: Visual Studio Net 2005   //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
void InitializeStudentHeaderFile(FILE * hfp)
{
StudentTreeHeader
Header;


WriteRecord(&Header,0, hfp);
Header.Set("Data Abstractions", "Dr. Hicks", "CSCI");
WriteRecord(&Header, 1, hfp);
Header.Set("Algorithm I", "Dr. Eggen", "CSCI");
WriteRecord(&Header, 2, hfp);
Header.Set("Algorithm II", "Dr. Lewis", "CSCI");
WriteRecord(&Header, 3, hfp);
Header.Set("Sr Software I", "Dr. Pitts", "CSCI");
WriteRecord(&Header, 4, hfp);
Header.Set("Graphics", "Dr. Howland", "CSCI");
WriteRecord(&Header, 5, hfp);
Header.Set("Theory", "Dr. Myers", "CSCI");
WriteRecord(&Header, 6, hfp);
}


//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//                        InitializeIntegerHeaderFile                           //
//                                                                              //
// Purpose    :  Initialize the 3 IntegerTreeHeader Headers in file *fp         //
//                                                                              //
// Record[0] - Title = ""                                                      //
// Record[1] - Title = "c"                                                     //
// Record[2] - Title = "No-2"                                                  //
// Record[3] - Title = "No-3"                                                  //
//                                                                              //
//  Written By : Thomas E. Hicks         Environment : Windows 2003 Server      //
//  Date ......: xx/xx/xxxx              Compiler ...: Visual Studio Net 2005   //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
void InitializeIntegerHeaderFile(FILE * hfp)
{
IntegerTreeHeader
Header;

WriteRecord(&Header,0, hfp);
Header.Set("No-1");
WriteRecord(&Header, 1, hfp);
Header.Set("No-2");
WriteRecord(&Header, 2, hfp);
Header.Set("No-3");
WriteRecord(&Header, 3, hfp);
}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//                         InitializePartHeaderFile                             //
//                                                                              //
// Purpose    :  Initialize the 4 PartTreeHeader Headers in file *fp            //
//                                                                              //
// Record[0] - Dept Name = ""                Manager = ""                      //
// Record[1] - Dept Name = "Appliances"      Manager = "Dr. Massingil"         //
// Record[2] - Dept Name = "Computers"       Manager = "Dr. Hicks"             //
// Record[3] - Dept Name = "Sporting Goods"  Manager = "Dr. Chang"             //
// Record[4] - Dept Name = "Ladie's Shoes"   Manager = "Dr. Semmes"            //
//                                                                              //
//  Written By : Thomas E. Hicks         Environment : Windows 2003 Server      //
//  Date ......: xx/xx/xxxx              Compiler ...: Visual Studio Net 2005   //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
void InitializePartHeaderFile(FILE * hfp)
{
PartTreeHeader
Header;

WriteRecord(&Header,0, hfp);
Header.Set("Appliances", "Pitts.");
WriteRecord(&Header, 1, hfp);
Header.Set("Computers", "Hicks.");
WriteRecord(&Header, 2, hfp);
Header.Set("Sporting Goods", "Lewis");
WriteRecord(&Header, 3, hfp);
Header.Set("Ladie's Shoes", "Myers");
WriteRecord(&Header, 4, hfp);
}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//                            InitializeAutoHeaderFile                          //
//                                                                              //
// Purpose    :  Initialize the 7 AutoTreeHeader Headers in file *fp            //
//                                                                              //
// Record[0] - Division Name = ""           Manager = ""                       //
// Record[1] - Division Name = "Mercury"    Manager = "Duck, Donald"           //
// Record[2] - Division Name = "Jaguar"     Manager = "Duck, Daffy"            //
// Record[3] - Division Name = "Audi"       Manager = "Road Runner"            //
// Record[4] - Division Name = "Ford"       Manager = "Sam, Yosemite"          //
// Record[5] - Division Name = "Crysler"    Manager = "Bunny, Buggs"           //
// Record[6] - Division Name = "Chevrolet"  Manager = "Menace, Dennis"         //
// Record[7] - Division Name = "Jeep"       Manager = "Pluto"                  //
//                                                                              //
//  Written By : Thomas E. Hicks         Environment : Windows 2003 Server      //
//  Date ......: xx/xx/xxxx              Compiler ...: Visual Studio Net 2005   //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
void InitializeAutoHeaderFile(FILE * hfp)
{
AutoTreeHeader
Header;

WriteRecord(&Header,0, hfp);
Header.Set("Mercury", "Duck, Donald");
WriteRecord(&Header, 1, hfp);
Header.Set("Jaguar", "Duck, Daffy");
WriteRecord(&Header, 2, hfp);
Header.Set("Audi", "Road Runner");
WriteRecord(&Header, 3, hfp);
Header.Set("Ford", "Sam, Yosemite");
WriteRecord(&Header, 4, hfp);
Header.Set("Crysler", "Bunny, Buggs");
WriteRecord(&Header, 5, hfp);
Header.Set("Chevrolet", "Menace, Dennis");
WriteRecord(&Header, 6, hfp);
Header.Set("Jeep", "Pluto");
WriteRecord(&Header, 7, hfp);
}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//                            InitializeBookHeaderFile                          //
//                                                                              //
// Purpose    :  Initialize the 6 BookTreeHeader Headers in file *fp            //
//                                                                              //
// Record[0] - Division Name = ""             Manager = ""                     //
// Record[1] - Division Name = "Fiction"      Manager = "John"                 //
// Record[2] - Division Name = "Reference"    Manager = "Gerald"               //
// Record[3] - Division Name = "Computers"    Manager = "Tom"                  //
// Record[4] - Division Name = "Non-Fiction"  Manager = "Paul"                 //
// Record[5] - Division Name = "Music"        Manager = "Morey"                //
// Record[6] - Division Name = "Self Help"    Manager = "Berna"                //
//                                                                              //
//  Written By : Thomas E. Hicks         Environment : Windows 2003 Server      //
//  Date ......: xx/xx/xxxx              Compiler ...: Visual Studio Net 2005   //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
void InitializeBookHeaderFile(FILE * hfp)
{
BookTreeHeader
Header("","");

WriteRecord(&Header,0, hfp);
Header.Set("Fiction", "John");
WriteRecord(&Header, 1, hfp);
Header.Set("Reference", "Gerald");
WriteRecord(&Header, 2, hfp);
Header.Set("Computers", "Tom");
WriteRecord(&Header, 3, hfp);
Header.Set("Non-Fiction", "Paul");
WriteRecord(&Header, 4, hfp);
Header.Set("Music", "Morey");
WriteRecord(&Header, 5, hfp);
Header.Set("Self Help", "Berna");
WriteRecord(&Header, 6, hfp);
}


//////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////
//                                                                                  //
//                            InitializeClientHeaderFile                            //
//                                                                                  //
// Purpose    :  Initialize the 6 ClientTreeHeader Headers in file *fp              //
//                                                                                  //
// Record[0] - Division Name = ""                Manager = ""                      //
// Record[1] - Division Name = "Schwab"          Manager = "John Wayne"            //
// Record[2] - Division Name = "Trade King"      Manager = "Jennifer Hewitt"       //
// Record[3] - Division Name = "Fidelity"        Manager = "Josh Hartnett"         //
// Record[4] - Division Name = "Smith Barney"    Manager = "Halle Berry"           //
// Record[5] - Division Name = "Ameritrade Inc"  Manager = "Reese Witherspoon"     //
// Record[6] - Division Name = "TD Waterhouse"   Manager = "Pierce Brosnan"        //
//                                                                                  //
//  Written By : Thomas E. Hicks         Environment : Windows 2003 Server          //
//  Date ......: xx/xx/xxxx              Compiler ...: Visual Studio Net 2005       //
//////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////
void InitializeClientHeaderFile(FILE * hfp)
{
ClientTreeHeader
Header;

WriteRecord(&Header,0, hfp);
Header.Set("Schwab", "John Wayne");
WriteRecord(&Header, 1, hfp);
Header.Set("Trade King", "Jennifer Hewitt");
WriteRecord(&Header, 2, hfp);
Header.Set("Fidelity", "Josh Hartnett");
WriteRecord(&Header, 3, hfp);
Header.Set("Smith Barney", "Halle Berry");
WriteRecord(&Header, 4, hfp);
Header.Set("Ameritrade Inc", "Reese Witherspoon");
WriteRecord(&Header, 5, hfp);
Header.Set("TD Waterhouse", "Pierce Brosnan");
WriteRecord(&Header, 6, hfp);
}


//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//                        InitializeMP3HeaderFile                               //
//                                                                              //
// Purpose    :  Initialize the 6 MP3TreeHeader Headers in file *fp             //
//                                                                              //
// Record[0]  - PlayAVLTree = ""          Genre = ""                           //
// Record[1]  - PlayAVLTree = "Ricardo"   Genre = "Contemporary Christian"     //
// Record[2]  - PlayAVLTree = "Cesar"     Genre = "Gospel"                     //
// Record[3]  - PlayAVLTree = "Michael"   Genre = "Jaz"                        //
// Record[4]  - PlayAVLTree = "Andy"      Genre = "Soft Classic"               //
// Record[5]  - PlayAVLTree = "Brit"      Genre = "Acid Techno"                //
// Record[6]  - PlayAVLTree = "Rebecca"   Genre = "Raggacore"                  //
// Record[7]  - PlayAVLTree = "Jason"     Genre = "Chillout"                   //
// Record[8]  - PlayAVLTree = "Crisanto"  Genre = "Breakcore"                  //
// Record[9]  - PlayAVLTree = "Andrew"    Genre = "Clownstep"                  //
// Record[10] - PlayAVLTree = "Amy"       Genre = "Ambient House"              //
// Record[11] - PlayAVLTree = "Jennifer"  Genre = "Melodic Psytrance"          //
//                                                                              //
//  Written By : Thomas E. Hicks         Environment : Windows 2003 Server      //
//  Date ......: xx/xx/xxxx              Compiler ...: Visual Studio Net 2005   //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
/********************************************************************************************
* For You To Do!                                                                            *
********************************************************************************************/

void InitializeMP3HeaderFile(FILE * hfp)
{
MP3TreeHeader
Header;

WriteRecord(&Header,0, hfp);
Header.Set("Ricardo","Classical");
WriteRecord(&Header, 1, hfp);
Header.Set("Cesar", "Soft Rock");
WriteRecord(&Header, 2, hfp);
Header.Set("Michael", "Jaz");
WriteRecord(&Header, 3, hfp);
Header.Set("Andy", "Soft Classic");
WriteRecord(&Header, 4, hfp);
Header.Set("Brit", "Acid Techno");
WriteRecord(&Header, 5, hfp);
Header.Set("Rebecca", "Raggacore");
WriteRecord(&Header, 6, hfp);
Header.Set("Jason", "Chillout");
WriteRecord(&Header, 7, hfp);
Header.Set( "Crisanto", "Breakcore");
WriteRecord(&Header, 8, hfp);
Header.Set("Andrew", "Clownstep");
WriteRecord(&Header, 9, hfp);
Header.Set( "Amy", "Ambient House");
WriteRecord(&Header, 10, hfp);
Header.Set("Jennifer", "Melodic Psytrance");
WriteRecord(&Header, 11, hfp);
}

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//                     InitializeAthleteHeaderFile                              //
//                                                                              //
// Purpose    :  Initialize the 8 AthleteTreeHeader Headers in file *fp         //
//                                                                              //
// Record[0] - Name = ""             Coach = ""                                //
// Record[1] - Name = "Golf"         Coach = "Dr. Hicks"                       //
// Record[2] - Name = "Racketball"   Coach = "Dr. Eggen"                       //
// Record[3] - Name = "Running"      Coach = "Dr. Howland"                     //
// Record[4] - Name = "Basketball"   Coach = "Dr. Lewis"                       //
// Record[5] - Name = "Fencing"      Coach = "Dr. Myers"                       //
// Record[6] - Name = "Softball"     Coach = "Dr. Massingil"                   //
// Record[7] - Name = "Tennis"       Coach = "Dr. Chang"                       //
// Record[8] - Name = "Skeet"        Coach = "Dr. Pitts"                       //
//                                                                              //
//  Written By : Thomas E. Hicks         Environment : Windows 2003 Server      //
//  Date ......: xx/xx/xxxx              Compiler ...: Visual Studio Net 2005   //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
/********************************************************************************************
* For You To Do!                                                                            *
********************************************************************************************/

void InitializeAthleteHeaderFile(FILE * hfp)
{
AthleteTreeHeader
Header;

WriteRecord(&Header,0, hfp);

Header.Set ("Golf", "Dr. Hicks");
WriteRecord(&Header, 1, hfp);
Header.Set("Racketball", "Dr. Eggen");
WriteRecord(&Header, 2, hfp);
Header.Set("Running", "Dr. Howland");
WriteRecord(&Header, 3, hfp);
Header.Set ("Basketball", "Dr. Lewis");
WriteRecord(&Header, 4, hfp);
Header.Set("Fencing", "Dr. Myers");
WriteRecord(&Header, 5, hfp);
Header.Set("Softball", "Dr. Massingil");
WriteRecord(&Header, 6, hfp);
Header.Set("Tennis", "Dr. Chang");
WriteRecord(&Header, 7, hfp);
Header.Set("Skeet", "Dr. Pitts");
WriteRecord(&Header, 8, hfp);
}


void TestDA_AVLTree1(void)
{
puts("\n\n*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("********************** Start TestDA_AVLTree1  **********************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************\n\n");

Student
Students[30];
Part
Parts[80];
Auto
Autos[30];

Students[0].Set("Brown, Chris", 101, MALE);
Students[1].Set("Weston, Clay", 102, MALE);
Students[2].Set("McBryde, Michael", 103, MALE);
Students[3].Set("Elsaifi, Leslie", 104, FEMALE);
Students[4].Set("Kelly, Nick", 105, MALE);
Students[5].Set("Wilson, Jennifer", 106, FEMALE);
Students[6].Set("Silliman, Mark", 107, MALE);
Students[7].Set("Merka, Lauren", 108, FEMALE);
Students[8].Set("Guest, Ben", 109, MALE);
Students[9].Set("Condon, Ryan", 200, MALE);
Students[10].Set("Bertles, Joe, Ryan", 201, MALE);
Students[11].Set("Gonzaba, Jodi", 202, FEMALE);
Students[12].Set("Crowe, Loren", 203, MALE);
Students[13].Set("Marquez, Angel", 204, MALE);
Students[14].Set("Houck, David", 205, MALE);
Students[15].Set("Ross, Garrett, David", 206, MALE);
Students[16].Set("Schwartz, Scott, David", 207, MALE);
Students[17].Set("Caille, Ryan", 208, MALE);
Students[18].Set("Schubet, Kurt", 209, MALE);
Students[19].Set("Canion, Todd", 300, MALE);
Students[20].Set("West, Paul", 301, MALE);
Students[21].Set("Haik, Adrienne", 302, FEMALE);
Students[22].Set("Swanson, Anna", 303, FEMALE);
Students[23].Set("Jones, Travis", 304, MALE);
Students[24].Set("Stansell, Kevin", 305, MALE);
Students[25].Set("Lara, Domingo", 306, MALE);
Students[26].Set("Rodriquez, Anthony", 307, MALE);
Students[27].Set("Mohajan, Rohit", 308, MALE);
Students[28].Set("Middleton, Phillip", 309, MALE);
Students[29].Set("Schwartz, Scott, David", 204, MALE);

Autos[0].Set("Corvette Stingray", 101, CONVERTABLE);
Autos[1].Set("Porche 911", 102, CONVERTABLE);
Autos[2].Set("VW", 103, CONVERTABLE);
Autos[3].Set("Limo", 104, COUP);
Autos[4].Set("Lincoln Continental", 105, CONVERTABLE);
Autos[5].Set("Maxima", 106, COUP);
Autos[6].Set("Mercury Cougar", 107, CONVERTABLE);
Autos[7].Set("Mustang", 108, COUP);
Autos[8].Set("Explorer", 109, CONVERTABLE);
Autos[9].Set("Lincoln Towncar", 200, CONVERTABLE);
Autos[10].Set("Chevrolet Capri", 201, CONVERTABLE);
Autos[11].Set("Jaguar", 202, COUP);
Autos[12].Set("Honda 2000", 203, CONVERTABLE);

Parts[1].Set("Basketball",       111, 3,  10,   25.00);
Parts[2].Set("Football",         105, 3,  15,   25.00);
Parts[3].Set("Tennis Balls",     127, 3,   6,    3.00);
Parts[4].Set("Golf Balls",       104, 3,  10,   12.00);
Parts[5].Set("Soccer Ball",      141, 3,   5,   40.00);
Parts[6].Set("GB Hard Drive",    120, 2,  12,   37.95);
Parts[7].Set("Microwave",        112, 1,  15,   59.80);
Parts[8].Set("Gas Stove",        136, 1,   6,  237.69);
Parts[9].Set("Cup",              156, 3,  23,    8.88);
Parts[10].Set("Baseball",        123, 3,  10,    8.00);
Parts[11].Set("Teather Ball",    155, 3,   4,   14.00);
Parts[12].Set("Golf Tees",       125, 3,  60,    2.00);
Parts[13].Set("Tennis Shoes",    101, 3,  10,  100.00);
Parts[14].Set("Ping Pong Balls", 154, 3,  10,    3.00);
Parts[15].Set("MotherBoard",     113, 2,  11,   55.00);
Parts[16].Set("SDRAM",           135, 2,  30,   40.01);
Parts[17].Set("Iron",            132, 1,  21,   38.77);
Parts[18].Set("Long Socks",      153, 3,  34,    9.99);
Parts[19].Set("CD-ROM",          110, 2,  11,   30.12);
Parts[20].Set("CD-RW",           124, 2,  26,   56.13);
Parts[21].Set("Thin Monitor",    140, 2,   5,   89.00);
Parts[22].Set("Large Monitor",   139, 2,   9,   78.99);
Parts[23].Set("Dish Washer",     117, 1,  10,  120.78);
Parts[24].Set("Tennis Racquet",  118, 3,   4,   80.00);
Parts[25].Set("Golf Club",       152, 3,  14,   49.00);
Parts[26].Set("Gym Bag",         151, 3,  10,   14.00);
Parts[27].Set("Golf Glove",      128, 3,  11,   14.06);
Parts[28].Set("Golf Bag",        150, 3,   5,   99.00);
Parts[29].Set("Squash Racquet",  119, 3,   2,   80.00);
Parts[30].Set("Squash Balls",    149, 3,   3,    8.00);
Parts[31].Set("Archery Set",     148, 3,   1,   25.00);
Parts[32].Set("Compound Bow",    102, 3,   1,   80.00);
Parts[33].Set("Arrows",          147, 3, 100,    6.00);
Parts[34].Set("Quiver",          131, 3,   2,   16.00);
Parts[35].Set("Racquet Balls",   146, 3,  15,    6.00);
Parts[36].Set("Baseball Bats",   106, 3,   4,   48.00);
Parts[37].Set("Golf Driver",     130, 3,   3,   99.00);
Parts[38].Set("Knee Pads",       103, 3,   4,    8.00);
Parts[39].Set("Soccer Cleats",   121, 3,   2,   48.00);
Parts[40].Set("Shin Guards",     137, 3,   5,   48.05);
Parts[41].Set("Printer",         145, 2,  14,   29.98);
Parts[42].Set("Laser Printer",   108, 2,  13,   43.99);
Parts[43].Set("Printer Cables",  144, 2,  12,    9.99);
Parts[44].Set("Tranportable Fan",116, 1,   6,   45.67);
Parts[45].Set("Dirt Devil",      114, 1,  11,   48.80);
Parts[46].Set("B-Ball Shoes",    143, 3,   9,  135.99);
Parts[47].Set("Case",            134, 2,   4,   20.00);
Parts[48].Set("Graphics Card",   142, 2,   7,   58.00);
Parts[49].Set("Sound Card",      107, 2,   4,   34.99);
Parts[50].Set("CD Player",       138, 1,  16,   57.75);
Parts[51].Set("Floppy Drive",    126, 2,   4,   12.00);
Parts[52].Set("Removeable Drive",122, 2,  12,   59.94);
Parts[53].Set("External zip",    129, 2,   8,   67.75);
Parts[54].Set("Floppy's",        115, 2,  99,     .50);
Parts[55].Set("Mouse",           109, 2,  35,    7.99);
Parts[56].Set("Keyboard",        133, 2,  44,   12.99);


if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 1)
{
puts("\n\n===================================================================");
puts("===================================================================");
puts("=============== DA_AVLTREE_DIAGNOSTICS_LEVEL = 1 =============");
puts("===============                                       =============");
puts("===============    Testing Constructor & Destructor   =============");
puts("===============         For Existing Files            =============");
puts("===================================================================\n");
puts("===================================================================\n");


DA_AVLTree <PartTreeHeader, Part>  
Inventory ("Hicks-Inventory.hf", "Hicks-Inventory.nf");
Inventory.Display("----> Existing Hicks-Inventory");

Inventory.InorderTraversalDisplay(1, "Contents of Inventory Header # 1");
Inventory.InorderTraversalDisplay(2, "Contents of Inventory Header # 2");
Inventory.InorderTraversalDisplay(3, "Contents of Inventory Header # 3");
Inventory.InorderTraversalDisplay(4, "Contents of Inventory Header # 4");

puts("*******************************************************************");
puts("*******************************************************************\n\n\n");
HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 2)
{
puts("\n\n===================================================================");
puts("===================================================================");
puts("=============== DA_AVLTREE_DIAGNOSTICS_LEVEL = 2 =============");
puts("===============                                       =============");
puts("===============    Testing Constructor & Destructor   =============");
puts("===============       For Newly Created Files         =============");
puts("===================================================================");
puts("===================================================================\n");

DA_AVLTree <TreeHeader, int>  
Num ("Num.hf", "Num.nf", 3, 7);
Num.Display("----> Initialized Num");

DA_AVLTree <StudentTreeHeader, Student>  
Trinity ("Trinity.hf", "Trinity.nf", 6, 3);
InitializeStudentHeaderFile(Trinity.hfp);
Trinity.Display("----> Initialized Trinity");

DA_AVLTree <AutoTreeHeader, Auto>  
NorthPark ("NorthPark.hf", "NorthPark.nf", 3, 7);
InitializeAutoHeaderFile(NorthPark.hfp);
NorthPark.Display("----> Initialized NorthPark");

DA_AVLTree <PartTreeHeader, Part>  
Inventory ("Inventory.hf", "Inventory.nf", 4, 7);
InitializePartHeaderFile(Inventory.hfp);
Inventory.Display("----> Initialized Inventory");

DA_AVLTree <ClientTreeHeader, Client>  
SmithBarney("SmithBarney.hf", "SmithBarney.nf", 8, 8);
InitializeClientHeaderFile(SmithBarney.hfp);
SmithBarney.Display("----> Initialized SmithBarney");

DA_AVLTree <IntegerTreeHeader, Integer>  
Nos ("Nos.hf", "Nos.nf", 3, 7);
InitializeIntegerHeaderFile(Nos.hfp);
Nos.Display("----> Initialized Nos");

DA_AVLTree <BookTreeHeader, Part>  
Library ("Library.hf", "Library.nf",  5, 12);
InitializeBookHeaderFile(Library.hfp);
Library.Display("----> Initialized Library");

DA_AVLTree <AthleteTreeHeader, Athlete>  
TrinitySports ("TrinitySports.hf", "TrinitySports.nf",  8, 10);
InitializeAthleteHeaderFile(TrinitySports.hfp);
TrinitySports.Display("----> Initialized TrinitySports");

DA_AVLTree <MP3TreeHeader, MP3>  
PlayAVLTrees ("PlayAVLTrees.hf", "PlayAVLTrees.nf",  12, 15);
InitializeMP3HeaderFile(PlayAVLTrees.hfp);
PlayAVLTrees.Display("----> Initialized PlayAVLTrees");

puts("*******************************************************************");
puts("*******************************************************************\n\n\n");
HitCarriageReturnToContinue();
}


// -------------------------------------------------------------------------------

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 3)
{
puts("\n\n===================================================================");
puts("===================================================================");
puts("=============== DA_AVLTREE_DIAGNOSTICS_LEVEL = 3 =============");
puts("===============                                       =============");
puts("===============              Testing GetNode          =============");
puts("===================================================================");
puts("===================================================================\n\n");

NodePtr
Ptr;
DA_AVLTree <StudentTreeHeader, Student>
Class("Student.hf", "Student.nf", 4,3);

Class.DisplayNodeFile("\n\n\n\nClass Nodes After Initialization");

Ptr = Class.GetNode();
if (Ptr == NILL)
puts("\n\aNo Nodes Available #1");
else
{
printf("\n\n First Call To GetNode Says You Can Use Node # %ld\n", Ptr);
Class.DisplayNodeFile("\n\n\n\nClass Nodes After 1st GetNode");
}

Ptr = Class.GetNode();
if (Ptr == NILL)
puts("\n\aNo Nodes Available # 2");
else
{
printf("\n\n Second Call To GetNode Says You Can Use Node # %ld\n", Ptr);
Class.DisplayNodeFile("\n\n\n\nClass Nodes After 2nd GetNode");
}

Ptr = Class.GetNode();
if (Ptr == NILL)
puts("\n\aNo Nodes Available # 3");
else
{
printf("\n\n Third Call To GetNode Says You Can Use Node # %ld\n", Ptr);
Class.DisplayNodeFile("\n\n\n\nClass Nodes After 3rd GetNode");
}

Ptr = Class.GetNode();
if (Ptr == NILL)
puts("\n\aNo Nodes Available # 4");
else
{
printf("\n\n Fourth Call To GetNode Says You Can Use Node # %ld\n", Ptr);
Class.DisplayNodeFile("\n\n\n\nClass Nodes After 3rd GetNode");
}
HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------


if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 4)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 4 *****************");
puts ("******************************* Empty **********************************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <PartTreeHeader, Part>  
Inventory ("Hicks-Inventory.hf", "Hicks-Inventory.nf");
Inventory.Display("----> Existing Hicks-Inventory");


if (Inventory.Empty(1))
puts("\n\n\7\7 WRONG --  Header No 1 Is Not Empty \n\n\7\7"); 
else
puts("CORRECT -- Since Header 1 Is Not Empty"); 

if (Inventory.Empty(2))
puts("\n\n\7\7 WRONG --  Header No 2 Is Not Empty \n\n\7\7"); 
else
puts("CORRECT -- Since Header 2 Is Not Empty"); 

if (Inventory.Empty(3))
puts("\n\n\7\7 WRONG --  Header No 3 Is Not Empty \n\n\7\7"); 
else
puts("CORRECT -- Since Header 3 Is Not Empty"); 

if (Inventory.Empty(4))
puts("CORRECT -- Since Header 4 Is Empty"); 
else
puts("\n\n\7\7 WRONG --  Header No 4 Is Empty \n\n\7\7"); 

HitCarriageReturnToContinue();
}

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 5)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 5 *****************");
puts ("**************************** ValidHeader *******************************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <PartTreeHeader, Part>  
Inventory ("Hicks-Inventory.hf", "Hicks-Inventory.nf");
Inventory.Display("----> Existing Hicks-Inventory");


if (Inventory.ValidHeader(1))
puts("CORRECT -- Since Header 1 Is Valid"); 
else
puts("\n\n\7\7 WRONG --  Header No 1 Is Valid \n\n\7\7"); 

if (Inventory.ValidHeader(2))
puts("CORRECT -- Since Header 2 Is Valid"); 
else
puts("\n\n\7\7 WRONG --  Header No 2 Is Valid \n\n\7\7"); 

if (Inventory.ValidHeader(3))
puts("CORRECT -- Since Header 3 Is Valid"); 
else
puts("\n\n\7\7 WRONG --  Header No 3 Is Valid \n\n\7\7"); 

if (Inventory.ValidHeader(4))
puts("CORRECT -- Since Header 4 Is Valid"); 
else
puts("\n\n\7\7 WRONG --  Header No 4 Is Valid \n\n\7\7"); 

if (Inventory.ValidHeader(5))
puts("\n\n\7\7 WRONG --  Header No 5 Is Valid \n\n\7\7"); 
else
puts("CORRECT -- Since Header 5 Is Not Valid"); 

if (Inventory.ValidHeader(0))
puts("\n\n\7\7 WRONG --  Header No 0 Is Valid \n\n\7\7"); 
else
puts("CORRECT -- Since Header 0 Is Not Valid"); 

if (Inventory.ValidHeader(-1))
puts("\n\n\7\7 WRONG --  Header No -1 Is Valid \n\n\7\7"); 
else
puts("CORRECT -- Since Header -1 Is Not Valid"); 

HitCarriageReturnToContinue();
}

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 5)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 6 *****************");
puts ("**************************** ValidNode *********************************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <PartTreeHeader, Part>  
Inventory ("Hicks-Inventory.hf", "Hicks-Inventory.nf");
Inventory.Display("----> Existing Hicks-Inventory");


if (Inventory.ValidNode(1))
puts("CORRECT -- Since Node 1 Is Valid"); 
else
puts("\n\n\7\7 WRONG --  Node No 1 Is Valid \n\n\7\7"); 

if (Inventory.ValidNode(2))
puts("CORRECT -- Since Node 2 Is Valid"); 
else
puts("\n\n\7\7 WRONG --  Node No 2 Is Valid \n\n\7\7"); 

if (Inventory.ValidNode(3))
puts("CORRECT -- Since Node 3 Is Valid"); 
else
puts("\n\n\7\7 WRONG --  Node No 3 Is Valid \n\n\7\7"); 

if (Inventory.ValidNode(4))
puts("CORRECT -- Since Node 4 Is Valid"); 
else
puts("\n\n\7\7 WRONG --  Node No 4 Is Valid \n\n\7\7"); 

if (Inventory.ValidNode(5))
puts("CORRECT -- Since Node 5 Is Valid"); 
else
puts("\n\n\7\7 WRONG --  Node No 5 Is Valid \n\n\7\7"); 

if (Inventory.ValidNode(155))
puts("\n\n\7\7 WRONG --  Node No 155 Is Valid \n\n\7\7"); 
else
puts("CORRECT -- Since Node 155 Is Not Valid"); 

if (Inventory.ValidNode(0))
puts("\n\n\7\7 WRONG --  Node No 0 Is Valid \n\n\7\7"); 
else
puts("CORRECT -- Since Node 0 Is Not Valid"); 

if (Inventory.ValidNode(-1))
puts("\n\n\7\7 WRONG --  Node No -1 Is Valid \n\n\7\7"); 
else
puts("CORRECT -- Since Node -1 Is Not Valid"); 

HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------

puts("\n\n*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("**********************  End TestDA_AVLTree1   *********************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************\n\n");
}




void TestDA_AVLTree2(void)
{
puts("\n\n*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("********************** Start TestDA_AVLTree2  *********************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************\n\n");Student
Students[30];
Part
Parts[80];
Auto
Autos[30];
Book
Books[10];
Client
Clients[10];

Clients[0].Set ("Donald", 111, 1, 16.50, 3.8);
Clients[1].Set ("Alex", 222, 1, 3.50, 1.8);
Clients[2].Set ("Ralph", 333, 1, 7.50, 2.8);
Clients[3].Set ("Tony", 444, 1, 10.50, 3.2);
Clients[4].Set ("Susan", 555, 1, 22.50, 4.0);

    Books[0].Set ("THE HOUSE", 11111);
    Books[1].Set ("THE 5TH HORSEMAN", 22222);
    Books[2].Set ("THE TENTH CIRCLE", 33333);
    Books[3].Set ("DIRTY BLONDE", 44444);
    Books[4].Set ("MARLEY & ME", 55555);
    Books[5].Set ("THE WORLD IS FLAT", 66666);

Students[0].Set("Brown, Chris", 101, MALE);
Students[1].Set("Weston, Clay", 102, MALE);
Students[2].Set("McBryde, Michael", 103, MALE);
Students[3].Set("Elsaifi, Leslie", 104, FEMALE);
Students[4].Set("Kelly, Nick", 105, MALE);
Students[5].Set("Wilson, Jennifer", 106, FEMALE);
Students[6].Set("Silliman, Mark", 107, MALE);
Students[7].Set("Merka, Lauren", 108, FEMALE);
Students[8].Set("Guest, Ben", 109, MALE);
Students[9].Set("Condon, Ryan", 200, MALE);
Students[10].Set("Bertles, Joe, Ryan", 201, MALE);
Students[11].Set("Gonzaba, Jodi", 202, FEMALE);
Students[12].Set("Crowe, Loren", 203, MALE);
Students[13].Set("Marquez, Angel", 204, MALE);
Students[14].Set("Houck, David", 205, MALE);
Students[15].Set("Ross, Garrett, David", 206, MALE);
Students[16].Set("Schwartz, Scott, David", 207, MALE);
Students[17].Set("Caille, Ryan", 208, MALE);
Students[18].Set("Schubet, Kurt", 209, MALE);
Students[19].Set("Canion, Todd", 300, MALE);
Students[20].Set("West, Paul", 301, MALE);
Students[21].Set("Haik, Adrienne", 302, FEMALE);
Students[22].Set("Swanson, Anna", 303, FEMALE);
Students[23].Set("Jones, Travis", 304, MALE);
Students[24].Set("Stansell, Kevin", 305, MALE);
Students[25].Set("Lara, Domingo", 306, MALE);
Students[26].Set("Rodriquez, Anthony", 307, MALE);
Students[27].Set("Mohajan, Rohit", 308, MALE);
Students[28].Set("Middleton, Phillip", 309, MALE);
Students[29].Set("Schwartz, Scott, David", 204, MALE);

Autos[0].Set("Corvette Stingray", 101, CONVERTABLE);
Autos[1].Set("Porche 911", 102, CONVERTABLE);
Autos[2].Set("VW", 103, CONVERTABLE);
Autos[3].Set("Limo", 104, COUP);
Autos[4].Set("Lincoln Continental", 105, CONVERTABLE);
Autos[5].Set("Maxima", 106, COUP);
Autos[6].Set("Mercury Cougar", 107, CONVERTABLE);
Autos[7].Set("Mustang", 108, COUP);
Autos[8].Set("Explorer", 109, CONVERTABLE);
Autos[9].Set("Lincoln Towncar", 200, CONVERTABLE);
Autos[10].Set("Chevrolet Capri", 201, CONVERTABLE);
Autos[11].Set("Jaguar", 202, COUP);
Autos[12].Set("Honda 2000", 203, CONVERTABLE);

Parts[1].Set("Basketball",       111, 3,  10,   25.00);
Parts[2].Set("Football",         105, 3,  15,   25.00);
Parts[3].Set("Tennis Balls",     127, 3,   6,    3.00);
Parts[4].Set("Golf Balls",       104, 3,  10,   12.00);
Parts[5].Set("Soccer Ball",      141, 3,   5,   40.00);
Parts[6].Set("GB Hard Drive",    120, 2,  12,   37.95);
Parts[7].Set("Microwave",        112, 1,  15,   59.80);
Parts[8].Set("Gas Stove",        136, 1,   6,  237.69);
Parts[9].Set("Cup",              156, 3,  23,    8.88);
Parts[10].Set("Baseball",        123, 3,  10,    8.00);
Parts[11].Set("Teather Ball",    155, 3,   4,   14.00);
Parts[12].Set("Golf Tees",       125, 3,  60,    2.00);
Parts[13].Set("Tennis Shoes",    101, 3,  10,  100.00);
Parts[14].Set("Ping Pong Balls", 154, 3,  10,    3.00);
Parts[15].Set("MotherBoard",     113, 2,  11,   55.00);
Parts[16].Set("SDRAM",           135, 2,  30,   40.01);
Parts[17].Set("Iron",            132, 1,  21,   38.77);
Parts[18].Set("Long Socks",      153, 3,  34,    9.99);
Parts[19].Set("CD-ROM",          110, 2,  11,   30.12);
Parts[20].Set("CD-RW",           124, 2,  26,   56.13);
Parts[21].Set("Thin Monitor",    140, 2,   5,   89.00);
Parts[22].Set("Large Monitor",   139, 2,   9,   78.99);
Parts[23].Set("Dish Washer",     117, 1,  10,  120.78);
Parts[24].Set("Tennis Racquet",  118, 3,   4,   80.00);
Parts[25].Set("Golf Club",       152, 3,  14,   49.00);
Parts[26].Set("Gym Bag",         151, 3,  10,   14.00);
Parts[27].Set("Golf Glove",      128, 3,  11,   14.06);
Parts[28].Set("Golf Bag",        150, 3,   5,   99.00);
Parts[29].Set("Squash Racquet",  119, 3,   2,   80.00);
Parts[30].Set("Squash Balls",    149, 3,   3,    8.00);
Parts[31].Set("Archery Set",     148, 3,   1,   25.00);
Parts[32].Set("Compound Bow",    102, 3,   1,   80.00);
Parts[33].Set("Arrows",          147, 3, 100,    6.00);
Parts[34].Set("Quiver",          131, 3,   2,   16.00);
Parts[35].Set("Racquet Balls",   146, 3,  15,    6.00);
Parts[36].Set("Baseball Bats",   106, 3,   4,   48.00);
Parts[37].Set("Golf Driver",     130, 3,   3,   99.00);
Parts[38].Set("Knee Pads",       103, 3,   4,    8.00);
Parts[39].Set("Soccer Cleats",   121, 3,   2,   48.00);
Parts[40].Set("Shin Guards",     137, 3,   5,   48.05);
Parts[41].Set("Printer",         145, 2,  14,   29.98);
Parts[42].Set("Laser Printer",   108, 2,  13,   43.99);
Parts[43].Set("Printer Cables",  144, 2,  12,    9.99);
Parts[44].Set("Tranportable Fan",116, 1,   6,   45.67);
Parts[45].Set("Dirt Devil",      114, 1,  11,   48.80);
Parts[46].Set("B-Ball Shoes",    143, 3,   9,  135.99);
Parts[47].Set("Case",            134, 2,   4,   20.00);
Parts[48].Set("Graphics Card",   142, 2,   7,   58.00);
Parts[49].Set("Sound Card",      107, 2,   4,   34.99);
Parts[50].Set("CD Player",       138, 1,  16,   57.75);
Parts[51].Set("Floppy Drive",    126, 2,   4,   12.00);
Parts[52].Set("Removeable Drive",122, 2,  12,   59.94);
Parts[53].Set("External zip",    129, 2,   8,   67.75);
Parts[54].Set("Floppy's",        115, 2,  99,     .50);
Parts[55].Set("Mouse",           109, 2,  35,    7.99);
Parts[56].Set("Keyboard",        133, 2,  44,   12.99);

// -------------------------------------------------------------------------------

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 5)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 5 *****************");
puts ("***************************** Inplace First  ***************************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <TreeHeader, int>  
Num ("Num.hf", "Num.nf", 3, 3);

Num.Display("\n\nDA_AVLTree <TreeHeader, int> Num is Empty\n");
if (Num.Inplace(4,500))
puts("\n\n\7\7 WRONG -- Should Not Be Able To Do Inplace With Header 4\n\7\7");
else
puts(" Correct -- We Can Not Do Inplace With Header 4");
if (Num.Inplace(0,500))
puts("\n\n\7\7 WRONG -- Should Not Be Able To Do Inplace With Header 0\n\7\7");
else
puts(" Correct -- We Can Not Do Inplace With Header 0");
if (Num.Inplace(-2,500))
puts("\n\n\7\7 WRONG -- Should Not Be Able To Do Inplace With Header -2\n\7\7");
else
puts(" Correct -- We Can Not Do Inplace With Header -2");
if (Num.Inplace(2,500))
Num.Display("\n\nDA_AVLTree <TreeHeader, int> Num = 500\n");
else
puts("\n\n\7\7 WRONG -- Should Be Able To Inplce 500 On Header 3\n\7\7");
puts ("=======================================================================");
puts ("=======================================================================");

  DA_AVLTree <AutoTreeHeader, Auto>  
NorthPark ("NorthPark.hf", "NorthPark.nf", 3, 3);
InitializeAutoHeaderFile(NorthPark.hfp);

NorthPark.Display("\n\nDA_AVLTree <AutoTreeHeader, Auto> NorthPark is Empty\n");
NorthPark.Inplace(2,Autos[1]);
NorthPark.Display("\n\nDA_AVLTree <AutoTreeHeader, Auto> NorthPark = Porche 911\n");
puts ("=======================================================================");
puts ("=======================================================================");

  DA_AVLTree <BookTreeHeader, Book>  
Library ("Library.hf", "Library.nf", 3, 3);
InitializeBookHeaderFile(Library.hfp);

Library.Display("\n\nDA_AVLTree <BookTreeHeader, Book> Library is Empty\n");
Library.Inplace(2,Books[1]);
Library.Display("\n\nDA_AVLTree <BookTreeHeader, Book> Library = The House\n");
puts ("=======================================================================");
puts ("=======================================================================");

DA_AVLTree <ClientTreeHeader, Client>  
SmithBarney ("SmithBarney.hf", "SmithBarney.nf", 3, 3);
InitializeClientHeaderFile(SmithBarney.hfp);

SmithBarney.Display("\n\nDA_AVLTree <ClientTreeHeader, Client> SmithBarney is Empty\n");
SmithBarney.Inplace(2,Clients[1]);
SmithBarney.Display("\n\nDA_AVLTree <ClientTreeHeader, Client> SmithBarney = Alex\n");
puts ("=======================================================================");
puts ("=======================================================================");

DA_AVLTree <IntegerTreeHeader, Integer>  
No ("No.hf", "No.nf", 3, 3);
InitializeIntegerHeaderFile(No.hfp);

No.Display("\n\nDA_AVLTree <IntegerTreeHeader, Integer> No is Empty\n");
No.Inplace(2,500);
No.Display("\n\nDA_AVLTree <IntegerTreeHeader, Integer> No = 500\n");
puts ("=======================================================================");
puts ("=======================================================================");

DA_AVLTree <PartTreeHeader, Part>  
Inventory ("Inventory.hf", "Inventory.nf", 4, 7);
InitializePartHeaderFile(Inventory.hfp);

Inventory.Display("\n\nDA_AVLTree <ClientTreeHeader, Part> Inventory is Empty\n");
Inventory.Inplace(2,Parts[1]);
Inventory.Display("\n\nDA_AVLTree <ClientTreeHeader, Part> Inventory = Basketball \n");
puts ("=======================================================================");
puts ("=======================================================================");
 
DA_AVLTree <StudentTreeHeader, Student>  
Trinity ("Trinity.hf", "Trinity.nf", 3, 3);
InitializeStudentHeaderFile(Trinity.hfp);

Trinity.Display("\n\nDA_AVLTree <StudentTreeHeader, Student> Trinity is Empty\n");
Trinity.Inplace(2,Students[1]);
Trinity.Display("\n\nDA_AVLTree <StudentTreeHeader, Student> Trinity = Clay Weston \n");
puts ("=======================================================================");
puts ("=======================================================================");

HitCarriageReturnToContinue();
}

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 8)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 8 *****************");
puts ("******************************** SetRight  ******************************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
No ("No.hf", "No.nf", 3, 3);
InitializeIntegerHeaderFile(No.hfp);

if (No.Inplace(2, 200))
No.Display("\n\nDA_AVLTree <IntegerTreeHeader, Integer> No = 200\n");
else
puts("\n\n\7\7 WRONG -- Unable To Inplace First 300 on Header 2\n\n\7\7"); 

if (No.SetRight(2, 300, 1)) 
No.Display("\n\nDA_AVLTree <IntegerTreeHeader, Integer> No = 200 -> 300\n");
else
puts("\n\n\7\7 WRONG -- Unable To Set 300 To The Right of Node 1 on Header 2\n\n\7\7"); 

if (No.SetRight(2, 400, 2))
No.Display("\n\nDA_AVLTree <IntegerTreeHeader, Integer> No = 200 -> 300 -> 400\n");
else
puts("\n\n\7\7 WRONG -- Unable To Set 400 To The Right of Node 2 on Header 2\n\n\7\7"); 

if (No.SetRight(2, 500, 3))
No.Display("\n\nDA_AVLTree <IntegerTreeHeader, Integer> No = 100 -> 200 -> 300 -> 400 -> 500\n");
else
puts("\n\n\7\7 WRONG -- Unable To Set 500 To The Right of Node 3 on Header 2\n\n\7\7"); 

if (No.SetRight(1, 1000, 4))
puts("\n\n\7\7 WRONG -- Header 1 Is Empty - Should Not Be Able To Do A SetRight\n\n\7\7"); 
else
puts("CORRECT -- Since Header 1 Is Empty, We Can Not Do A SetRight"); 

if (No.SetRight(0, 10, 3))
puts("\n\n\7\7 WRONG --  Header No 0 Is Invalid - Should Not Be Able To Do A SetRight \n\n\7\7"); 
else
puts("CORRECT -- Since Header 0 Is Invalid, We Can Not Do A SetRight"); 

if (No.SetRight(4, 10, 3))
puts("\n\n\7\7 WRONG --  Header No 4 Is Invalid - Should Not Be Able To Do A SetRight \n\n\7\7"); 
else
puts("CORRECT -- Since Header 4 Is Invalid, We Can Not Do A SetRight"); 

if (No.SetRight(-2, 10, 3))
puts("\n\n\7\7 WRONG --  Header No -2 Is Invalid - Should Not Be Able To Do A SetRight \n\n\7\7"); 
else
puts("CORRECT -- Since Header -2 Is Invalid, We Can Not Do A SetRight"); 

if (No.SetRight(2, 600, 3))
puts("\n\n\7\7 WRONG --  Father 3 Alredy Has A Right Son - Should Not Be Able To Do A SetRight \n\n\7\7"); 
else
puts("CORRECT -- Since Father 3 Alredy Has A Right Son, We Can Not Do A SetRight"); 

HitCarriageReturnToContinue();
}

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 9)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 9 *****************");
puts ("******************************** SetLeft  *****************************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");


DA_AVLTree <IntegerTreeHeader, Integer>  
No ("No.hf", "No.nf", 3, 3);
InitializeIntegerHeaderFile(No.hfp);

if (No.Inplace(2, 300))
No.Display("\n\nDA_AVLTree <IntegerTreeHeader, Integer> No = 300\n");
else
puts("\n\n\7\7 WRONG -- Unable To Inplace First 300 on Header 2\n\n\7\7"); 

if (No.SetLeft(2, 200, 1)) 
No.Display("\n\nDA_AVLTree <IntegerTreeHeader, Integer> No = 200 -> 300\n");
else
puts("\n\n\7\7 WRONG -- Unable To Set 200 To The Left of Node 1 on Header 2\n\n\7\7"); 

if (No.SetLeft(2, 100, 2))
No.Display("\n\nDA_AVLTree <IntegerTreeHeader, Integer> No = 100 -> 200 -> 300\n");
else
puts("\n\n\7\7 WRONG -- Unable To Set 100 To The Left of Node 2 on Header 2\n\n\7\7"); 

if (No.SetLeft(2, 50, 3))
No.Display("\n\nDA_AVLTree <IntegerTreeHeader, Integer> No = 50 -> 100 -> 200 -> 300\n");
else
puts("\n\n\7\7 WRONG -- Unable To Set 50 To The Left of Node 3 on Header 2\n\n\7\7"); 

if (No.SetLeft(1, 1000, 4))
puts("\n\n\7\7 WRONG -- Header 1 Is Empty - Should Not Be Able To Do A SetLeft\n\n\7\7"); 
else
puts("CORRECT -- Since Header 1 Is Empty, We Can Not Do A SetLeft"); 

if (No.SetLeft(0, 10, 3))
puts("\n\n\7\7 WRONG --  Header No 0 Is Invalid - Should Not Be Able To Do A SetLeft \n\n\7\7"); 
else
puts("CORRECT -- Since Header 0 Is Invalid, We Can Not Do A SetLeft"); 

if (No.SetLeft(4, 10, 3))
puts("\n\n\7\7 WRONG --  Header No 4 Is Invalid - Should Not Be Able To Do A SetLeft \n\n\7\7"); 
else
puts("CORRECT -- Since Header 4 Is Invalid, We Can Not Do A SetLeft"); 

if (No.SetLeft(-2, 10, 3))
puts("\n\n\7\7 WRONG --  Header No -2 Is Invalid - Should Not Be Able To Do A SetLeft \n\n\7\7"); 
else
puts("CORRECT -- Since Header -2 Is Invalid, We Can Not Do A SetLeft"); 

if (No.SetLeft(2, 10, 3))
puts("\n\n\7\7 WRONG --  Father 3 Alredy Has A Left Son - Should Not Be Able To Do A SetLeft \n\n\7\7"); 
else
puts("CORRECT -- Since Father 3 Alredy Has A Left Son, We Can Not Do A SetLeft"); 

HitCarriageReturnToContinue(); }


if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 10)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 10 ****************");
puts ("***************************** Simple Inplace  **************************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
No ("CompleteTree.hf", "CompleteTree.nf", 3, 3);
InitializeIntegerHeaderFile(No.hfp);

No.Display("\n\n No is Empty\n");
No.Inplace(1, 8);
No.Display("\n\n No = 8\n");
No.Inplace(1, 4);
No.Display("\n\n No = 4, 8\n");
No.Inplace(1, 2);
No.Display("\n\n No = 2, 4, 8\n");
No.Inplace(1, 6);
No.Display("\n\n No = 2, 4, 6, 8\n");
No.Inplace(1, 12);
No.Display("\n\n No = 2, 4, 6, 8, 12\n");
No.Inplace(1, 14);
No.Display("\n\n No = 2, 4, 6, 8, 12, 14\n");
No.Inplace(1, 10);
No.Display("\n\n No = 2, 4, 6, 8, 10, 12, 14\n");
No.Inplace(1, 15);
No.Display("\n\n No = 2, 4, 6, 8, 10, 12, 14, 15\n");
No.Inplace(1, 13);
No.Display("\n\n No = 2, 4, 6, 8, 10, 12, 13, 14, 15\n");
No.Inplace(1, 11);
No.Display("\n\n No = 2, 4, 6, 8, 10, 11, 12, 13, 14, 15\n");
No.Inplace(1, 9);
No.Display("\n\n No = 2, 4, 6, 8, 9, 10, 11, 12, 13, 14, 15\n");
No.Inplace(1, 7);
No.Display("\n\n No = 2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15\n");
No.Inplace(1, 5);
No.Display("\n\n No = 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15\n");
No.Inplace(1, 3);
No.Display("\n\n No = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15\n");
No.Inplace(1, 1);
No.Display("\n\n No = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15\n");

No.Inplace(3, 100);
No.Inplace(3, 50);
No.Inplace(3, 60);
No.Inplace(3, 70);
No.Inplace(3, 65);
No.Inplace(3, 63);
No.Inplace(3, 64);

No.QuickAndDirtyIntegerDisplay(1, "Header 1");
No.QuickAndDirtyIntegerDisplay(2, "Header 2");
No.QuickAndDirtyIntegerDisplay(3, "Header 3");

HitCarriageReturnToContinue();
}

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 11)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 11 ****************");
puts ("*************************** Inorder Traversal  *************************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
No ("CompleteTree.hf", "CompleteTree.nf");
No.InorderTraversalDisplay(1, "\nInorder 4-Level Complete Tree\n");
No.InorderTraversalDisplay(2, "\nInorder Empty Tree\n");
No.InorderTraversalDisplay(3, "\nInorder Skew Tree\n");

HitCarriageReturnToContinue();
}

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 12)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 12 ****************");
puts ("*************************** Prerder Traversal  *************************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
No ("CompleteTree.hf", "CompleteTree.nf");
No.PreorderTraversalDisplay(1, "\nPreorder 4-Level Complete Tree\n");
No.PreorderTraversalDisplay(2, "\nPreoder Empty Tree\n");
No.PreorderTraversalDisplay(3, "\nPreorder Skew Tree\n");

HitCarriageReturnToContinue();
}

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 13)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 13 ****************");
puts ("*************************** Postrder Traversal  ************************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
No ("CompleteTree.hf", "CompleteTree.nf");
No.PostorderTraversalDisplay(1, "\nPostorder 4-Level Complete Tree\n");
No.PostorderTraversalDisplay(2, "\nPostorder Empty Tree\n");
No.PostorderTraversalDisplay(3, "\nPostrder Skew Tree\n");

HitCarriageReturnToContinue();
}


if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 14)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 14 ****************");
puts ("****************************  Inplace Integer **************************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

# define MAXTREE 1000
DA_AVLTree <IntegerTreeHeader, Integer>  
Num ("Num.hf", "Num.nf", 3, 3);
InitializeIntegerHeaderFile(Num.hfp);
long int
* NoArray,
TempMax,
Counter,
RandNo;
int
NewNo;

NoArray = new long int [MAXTREE + 1];
TempMax = MAXTREE;

for (Counter = 1; Counter <= MAXTREE; Counter ++)
NoArray [Counter] = Counter;

for ( Counter = 1; Counter <= MAXTREE; Counter ++)
{
RandNo = rand() % TempMax + 1;
NewNo = NoArray[RandNo];
NoArray[RandNo] = NoArray[TempMax];
TempMax = TempMax - 1;

Num.Inplace(1,NewNo);
}
delete [] NoArray;

Num.QuickAndDirtyIntegerDisplay(1, "Array After 1000 Random Values 1-1000 - No Duplicates");
HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 15)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("****************** LINEAR_PROBE_DIAGNOSTICS_LEVEL = 15 ******************");
puts ("********************* Test Inorder Traversal Parts   *******************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");
DA_AVLTree <PartTreeHeader, Part>  
Inventory ("Inventory.hf", "Inventory.nf", 4, 10);
long int
Counter;

InitializePartHeaderFile(Inventory.hfp);
for (Counter = 1; Counter <= 56; Counter ++)
if (!Inventory.Inplace(Parts[Counter].DeptNo_(), Parts[Counter]))
puts("Unable To Insert Part!");


Inventory.InorderTraversalDisplay(1, "Contents of Inventory Header # 1");
Inventory.InorderTraversalDisplay(2, "Contents of Inventory Header # 2");
Inventory.InorderTraversalDisplay(3, "Contents of Inventory Header # 3");
Inventory.InorderTraversalDisplay(4, "Contents of Inventory Header # 4");
HitCarriageReturnToContinue();
}

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 16)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("****************** LINEAR_PROBE_DIAGNOSTICS_LEVEL = 16 ******************");
puts ("******************* Test Inorder Traversal Autos   ******************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");
DA_AVLTree <AutoTreeHeader, Auto>  
NorthPark ("NorthPark.hf", "NorthPark.nf", 3, 10);
AutoTreeHeader
Header;
long int
Counter;
char
Message[50];

InitializeAutoHeaderFile(NorthPark.hfp);
for (Counter = 0; Counter <= 12; Counter ++)
{
sprintf(Message, "Adding Autos[%d]", Counter);
if (Counter % 2 == 0)
NorthPark.Inplace(1, Autos[Counter]);
else
NorthPark.Inplace(2, Autos[Counter]);
// sprintf(Message, "Adding Autos[%d]", Counter);
// NorthPark.Display(Message);
}
NorthPark.InorderTraversalDisplay(1, "Contents of NorthPark Header # 1");
NorthPark.InorderTraversalDisplay(2, "Contents of NorthPark Header # 2");
HitCarriageReturnToContinue();
}



// -------------------------------------------------------------------------------

puts("\n\n*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("**********************  End TestDA_AVLTree2   *********************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************\n\n");

}

void TestDA_AVLTree3(void)
{
puts("\n\n*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("********************** Start TestDA_AVLTree3  *********************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************\n\n");

Part
Parts[80];

Parts[1].Set("Basketball",       111, 3,  10,   25.00);
Parts[2].Set("Football",         105, 3,  15,   25.00);
Parts[3].Set("Tennis Balls",     127, 3,   6,    3.00);
Parts[4].Set("Golf Balls",       104, 3,  10,   12.00);
Parts[5].Set("Soccer Ball",      141, 3,   5,   40.00);
Parts[6].Set("GB Hard Drive",    120, 2,  12,   37.95);
Parts[7].Set("Microwave",        112, 1,  15,   59.80);
Parts[8].Set("Gas Stove",        136, 1,   6,  237.69);
Parts[9].Set("Cup",              156, 3,  23,    8.88);
Parts[10].Set("Baseball",        123, 3,  10,    8.00);
Parts[11].Set("Teather Ball",    155, 3,   4,   14.00);
Parts[12].Set("Golf Tees",       125, 3,  60,    2.00);
Parts[13].Set("Tennis Shoes",    101, 3,  10,  100.00);
Parts[14].Set("Ping Pong Balls", 154, 3,  10,    3.00);
Parts[15].Set("MotherBoard",     113, 2,  11,   55.00);
Parts[16].Set("SDRAM",           135, 2,  30,   40.01);
Parts[17].Set("Iron",            132, 1,  21,   38.77);
Parts[18].Set("Long Socks",      153, 3,  34,    9.99);
Parts[19].Set("CD-ROM",          110, 2,  11,   30.12);
Parts[20].Set("CD-RW",           124, 2,  26,   56.13);
Parts[21].Set("Thin Monitor",    140, 2,   5,   89.00);
Parts[22].Set("Large Monitor",   139, 2,   9,   78.99);
Parts[23].Set("Dish Washer",     117, 1,  10,  120.78);
Parts[24].Set("Tennis Racquet",  118, 3,   4,   80.00);
Parts[25].Set("Golf Club",       152, 3,  14,   49.00);
Parts[26].Set("Gym Bag",         151, 3,  10,   14.00);
Parts[27].Set("Golf Glove",      128, 3,  11,   14.06);
Parts[28].Set("Golf Bag",        150, 3,   5,   99.00);
Parts[29].Set("Squash Racquet",  119, 3,   2,   80.00);
Parts[30].Set("Squash Balls",    149, 3,   3,    8.00);
Parts[31].Set("Archery Set",     148, 3,   1,   25.00);
Parts[32].Set("Compound Bow",    102, 3,   1,   80.00);
Parts[33].Set("Arrows",          147, 3, 100,    6.00);
Parts[34].Set("Quiver",          131, 3,   2,   16.00);
Parts[35].Set("Racquet Balls",   146, 3,  15,    6.00);
Parts[36].Set("Baseball Bats",   106, 3,   4,   48.00);
Parts[37].Set("Golf Driver",     130, 3,   3,   99.00);
Parts[38].Set("Knee Pads",       103, 3,   4,    8.00);
Parts[39].Set("Soccer Cleats",   121, 3,   2,   48.00);
Parts[40].Set("Shin Guards",     137, 3,   5,   48.05);
Parts[41].Set("Printer",         145, 2,  14,   29.98);
Parts[42].Set("Laser Printer",   108, 2,  13,   43.99);
Parts[43].Set("Printer Cables",  144, 2,  12,    9.99);
Parts[44].Set("Tranportable Fan",116, 1,   6,   45.67);
Parts[45].Set("Dirt Devil",      114, 1,  11,   48.80);
Parts[46].Set("B-Ball Shoes",    143, 3,   9,  135.99);
Parts[47].Set("Case",            134, 2,   4,   20.00);
Parts[48].Set("Graphics Card",   142, 2,   7,   58.00);
Parts[49].Set("Sound Card",      107, 2,   4,   34.99);
Parts[50].Set("CD Player",       138, 1,  16,   57.75);
Parts[51].Set("Floppy Drive",    126, 2,   4,   12.00);
Parts[52].Set("Removeable Drive",122, 2,  12,   59.94);
Parts[53].Set("External zip",    129, 2,   8,   67.75);
Parts[54].Set("Floppy's",        115, 2,  99,     .50);
Parts[55].Set("Mouse",           109, 2,  35,    7.99);
Parts[56].Set("Keyboard",        133, 2,  44,   12.99);


if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 31)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 31 ****************");
puts ("*********************  Calculate NoNodes At Each Level *****************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
Num ("Num-31.hf", "Num-31.nf", 3, 3);
long int
* NoArray,
TempMax,
Counter,
RandNo;
int
NewNo;

InitializeIntegerHeaderFile(Num.hfp);

Num.Inplace(1,100);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,80);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,60);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,40);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,120);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,140);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,160);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,90);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,110);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,70);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,85);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,95);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,105);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,130);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,115);
Num.NoNodesAtEachLevelTraversalDisplay (1);

Num.QuickAndDirtyIntegerDisplay(1, "Balanced Tree?");
HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------
if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 32)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("****************** LINEAR_PROBE_DIAGNOSTICS_LEVEL = 32 ******************");
puts ("********************* Display Inventory Distribution *******************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");
DA_AVLTree <PartTreeHeader, Part>  
Inventory ("Inventory-32.hf", "Inventory-32.nf", 4, 10);
long int
Counter;

InitializePartHeaderFile(Inventory.hfp);
for (Counter = 1; Counter <= 56; Counter ++)
if (!Inventory.Inplace(1, Parts[Counter]))
puts("Unable To Insert Part!");

Inventory.InorderTraversalDisplay(1, "Contents of Inventory Header # 1");
Inventory.NoNodesAtEachLevelTraversalDisplay (1, "Tree Distribution For Header 1");

Inventory.InorderTraversalDisplay(4, "Contents of Inventory Header # 4");
Inventory.NoNodesAtEachLevelTraversalDisplay (4, "Tree Distribution For Header 4");


HitCarriageReturnToContinue();
}


if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 33)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 33 ****************");
puts ("****************** Advanced Calculate NoNodes At Each Level ************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

# define MAXTREE 1000
DA_AVLTree <IntegerTreeHeader, Integer>  
Num ("Num-33.hf", "Num-33.nf", 3, 3);
InitializeIntegerHeaderFile(Num.hfp);
long int
* NoArray,
TempMax,
Counter,
RandNo;
int
NewNo;

NoArray = new long int [MAXTREE + 1];
TempMax = MAXTREE;

for (Counter = 1; Counter <= MAXTREE; Counter ++)
NoArray [Counter] = Counter;

for ( Counter = 1; Counter <= MAXTREE; Counter ++)
{
RandNo = rand() % TempMax + 1;
NewNo = NoArray[RandNo];
NoArray[RandNo] = NoArray[TempMax];
TempMax = TempMax - 1;

Num.Inplace(1,NewNo);
}
delete [] NoArray;

Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.QuickAndDirtyIntegerDisplay(1, "Array After 1000 Random Values 1-1000 - No Duplicates");

HitCarriageReturnToContinue();
}



if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 34)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 34 ****************");
puts ("****************************  Inplace Integer **************************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");


DA_AVLTree <IntegerTreeHeader, Integer>  
Num31 ("Num-31.hf", "Num-31.nf");
DA_AVLTree <PartTreeHeader, Part>  
Inventory32 ("Inventory-32.hf", "Inventory-32.nf");
DA_AVLTree <IntegerTreeHeader, Integer>  
Num33 ("Num-33.hf", "Num-33.nf");

puts("<===========================================================================>");
Num31.DisplayLoadBalanceStatistics (1, "Num31 Distribution");
puts("<===========================================================================>");
Inventory32.DisplayLoadBalanceStatistics (1, "Inventory32 Distribution");
puts("<===========================================================================>");
Num33.DisplayLoadBalanceStatistics (1, "Num32 Distribution");
puts("<===========================================================================>");



HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------

puts("\n\n*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("**********************  End TestDA_AVLTree3   *********************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************\n\n");

}


void TestDA_AVLTree4(void)
{
puts("\n\n*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("********************** Start TestDA_AVLTree4  *********************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************\n\n");

Part
Parts[80];

Parts[1].Set("Basketball",       111, 3,  10,   25.00);
Parts[2].Set("Football",         105, 3,  15,   25.00);
Parts[3].Set("Tennis Balls",     127, 3,   6,    3.00);
Parts[4].Set("Golf Balls",       104, 3,  10,   12.00);
Parts[5].Set("Soccer Ball",      141, 3,   5,   40.00);
Parts[6].Set("GB Hard Drive",    120, 2,  12,   37.95);
Parts[7].Set("Microwave",        112, 1,  15,   59.80);
Parts[8].Set("Gas Stove",        136, 1,   6,  237.69);
Parts[9].Set("Cup",              156, 3,  23,    8.88);
Parts[10].Set("Baseball",        123, 3,  10,    8.00);
Parts[11].Set("Teather Ball",    155, 3,   4,   14.00);
Parts[12].Set("Golf Tees",       125, 3,  60,    2.00);
Parts[13].Set("Tennis Shoes",    101, 3,  10,  100.00);
Parts[14].Set("Ping Pong Balls", 154, 3,  10,    3.00);
Parts[15].Set("MotherBoard",     113, 2,  11,   55.00);
Parts[16].Set("SDRAM",           135, 2,  30,   40.01);
Parts[17].Set("Iron",            132, 1,  21,   38.77);
Parts[18].Set("Long Socks",      153, 3,  34,    9.99);
Parts[19].Set("CD-ROM",          110, 2,  11,   30.12);
Parts[20].Set("CD-RW",           124, 2,  26,   56.13);
Parts[21].Set("Thin Monitor",    140, 2,   5,   89.00);
Parts[22].Set("Large Monitor",   139, 2,   9,   78.99);
Parts[23].Set("Dish Washer",     117, 1,  10,  120.78);
Parts[24].Set("Tennis Racquet",  118, 3,   4,   80.00);
Parts[25].Set("Golf Club",       152, 3,  14,   49.00);
Parts[26].Set("Gym Bag",         151, 3,  10,   14.00);
Parts[27].Set("Golf Glove",      128, 3,  11,   14.06);
Parts[28].Set("Golf Bag",        150, 3,   5,   99.00);
Parts[29].Set("Squash Racquet",  119, 3,   2,   80.00);
Parts[30].Set("Squash Balls",    149, 3,   3,    8.00);
Parts[31].Set("Archery Set",     148, 3,   1,   25.00);
Parts[32].Set("Compound Bow",    102, 3,   1,   80.00);
Parts[33].Set("Arrows",          147, 3, 100,    6.00);
Parts[34].Set("Quiver",          131, 3,   2,   16.00);
Parts[35].Set("Racquet Balls",   146, 3,  15,    6.00);
Parts[36].Set("Baseball Bats",   106, 3,   4,   48.00);
Parts[37].Set("Golf Driver",     130, 3,   3,   99.00);
Parts[38].Set("Knee Pads",       103, 3,   4,    8.00);
Parts[39].Set("Soccer Cleats",   121, 3,   2,   48.00);
Parts[40].Set("Shin Guards",     137, 3,   5,   48.05);
Parts[41].Set("Printer",         145, 2,  14,   29.98);
Parts[42].Set("Laser Printer",   108, 2,  13,   43.99);
Parts[43].Set("Printer Cables",  144, 2,  12,    9.99);
Parts[44].Set("Tranportable Fan",116, 1,   6,   45.67);
Parts[45].Set("Dirt Devil",      114, 1,  11,   48.80);
Parts[46].Set("B-Ball Shoes",    143, 3,   9,  135.99);
Parts[47].Set("Case",            134, 2,   4,   20.00);
Parts[48].Set("Graphics Card",   142, 2,   7,   58.00);
Parts[49].Set("Sound Card",      107, 2,   4,   34.99);
Parts[50].Set("CD Player",       138, 1,  16,   57.75);
Parts[51].Set("Floppy Drive",    126, 2,   4,   12.00);
Parts[52].Set("Removeable Drive",122, 2,  12,   59.94);
Parts[53].Set("External zip",    129, 2,   8,   67.75);
Parts[54].Set("Floppy's",        115, 2,  99,     .50);
Parts[55].Set("Mouse",           109, 2,  35,    7.99);
Parts[56].Set("Keyboard",        133, 2,  44,   12.99);

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 40)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 40 ****************");
puts ("**********************  Examine Stack With Tree Path *******************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
Num ("Num-31.hf", "Num-31.nf", 3,3);
long int
* NoArray,
TempMax,
Counter,
RandNo;
int
NewNo;

InitializeIntegerHeaderFile(Num.hfp);

Num.Inplace(1,100);
Num.NoNodesAtEachLevelTraversalDisplay (1, "NoNodes: 100");
Num.Display();
HitCarriageReturnToContinue();


Num.Inplace(1,80);
Num.NoNodesAtEachLevelTraversalDisplay (1, "NoNodes: 100,80");
Num.Display();
HitCarriageReturnToContinue();

Num.Inplace(1,60);
Num.NoNodesAtEachLevelTraversalDisplay (1, "NoNodes: 100,80,60");
Num.Display();
HitCarriageReturnToContinue();

Num.Inplace(1,40);
Num.NoNodesAtEachLevelTraversalDisplay (1, "NoNodes: 100,80,60,40");
Num.Display();
HitCarriageReturnToContinue();

Num.Inplace(1,20);
Num.NoNodesAtEachLevelTraversalDisplay (1, "NoNodes: 100,80,60,40, 20");
Num.Display();
HitCarriageReturnToContinue();

Num.Inplace(1,120);
Num.NoNodesAtEachLevelTraversalDisplay (1, "NoNodes: 100,80,60,40");
Num.Display();
HitCarriageReturnToContinue();

Num.Inplace(1,140);
Num.NoNodesAtEachLevelTraversalDisplay (1);

Num.Inplace(1,160);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,90);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,110);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,70);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,85);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,95);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,105);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,130);
Num.NoNodesAtEachLevelTraversalDisplay (1);
Num.Inplace(1,115);
Num.NoNodesAtEachLevelTraversalDisplay (1);

Num.QuickAndDirtyIntegerDisplay(1, "Balanced Tree?");
HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 41)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 41 ****************");
puts ("************************ Test Single Rotate Right A ********************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
Num ("Num-41.hf", "Num-41.nf", 3, 3);
long int
* NoArray,
TempMax,
Counter,
RandNo;
int
NewNo;

InitializeIntegerHeaderFile(Num.hfp);

printf("<===========================================================================>");
for (Counter = 63; Counter >= 1; Counter --) // You Might Want To Uncomment This For Development
{
// printf("<===========================================================================>");
// printf("\nNewInfo = %ld\n\n", Counter);
Num.Inplace(1,Counter);
// Num.NoNodesAtEachLevelTraversalDisplay (1,"NoNodes Distribution");
// Num.Display("Tree Display");
// Num.TreePtrs.Display("Father TreePtr Stack");
// Num.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
// printf("<===========================================================================>");
// HitCarriageReturnToContinue();
}
Num.NoNodesAtEachLevelTraversalDisplay (1,"NoNodes Distribution");
Num.Display("Tree Display");
Num.TreePtrs.Display("Father TreePtr Stack");
Num.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
printf("<===========================================================================>");
HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 42)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 42 ****************");
puts ("************************ Test Single Rotate Right B ********************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
Num ("Num-42.hf", "Num-42.nf", 3, 3);
long int
* NoArray,
TempMax,
Counter,
RandNo;
int
NewNo;

InitializeIntegerHeaderFile(Num.hfp);

for (Counter = 32767; Counter >= 1; Counter --)
Num.Inplace(1,Counter);
printf("<===========================================================================>");
Num.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
printf("No Single Right Rotations = %ld\n", Num.NoRotateRightRotations);

printf("<===========================================================================>");
HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 43)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 43 ****************");
puts ("************************ Test Single Rotate Left B ********************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
Num ("Num-43.hf", "Num-43.nf", 3, 3);
long int
* NoArray,
TempMax,
Counter,
RandNo;
int
NewNo;

InitializeIntegerHeaderFile(Num.hfp);

for (Counter = 1; Counter <= 32767; Counter ++)
Num.Inplace(1,Counter);
printf("<===========================================================================>");
Num.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
printf("No Single Left Rotations = %ld\n", Num.NoRotateLeftRotations);

printf("<===========================================================================>");
HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------
/*
if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 44)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 44 ****************");
puts ("********************* Test Double Rotate Right - Case A ****************");
puts ("************************* Down Left and Then Right *********************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
Num1("Num-44.hf", "Num-44.nf", 3, 3);

InitializeIntegerHeaderFile(Num1.hfp);

puts("<===========================================================================>");
puts("<============================= Case A-Root =================================>");
puts("<===========================================================================>");
Num1.Inplace(1,1000);
Num1.Inplace(1,600);
Num1.Inplace(1,800);
Num1.Display();
Num1.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num1.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
puts("<===========================================================================>");
HitCarriageReturnToContinue();

puts("<===========================================================================>");
puts("<=========================== Case A-Non-Root ===============================>");
puts("<===========================================================================>");
Num1.Inplace(1,400);
Num1.Inplace(1,500);
Num1.Display();
Num1.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num1.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
puts("<===========================================================================>");
HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 45)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 45 ****************");
puts ("********************* Test Double Rotate Right - Case B ****************");
puts ("************************* Down Left and Then Right *********************");
puts ("************************ Add To The Right Of Node C ********************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
Num1("Num-45.hf", "Num-45.nf", 3, 3);

InitializeIntegerHeaderFile(Num1.hfp);

puts("<===========================================================================>");
puts("<=========================== Case B [Root Right] ===========================>");
puts("<===========================================================================>");
Num1.Inplace(1,800);
Num1.Inplace(1,500);
Num1.Inplace(1,1000);
Num1.Inplace(1,400);
Num1.Inplace(1,600);
Num1.Inplace(1,700);
Num1.Display();
Num1.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num1.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
puts("<===========================================================================>");
HitCarriageReturnToContinue();

puts("<===========================================================================>");
puts("<========================= Case B [Non-Root Right] =========================>");
puts("<===========================================================================>");
Num1.Inplace(1,550);
Num1.Inplace(1,300);
Num1.Inplace(1,450);
Num1.Inplace(1,475);
Num1.Display();
Num1.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num1.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
puts("<===========================================================================>");
HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 46)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 46 ****************");
puts ("********************* Test Double Rotate Right - Case C ****************");
puts ("************************* Down Left and Then Right *********************");
puts ("************************ Add To The Left Of Node C *********************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
Num1("Num-46.hf", "Num-46.nf", 3, 3);

InitializeIntegerHeaderFile(Num1.hfp);

puts("<===========================================================================>");
puts("<=========================== Case C [Root Right] ===========================>");
puts("<===========================================================================>");
Num1.Inplace(1,800);
Num1.Inplace(1,500);
Num1.Inplace(1,1000);
Num1.Inplace(1,400);
Num1.Inplace(1,600);
Num1.Inplace(1,550);
Num1.Display();
Num1.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num1.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
puts("<===========================================================================>");
HitCarriageReturnToContinue();

puts("<===========================================================================>");
puts("<========================= Case C [Non-Root Right] =========================>");
puts("<===========================================================================>");
Num1.Inplace(1,550);
Num1.Inplace(1,300);
Num1.Inplace(1,450);
Num1.Inplace(1,475);
Num1.Display();
Num1.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num1.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
puts("<===========================================================================>");
HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 47)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 47 ****************");
puts ("********************* Test Double Rotate Left - Case A *****************");
puts ("************************* Down Right and Then Left *********************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
Num1("Num-47.hf", "Num-47.nf", 3, 3);

InitializeIntegerHeaderFile(Num1.hfp);

puts("<===========================================================================>");
puts("<============================= Case A-Root =================================>");
puts("<===========================================================================>");
Num1.Inplace(1,400);
Num1.Inplace(1,800);
Num1.Inplace(1,600);
Num1.Display();
Num1.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num1.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
puts("<===========================================================================>");
HitCarriageReturnToContinue();

puts("<===========================================================================>");
puts("<=========================== Case A-Non-Root ===============================>");
puts("<===========================================================================>");
Num1.Inplace(1,1000);
Num1.Inplace(1,900);
Num1.Display();
Num1.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num1.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
puts("<===========================================================================>");
HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 48)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 48 ****************");
puts ("********************* Test Double Rotate Left - Case B *****************");
puts ("************************* Down Right and Then Left *********************");
puts ("************************ Add To The Right Of Node C ********************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
Num1("Num-48.hf", "Num-48.nf", 3, 3);

InitializeIntegerHeaderFile(Num1.hfp);

puts("<===========================================================================>");
puts("<=========================== Case B [Root Right] ===========================>");
puts("<===========================================================================>");
Num1.Inplace(1,600);
Num1.Inplace(1,400);
Num1.Inplace(1,900);
Num1.Inplace(1,800);
Num1.Inplace(1,1000);
Num1.Inplace(1,850);
Num1.Display();
Num1.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num1.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
puts("<===========================================================================>");
HitCarriageReturnToContinue();

puts("<===========================================================================>");
puts("<========================= Case B [Non-Root Right] =========================>");
puts("<===========================================================================>");
Num1.Inplace(1,700);
Num1.Inplace(1,960);
Num1.Inplace(1,1200);
Num1.Inplace(1,980);
Num1.Display();
Num1.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num1.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
puts("<===========================================================================>");
HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 49)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 49 ****************");
puts ("********************* Test Double Rotate Right - Case C ****************");
puts ("************************* Down Left and Then Right *********************");
puts ("************************ Add To The Left Of Node C *********************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
Num1("Num-49.hf", "Num-49.nf", 3, 3);

InitializeIntegerHeaderFile(Num1.hfp);

puts("<===========================================================================>");
puts("<=========================== Case C [Root Right] ===========================>");
puts("<===========================================================================>");
Num1.Inplace(1,600);
Num1.Inplace(1,400);
Num1.Inplace(1,900);
Num1.Inplace(1,1000);
Num1.Inplace(1,800);
Num1.Inplace(1,700);
Num1.Display();
Num1.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num1.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
puts("<===========================================================================>");
HitCarriageReturnToContinue();

puts("<===========================================================================>");
puts("<========================= Case C [Non-Root Right] =========================>");
puts("<===========================================================================>");
Num1.Inplace(1,850);
Num1.Inplace(1,960);
Num1.Inplace(1,1200);
Num1.Inplace(1,920);
Num1.Display();
Num1.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num1.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
puts("<===========================================================================>");
HitCarriageReturnToContinue();
}

// -------------------------------------------------------------------------------

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 50)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 50 ****************");
puts ("************************ Test Stop When Father BF = 0 ******************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

DA_AVLTree <IntegerTreeHeader, Integer>  
Num1("Num-50.hf", "Num-50.nf", 3, 3);

InitializeIntegerHeaderFile(Num1.hfp);

Num1.Inplace(1,500);
Num1.Inplace(1,800);
Num1.Inplace(1,300);
Num1.Display();
Num1.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num1.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");

Num1.Inplace(1,700);
Num1.Inplace(1,200);
Num1.Inplace(1,900);
Num1.Display();
Num1.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num1.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");

Num1.Inplace(1,750);
Num1.Inplace(1,600);
Num1.Display();
Num1.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
Num1.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
puts("<===========================================================================>");
HitCarriageReturnToContinue();
}

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 51)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 51 ****************");
puts ("**************************  AVL Small Tree Test ************************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

# define MAXTREE 1023   // 18 Perfect Levels

DA_AVLTree <IntegerTreeHeader, Integer>  
Num ("Num-51.hf", "Num-51.nf", 3, 3);
InitializeIntegerHeaderFile(Num.hfp);
long int
* NoArray,
TempMax,
Counter,
RandNo;
int
NewNo;

NoArray = new long int [MAXTREE + 1];
TempMax = MAXTREE;

for (Counter = 1; Counter <= MAXTREE; Counter ++)
NoArray [Counter] = Counter;

for ( Counter = 1; Counter <= MAXTREE; Counter ++)
{
RandNo = rand() % TempMax + 1;
NewNo = NoArray[RandNo];
NoArray[RandNo] = NoArray[TempMax];
TempMax = TempMax - 1;

Num.Inplace(1,NewNo);
if (Counter % 1000 == 0)
printf ("%10ld", Counter);
}
delete [] NoArray;

Num.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
printf("\n\n\nNo Single Right Rotations  = %ld\n", Num.NoRotateRightRotations);
printf("No Single Left Rotations   = %ld\n", Num.NoRotateLeftRotations);
printf("No Dobuble Right Rotations = %ld\n", Num.NoDoubleRotateRightRotations);
printf("No Double Left Rotations   = %ld\n", Num.NoDoubleRotateLeftRotations);
printf("Total Rotations            = %ld\n", Num.NoRotateRightRotations +
                                         Num.NoDoubleRotateLeftRotations +
                                         Num.NoRotateLeftRotations +
 Num.NoDoubleRotateRightRotations);
Num.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");

if (Num.TestAVLIntegrity(1) == false)
printf("\n\n\n\n\7\7\7\7 AVL Tree Is Invalid! \n\n\n\7\7\7\7");
HitCarriageReturnToContinue();
}


if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 52)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("********************* DA_AVLTREE_DIAGNOSTICS_LEVEL = 52 ****************");
puts ("***************************  AVL Big Tree Test *************************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");

# define MAXTREE 262143   // 18 Perfect Levels

DA_AVLTree <IntegerTreeHeader, Integer>  
Num ("Num-52.hf", "Num-52.nf", 3, 3);
InitializeIntegerHeaderFile(Num.hfp);
long int
* NoArray,
TempMax,
Counter,
RandNo;
int
NewNo;

NoArray = new long int [MAXTREE + 1];
TempMax = MAXTREE;

for (Counter = 1; Counter <= MAXTREE; Counter ++)
NoArray [Counter] = Counter;

for ( Counter = 1; Counter <= MAXTREE; Counter ++)
{
RandNo = rand() % TempMax + 1;
NewNo = NoArray[RandNo];
NoArray[RandNo] = NoArray[TempMax];
TempMax = TempMax - 1;

Num.Inplace(1,NewNo);
if (Counter % 1000 == 0)
printf ("%10ld", Counter);
}
delete [] NoArray;

printf("\n\n\nNo Single Right Rotations  = %ld\n", Num.NoRotateRightRotations);
printf("No Single Left Rotations   = %ld\n", Num.NoRotateLeftRotations);
printf("No Dobuble Right Rotations = %ld\n", Num.NoDoubleRotateRightRotations);
printf("No Double Left Rotations   = %ld\n", Num.NoDoubleRotateLeftRotations);
printf("Total Rotations            = %ld\n", Num.NoRotateRightRotations +
                                         Num.NoDoubleRotateLeftRotations +
                                         Num.NoRotateLeftRotations +
 Num.NoDoubleRotateRightRotations);
Num.DisplayLoadBalanceStatistics (1,"NoNodes Distribution");
if (Num.TestAVLIntegrity(1) == false)
{
printf("\n\n\n\n\7\7\7\7 AVL Tree Is Invalid! \n\n\n\7\7\7\7");
Num.QuickAndDirtyIntegerDisplay(1, "Inorder Traversal");
}

HitCarriageReturnToContinue();
}

if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 53)
{
puts ("\n\n************************************************************************");
puts ("************************************************************************");
puts ("****************** LINEAR_PROBE_DIAGNOSTICS_LEVEL = 53 *****************");
puts ("*********************         Test AVL Parts          ******************");
puts ("************************************************************************");
puts ("************************************************************************\n\n");
DA_AVLTree <PartTreeHeader, Part>  
Inventory ("Inventory-53.hf", "Inventory.nf-53", 4, 10);
long int
Counter;

InitializePartHeaderFile(Inventory.hfp);
for (Counter = 1; Counter <= 56; Counter ++)
if (!Inventory.Inplace(2, Parts[Counter]))
puts("Unable To Insert Part!");

Inventory.InorderTraversalDisplay(2, "Contents of Inventory Header # 2");
printf("\n\n\nNo Single Right Rotations  = %ld\n", Inventory.NoRotateRightRotations);
printf("No Single Left Rotations   = %ld\n", Inventory.NoRotateLeftRotations);
printf("No Dobuble Right Rotations = %ld\n", Inventory.NoDoubleRotateRightRotations);
printf("No Double Left Rotations   = %ld\n", Inventory.NoDoubleRotateLeftRotations);
printf("Total Rotations            = %ld\n", Inventory.NoRotateRightRotations +
                                         Inventory.NoDoubleRotateLeftRotations +
                                         Inventory.NoRotateLeftRotations +
         Inventory.NoDoubleRotateRightRotations);
Inventory.DisplayLoadBalanceStatistics (2,"NoNodes Distribution");
if (Inventory.TestAVLIntegrity(2) == false)
printf("\n\n\n\n\7\7\7\7 AVL Tree Is Invalid! \n\n\n\7\7\7\7");
HitCarriageReturnToContinue();
}
*/
// -------------------------------------------------------------------------------

puts("\n\n*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("**********************  End TestDA_AVLTree4   *********************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************\n\n");
}
# endif // DA_AVLTREE_DIAGNOSTICS_LEVEL ---------------------------------

Output & Testing

1] Do Single Rotate Right. Copy

4] Comment out all of the diagnostic testing for DA_AVLTREE_DIAGNOSTICS_LEVEL >= 44

5] Make sure that you carefully examine the diagnostic testing for all levels <= 43

6] Set DA_AVLTREE_DIAGNOSTICS_LEVEL = 42

7] Run the program and print the output.

2] You must print all files using New Courier 8 point font.

3] Print Output.txt , DA_AVLTree.hpp, DA_AVLTree.cpp, AVLNode.hpp and AVLTreeNode.cpp.

4 Back up on at least two systems. Put folder in each account on Ananke. If something happens to Ananke, burn the folder on a cd and include it with your folder when you turn it in.


5] 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!

Turn In The Following [Staple or Bind In This Order!]

A]  Copy of Page 1 assignment sheet. Using an ink pen, print your name(s) and sign this lab at the top.

B] Listings Output.txt , DA_AVL_Tree.hpp, DA_AVL_Tree.cpp, AVLNode.hpp and AVLTreeNode.cpp.

You must print all files using New Courier 8 point font.