home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 3 / 3147 / avl.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-03-29  |  2.0 KB  |  77 lines
  1. /**
  2. *  avl.h -- public types and external declarations for avl trees
  3. *
  4. *  Created 03/01/89 by Brad Appleton
  5. *
  6. * ^{Mods:* }
  7. * 
  8. * Fri Jul 14 13:54:12 1989, Rev 1.0, brad(0165)
  9. * 
  10. **/
  11.   
  12. #ifndef AVL_H
  13. #define AVL_H
  14.  
  15. #ifdef __STDC__
  16. # define _P(x)  x
  17. #else
  18. # define _P(x)  /*x*/
  19. #endif
  20.  
  21.        /* definition of traversal type */
  22. typedef  enum  { PREORDER, INORDER, POSTORDER }  VISIT;
  23.   
  24.   
  25.        /* definition of sibling order type */
  26. typedef  enum  { LEFT_TO_RIGHT, RIGHT_TO_LEFT }  SIBLING_ORDER;
  27.   
  28.   
  29.        /* definition of node type */
  30. typedef  enum  { IS_TREE, IS_LBRANCH, IS_RBRANCH, IS_LEAF, IS_NULL }  NODE;
  31.   
  32.   
  33.        /* definition of opaque type for AVL trees */
  34. typedef  void  *AVL_TREE;
  35.   
  36.   
  37. #ifndef NEXTERN
  38.   
  39.      /* Constructor and Destructor functions for AVL trees:
  40.      *          avlfree is a macro for avldispose in the fashion
  41.      *          of free(). It assumes certain default values 
  42.      *          (shown below) for the deallocation function and
  43.      *          for the order in which children are traversed.
  44.      */
  45. extern AVL_TREE     avlinit    _P( int(*) (), unsigned(*)() );
  46. extern void         avldispose _P( AVL_TREE *, void(*) (), SIBLING_ORDER );
  47. #define avlfree(x)  avldispose _P( &(x), free, LEFT_TO_RIGHT )
  48.     
  49.   
  50.        /* Routine for manipulating/accessing each data item in a tree */
  51. extern void      avlwalk  _P( AVL_TREE, void(*) (), SIBLING_ORDER );
  52.   
  53.   
  54.        /* Routine for obtaining the size of an AVL tree */
  55. extern int       avlcount  _P( AVL_TREE );
  56.   
  57.   
  58.        /* Routines to search for a given item */
  59. extern void     *avlins  _P( void *, AVL_TREE );
  60. extern void     *avldel  _P( void *, AVL_TREE );
  61. extern void     *avlfind _P( void *, AVL_TREE );
  62.   
  63.   
  64.        /* Routines to search for the minimal item of a tree */
  65. extern void     *avldelmin  _P( AVL_TREE );
  66. extern void     *avlfindmin _P( AVL_TREE );
  67.   
  68.   
  69.        /* Routines to search for the maximal item of a tree */
  70. extern void     *avldelmax  _P( AVL_TREE );
  71. extern void     *avlfindmax _P( AVL_TREE );
  72.   
  73. #endif /* NEXTERN */
  74.  
  75. #undef _P
  76. #endif /* AVL_H */
  77.