home *** CD-ROM | disk | FTP | other *** search
/ Graphics Programming Black Book (Special Edition) / BlackBook.bin / disk1 / source / chapter59 / l59_4.c < prev    next >
C/C++ Source or Header  |  1997-06-18  |  3KB  |  79 lines
  1. // Function to inorder walk a tree, using data recursion.
  2. // No stack overflow testing is performed.
  3. // Tested with 32-bit Visual C++ 1.10.
  4.  
  5. #include <stdlib.h>
  6. #include "tree.h"
  7.  
  8. #define MAX_PUSHED_NODES   100
  9.  
  10. extern void Visit(NODE *pNode);
  11.  
  12. void WalkTree(NODE *pNode)
  13. {
  14.    NODE *NodeStack[MAX_PUSHED_NODES];
  15.    NODE **pNodeStack;
  16.  
  17.    // Make sure the tree isn't empty
  18.    if (pNode != NULL)
  19.    {
  20.       NodeStack[0] = NULL;  // push "stack empty" value
  21.       pNodeStack = NodeStack + 1;
  22.  
  23.       for (;;)
  24.       {
  25.          // If the current node has a left child, push
  26.          // the current node and descend to the left
  27.          // child to start traversing the left subtree.
  28.          // Keep doing this until we come to a node
  29.          // with no left child; that's the next node to
  30.          // visit in inorder sequence
  31.          while (pNode->pLeftChild != NULL)
  32.          {
  33.             *pNodeStack++ = pNode;
  34.             pNode = pNode->pLeftChild;
  35.          }
  36.  
  37.          // We're at a node that has no left child, so
  38.          // visit the node, then visit the right
  39.          // subtree if there is one, or the last-
  40.          // pushed node otherwise; repeat for each
  41.          // popped node until one with a right
  42.          // subtree is found or we run out of pushed
  43.          // nodes (note that the left subtrees of
  44.          // pushed nodes have already been visited, so
  45.          // they're equivalent at this point to nodes
  46.          // with no left children)
  47.          for (;;)
  48.          {
  49.             Visit(pNode);
  50.  
  51.             // If the node has a right child, make
  52.             // the child the current node and start
  53.             // traversing that subtree; otherwise, pop
  54.             // back up the tree, visiting nodes we
  55.             // passed on the way down, until we find a
  56.             // node with a right subtree to traverse
  57.             // or run out of pushed nodes and are done
  58.             if (pNode->pRightChild != NULL)
  59.             {
  60.                // Current node has a right child;
  61.                // traverse the right subtree
  62.                pNode = pNode->pRightChild;
  63.                break;
  64.             }
  65.  
  66.             // Pop the next node from the stack so
  67.             // we can visit it and see if it has a
  68.             // right subtree to be traversed
  69.             if ((pNode = *--pNodeStack) == NULL)
  70.             {
  71.                // Stack is empty and the current node
  72.                // has no right child; we're done
  73.                return;
  74.             }
  75.          }
  76.       }
  77.    }
  78. }
  79.