home *** CD-ROM | disk | FTP | other *** search
/ Graphics Programming Black Book (Special Edition) / BlackBook.bin / disk1 / source / chapter59 / l59_5.c < prev   
C/C++ Source or Header  |  1997-06-18  |  2KB  |  80 lines
  1. // Sample program to exercise and time the performance of
  2. // implementations of WalkTree().
  3. // Tested with 32-bit Visual C++ 1.10.
  4.  
  5. #include <stdio.h>
  6. #include <conio.h>
  7. #include <stdlib.h>
  8. #include <time.h>
  9. #include "tree.h"
  10.  
  11. long VisitCount = 0;
  12.  
  13. void main(void);
  14. void BuildTree(NODE *pNode, int RemainingDepth);
  15. extern void WalkTree(NODE *pRootNode);
  16.  
  17. void main()
  18. {
  19.    NODE RootNode;
  20.    int i;
  21.    long StartTime;
  22.  
  23.    // Build a sample tree
  24.  
  25.    BuildTree(&RootNode, 14);
  26.  
  27.    // Walk the tree 1000 times and see how long it takes
  28.  
  29.    StartTime = time(NULL);
  30.  
  31.    for (i=0; i<1000; i++)
  32.    {
  33.       WalkTree(&RootNode);
  34.    }
  35.  
  36.    printf("Seconds elapsed: %ld\n",
  37.            time(NULL) - StartTime);
  38.    getch();
  39. }
  40.  
  41. //
  42. // Function to add right and left subtrees of the
  43. // specified depth off the passed-in node.
  44. //
  45. void BuildTree(NODE *pNode, int RemainingDepth)
  46. {
  47.    if (RemainingDepth == 0)
  48.    {
  49.       pNode->pLeftChild = NULL;
  50.       pNode->pRightChild = NULL;
  51.    }
  52.    else
  53.    {
  54.       pNode->pLeftChild = malloc(sizeof(NODE));
  55.       if (pNode->pLeftChild == NULL)
  56.       {
  57.          printf("Out of memory\n");
  58.          exit(1);
  59.       }
  60.       pNode->pRightChild = malloc(sizeof(NODE));
  61.       if (pNode->pRightChild == NULL)
  62.       {
  63.          printf("Out of memory\n");
  64.          exit(1);
  65.       }
  66.  
  67.       BuildTree(pNode->pLeftChild, RemainingDepth - 1);
  68.       BuildTree(pNode->pRightChild, RemainingDepth - 1);
  69.    }
  70. }
  71.  
  72. //
  73. // Node-visiting function so WalkTree() has something to
  74. // call.
  75. //
  76. void Visit(NODE *pNode)
  77. {
  78.    VisitCount++;
  79. }
  80.