home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2468 < prev    next >
Encoding:
Text File  |  1992-08-25  |  3.0 KB  |  93 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!gumby!wupost!uwm.edu!csd4.csd.uwm.edu!markh
  3. From: markh@csd4.csd.uwm.edu (Mark)
  4. Subject: Re: Teaching the basics
  5. Message-ID: <1992Aug25.174243.10436@uwm.edu>
  6. Sender: news@uwm.edu (USENET News System)
  7. Organization: Computing Services Division, University of Wisconsin - Milwaukee
  8. References: <1992Aug19.154830.11787@uwm.edu> <MJN.92Aug23031941@pseudo.uucp> <7116@charon.cwi.nl>
  9. Date: Tue, 25 Aug 1992 17:42:43 GMT
  10. Lines: 81
  11.  
  12. In article <7116@charon.cwi.nl> tromp@cwi.nl (John Tromp) writes:
  13. >>On top of it all, the recursive version does not have an arbitrary
  14. >>limit on the number of disks, and can be easily translated to any
  15. >>language supporting recursion.
  16. >
  17. >Well, nobody in his right mind would ever run hanoi on 32 discs or more:-)
  18. >
  19. >One of the prime applications of recursion, IMHO,
  20. >and where you cannot hope to replace it by anything else,
  21. >is in a tree search algorithm like alpha beta or plain old minimax.
  22.  
  23. Wrong.  In fact, the non-recursive version (tree search) is far smaller and
  24. simpler.  No stacks either.
  25.  
  26. #include <malloc.h>
  27. #include <stdio.h>
  28.  
  29. typedef struct Tree *Tree;
  30. struct Tree {
  31.    char *S; int Key, State;
  32.    Tree Left, Right;
  33. };
  34. Tree Root;
  35.  
  36. Tree Find(int Key) {
  37.    Tree Prev, Cur;
  38.    for (Prev = 0, Cur = Root; Cur != Prev; ) {
  39.       if (Cur->Key == Key) return Cur;
  40.       Prev = Cur, Cur = (Cur->Key < Key)? Cur->Left: Cur->Right;
  41.    }
  42.    Cur = (Tree)malloc(sizeof *Cur);      /* Add in your own error checks */
  43.    Cur->Key = Key, Cur->State = 0;
  44.    Cur->Left = Cur->Right = Cur;
  45.    if (Prev == 0) Root = Cur;
  46.    else if (Prev->Key < Key) Prev->Left = Cur; else Prev->Right = Cur;
  47.    return Cur;
  48. }
  49.  
  50. #define PRE_ORDER  0
  51. #define IN_ORDER   1
  52. #define POST_ORDER 2
  53.  
  54. #define BACKWARDS 0
  55. #define FORWARDS  1
  56. void Traverse(int Dir, int Order) {
  57.    Tree Prev, Cur;
  58.    for (Prev = 0, Cur = Root; Cur != 0; ) {
  59.       Tree T;
  60.       if (Cur->State == Order) printf(" %s", Cur->S);
  61.       Cur->State = (Cur->State + 1)%3;
  62.       if (Dir == BACKWARDS) {
  63.          T = Cur->Left, Cur->Left = Cur->Right,
  64.          Cur->Right = Prev, Prev = Cur, Cur = T;
  65.       } else {
  66.          T = Cur->Right, Cur->Right = Cur->Left,
  67.          Cur->Left = Prev, Prev = Cur, Cur = T;
  68.       }
  69.    }
  70. }
  71.  
  72. main() {
  73.    Tree T0, T1, T2, T3, T4, T5, T6, T7;
  74.    Root = 0;
  75.    T3 = Find(3), T0 = Find(0), T4 = Find(4), T6 = Find(6),
  76.    T5 = Find(5), T1 = Find(1), T7 = Find(7), T2 = Find(2);
  77.    T0->S = "This", T1->S = "is", T2->S = "a", T3->S = "non",
  78.    T4->S = "recursive", T5->S = "tree", T6->S = "traversal",
  79.    T7->S = "routine";
  80.    printf("Backwards,  pre order:"); Traverse(BACKWARDS, PRE_ORDER);
  81.    putchar('\n');
  82.    printf("Backwards, post order:"); Traverse(BACKWARDS, POST_ORDER);
  83.    putchar('\n');
  84.    printf("Backwards,   in order:"); Traverse(BACKWARDS, IN_ORDER);
  85.    putchar('\n');
  86.    printf("Forwards,   pre order:"); Traverse(FORWARDS,  PRE_ORDER);
  87.    putchar('\n');
  88.    printf("Forwards,  post order:"); Traverse(FORWARDS,  POST_ORDER);
  89.    putchar('\n');
  90.    printf("Forwards,    in order:"); Traverse(FORWARDS,  IN_ORDER);
  91.    putchar('\n');
  92. }
  93.