home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_10_07 / 1007068b < prev    next >
Text File  |  1992-05-13  |  5KB  |  229 lines
  1. Listing 2
  2.  
  3.  
  4. /* ----------------------------------------------------------- */
  5.  
  6. #include <stdio.h>
  7.  
  8. typedef struct node {
  9.     char value;
  10.     struct node *left_child;
  11.     struct node *right_child;
  12. } Node;
  13.  
  14. void prt_tree_prefix_order(Node *tree);
  15. void prt_tree_infix_order(Node *tree);
  16. void prt_tree_postfix_order(Node *tree);
  17.  
  18. void push(Node *value);
  19. Node *pop(void);
  20.  
  21. /* ----------------------------------------------------------- */
  22.  
  23. main()
  24. {
  25.     static Node tree[] = {
  26.         {'*', &tree[1], &tree[2]},    /* [0] */
  27.         {'+', &tree[3], &tree[4]},    /* [1] */
  28.         {'-', &tree[5], &tree[6]},    /* [2] */
  29.         {'A',     NULL,     NULL},    /* [3] */
  30.         {'B',     NULL,     NULL},    /* [4] */
  31.         {'C',     NULL,     NULL},    /* [5] */
  32.         {'/', &tree[7], &tree[8]},    /* [6] */
  33.         {'D',     NULL,     NULL},    /* [7] */
  34.         {'E',     NULL,     NULL}    /* [8] */
  35.     };
  36.  
  37.     prt_tree_prefix_order(tree);
  38.     prt_tree_infix_order(tree);
  39.     prt_tree_postfix_order(tree);
  40.  
  41.     return 0;
  42. }
  43.  
  44. /* --------------------------------------------------------------
  45.  
  46. PRT_TREE_PREFIX_ORDER: The steps to traverse a binary tree in prefix
  47. order and to display the value of each node are:
  48.  
  49. A.  Initialize a pointer to the root of the tree.
  50.  
  51. B.  Push a null sentinel on the stack.
  52.  
  53. C.  Process the whole tree (until we run into the null sentinel we 
  54.     placed on the stack in Step B. We do this by going down the left 
  55.     branch as far as we can, then down the right branch until we come 
  56.     to another left branch.
  57.  
  58. D.  Display node's value.
  59.  
  60. E.  If the current node has a right branch push the pointer to that 
  61.     branch on the stack.
  62.  
  63. F.  If the current node has a left branch follow that branch.
  64.  
  65. G.  If the current node is a leaf (terminal) node or has no left 
  66.     branch, pop a saved (right branch) value back off the stack
  67.     and start traversing the subtree to the right.
  68.  
  69. -------------------------------------------------------------- */
  70.  
  71. void prt_tree_prefix_order(Node *tree)
  72. {
  73. /*A*/    const Node *ptr = tree;
  74.  
  75. /*B*/    push(NULL);
  76.  
  77. /*C*/    while (ptr != NULL) {
  78. /*D*/        printf("%c", ptr->value);
  79. /*E*/        if (ptr->right_child != NULL) {
  80.             push(ptr->right_child);
  81.         }
  82. /*F*/        if (ptr->left_child != NULL) {
  83.             ptr = ptr->left_child;
  84.         }
  85. /*G*/        else {
  86.             ptr = pop();
  87.         }
  88.     }
  89.     putchar('\n');
  90. }
  91.  
  92. /* --------------------------------------------------------------
  93.  
  94. PRT_TREE_INFIX_ORDER: The steps to traverse a binary tree in infix
  95. order and to display the value of each node are:
  96.  
  97. A.  Initialize a pointer to the root of the tree.
  98.  
  99. B.  Push a null sentinel on the stack.
  100.  
  101. C.  Push the whole left subtree on the stack.
  102.  
  103. D.  Start backtracking by popping off last node pushed.
  104.  
  105. E.  Backtrack until we run into the sentinel placed on the stack in
  106.     Step B.
  107.  
  108. F.  Display node's value.
  109.  
  110. G.  If the current node has a right branch follow that branch and go
  111.     to Step C.
  112.  
  113. H.  Pop the next node off stack.
  114.  
  115. -------------------------------------------------------------- */
  116.  
  117. void prt_tree_infix_order(Node *tree)
  118. {
  119. /*A*/    Node *ptr = tree;
  120.  
  121. /*B*/    push(NULL);
  122.  
  123. /*C*/
  124. loop:    while (ptr != NULL) {
  125.         push(ptr);
  126.         ptr = ptr->left_child;
  127.     }
  128.  
  129. /*D*/    ptr = pop();
  130. /*E*/    while (ptr != NULL) {
  131. /*F*/        printf("%c", ptr->value);
  132. /*G*/        if (ptr->right_child != NULL) {
  133.             ptr = ptr->right_child;
  134.             goto loop;
  135.         }
  136. /*H*/        ptr = pop();
  137.     }
  138.     putchar('\n');
  139. }
  140.  
  141. /* --------------------------------------------------------------
  142.  
  143. PRT_TREE_POSTFIX_ORDER: The steps to traverse a binary tree in postfix
  144. order and to display the value of each node are:
  145.  
  146. A.  Initialize a pointer to the root of the tree.
  147.  
  148. B.  Push a null sentinel on the stack.
  149.  
  150. C.  Push the whole left subtree on the stack.
  151.  
  152. D.  Push current node pointer on stack.
  153.  
  154. E.  If the current node has a right branch push the pointer to that 
  155.     branch on the stack and also push a special marker.  This is
  156.     achieved by allocating a dummy variable `marker' so we can use its 
  157.     address as a unique special pointer.
  158.  
  159. F.  Follow the left branch.
  160.  
  161. G.  Pop a pointer off stack.
  162.  
  163. H.  Display node's value and keep popping off the stack until we 
  164.     either run into the null sentinel (end of stack) or the special 
  165.     marker.
  166.  
  167. I.  If we found a special marker, pop the associated pointer and go to 
  168.     Step C. Otherwise, we must have reached the null sentinel so we're 
  169.     done.
  170.  
  171. -------------------------------------------------------------- */
  172.  
  173. void prt_tree_postfix_order(Node *tree)
  174. {
  175. /*A*/    Node *ptr = tree;
  176.     Node marker;
  177.  
  178. /*B*/    push(NULL);
  179.  
  180. /*C*/
  181. loop:    while (ptr != NULL) {
  182. /*D*/        push(ptr);
  183. /*E*/        if (ptr->right_child != NULL) {
  184.             push(ptr->right_child);
  185.             push(&marker);
  186.         }
  187. /*F*/        ptr = ptr->left_child;
  188.     }
  189. /*G*/    ptr = pop();
  190. /*H*/    while (ptr != NULL && ptr != &marker) {
  191.         printf("%c", ptr->value);
  192.         ptr = pop();
  193.     }
  194. /*I*/    if (ptr == &marker) {
  195.         ptr = pop();
  196.         goto loop;
  197.     }
  198.     putchar('\n');
  199. }
  200.  
  201. /* ----------------------------------------------------------- */
  202.  
  203. #define STACK_SIZE 30
  204.  
  205. static Node *stack[STACK_SIZE];
  206.  
  207. static size_t stack_ptr = 0;
  208.  
  209. void push(Node *value)
  210. {
  211.     if (stack_ptr == STACK_SIZE)
  212.         printf("Stack is full\n");
  213.     else
  214.         stack[stack_ptr++] = value;
  215. }
  216.  
  217. Node *pop(void)
  218. {
  219.     if (stack_ptr == 0) {
  220.         printf("Stack is empty\n");
  221.         return 0;
  222.     }
  223.  
  224.     return stack[--stack_ptr];
  225. }
  226.  
  227. /* ----------------------------------------------------------- */
  228.  
  229.