home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_11_02 / 1102050a < prev    next >
Text File  |  1992-06-04  |  2KB  |  97 lines
  1. #include <stdio.h>
  2.  
  3. /* TREE STRUCT: GENERIC BINARY TREE NODE */
  4. typedef struct treenode {
  5.   struct treenode *left;
  6.   struct treenode *right;
  7.   /* Data is unimportant ...*/
  8. } TREENODE;
  9.  
  10. /* STATIC VARIABLES */
  11. static int       list_num;
  12. static TREENODE  list_base;
  13. static TREENODE *list_tail;
  14. static TREENODE *root;
  15. static int       left;
  16.  
  17. /*list_num  IS SIMPLY A COUNTER OF HOW MANY ITEMS HAVE 
  18.             BEEN ADDED TO THE LIST.
  19.   list_base IS USED AS A DUMMY NODE AT THE HEAD OF THE 
  20.             LIST TO PREVENT TESTING FOR A NULL ROOT 
  21.             EVERY TIME A NODE IS ADDED TO THE LIST.
  22.   list_tail IS USED AS A POINTER TO THE LAST NODE IN 
  23.             THE LINKED LIST.
  24.   root      IS USED AS A POINTER TO THE NODE AT THE 
  25.             HEAD OF THE LIST.
  26.   left      IS A BOOLEAN TO KEEP TRACK OF WHICH WAY WE 
  27.             ARE GOING IN THE TREE SO THAT WE DIVIDE 
  28.             UNEVEN LISTS CORRECTLY. ALTHOUGH IT WOULD 
  29.             BE MORE CLEAR TO USE A PARAMETER, THE 
  30.             ROUTINE IS FINISHED WITH left BEFORE IT 
  31.             RECURSES (IT'S NO LONGER USING IT) AND 
  32.             MAKING IT STATIC REDUCES THE STACK SIZE 
  33.             REQUIRED FOR THE RECURSION. */
  34.  
  35. /* Function prototypes */
  36.        void     *optree    (void *);
  37. static void      list_build(TREENODE *);
  38. static TREENODE *form_tree (int);
  39.  
  40. /* OPTIMIZE A TREE */
  41. void *optree(void *opt_root)
  42. {
  43.   if (opt_root == NULL) return(NULL);
  44.  
  45.   list_tail = &list_base;
  46.   list_num  = 0;
  47.  
  48.   list_build(opt_root);
  49.  
  50.   root = list_base.right;
  51.  
  52.   left = 0;
  53.   return((void *) form_tree(list_num));
  54. }
  55.  
  56. /* FORM AN OPTIMIZED TREE FROM LIST */
  57. TREENODE *form_tree(int num)
  58. {
  59.   int middle;
  60.   TREENODE *ptr;
  61.  
  62.   middle = (num >> 1);   /* (num / 2) */
  63.  
  64.   /* SPECIAL 5-NODE CASE */
  65.   if(num == 5) middle++;
  66.  
  67.   /* LEAN BRANCH TO CENTER OF TREE */
  68.   if(left) middle = num - middle - 1; 
  69.  
  70.   /* REMOVE LEFT SUBTREE FROM LIST */
  71.   left = 1;
  72.   ptr = (middle > 0) ? form_tree(middle) : NULL;
  73.   root->left = ptr;
  74.  
  75.   /* REMOVE THIS NODE FROM LIST */
  76.   ptr = root;
  77.   root = root->right;
  78.  
  79.   /* REMOVE RIGHT SUBTREE FROM LIST */
  80.   left = 0;
  81.   middle = num - middle - 1;
  82.   ptr->right = (middle > 0) ? form_tree(middle) : NULL;
  83.   return ptr;
  84. }
  85.  
  86. /* FLATTEN TREE INTO LINKED LIST */
  87. void list_build(TREENODE *node)
  88. {
  89.   if(node->left)  list_build(node->left);
  90.  
  91.   list_tail->right = node;
  92.   list_tail = node;
  93.   list_num++;
  94.  
  95.   if(node->right) list_build(node->right);
  96. }
  97.