libwww/Library/src/HTBTree.html - annotate

Return to HTBTree.html CVS log
Up to [Public] / libwww / Library / src
Annotation of libwww/Library/src/HTBTree.html, revision 2.8

2.8     ! frystyk     1: <HTML>
        !             2: <HEAD>
        !             3: <TITLE>Balanced Binary Tree</TITLE>
        !             4: </HEAD>
2.7       timbl       5: <BODY>
2.8     ! frystyk     6: 
        !             7: <H1>Balanced Binary Tree</H1>
        !             8: 
        !             9: <PRE>
        !            10: /*
        !            11: **     (c) COPYRIGHT CERN 1994.
        !            12: **     Please first read the full copyright statement in the file COPYRIGH.
        !            13: */
        !            14: </PRE>
        !            15: 
        !            16: Tree creation, traversal and freeing. User-supplied comparison
        !            17: routine.<P>
        !            18: 
        !            19: This module is implemented by <A HREF="HTBTree.c">HTBTree.c</A>, and
        !            20: it is a part of the <A
        !            21: HREF="http://info.cern.ch/hypertext/WWW/Library/User/Guide/Guide.html">
        !            22: Library of Common Code</A>.
        !            23: 
        !            24: <PRE>
        !            25: #ifdef SHORT_NAMES
2.7       timbl      26: #define        HTBTree_new             HTBTNew
                     27: #define        HTBTree_free            HTBTFree
                     28: #define HTBTreeAndObject_free  HTBTAOFr
                     29: #define HTBTree_add            HTBTAdd
                     30: #define        HTBTree_next            HTBTNext
                     31: /* #define     HTBTree_object          HTBTObje already a macro */
                     32: #endif
1.1       timbl      33: 
                     34: 
2.7       timbl      35: </PRE>
                     36: <H2>Data structures</H2>
                     37: <PRE>typedef struct _HTBTree_element {
1.1       timbl      38:     void                       *object;        /* User object */
                     39:     struct _HTBTree_element    *up;
                     40:     struct _HTBTree_element    *left;
                     41:     int                                left_depth;
                     42:     struct _HTBTree_element    *right;
                     43:     int                                right_depth;
                     44: } HTBTElement;
                     45: 
2.6       secret     46: typedef int (*HTComparer) PARAMS((void * a, void * b));
1.1       timbl      47: 
                     48: typedef struct _HTBTree_top {
                     49:     HTComparer                 compare;
                     50:     struct _HTBTree_element    *top;   
                     51: } HTBTree;
                     52: 
                     53: 
2.7       timbl      54: </PRE>
                     55: <H2>Create a binary tree given its discrimination
                     56: routine</H2>
                     57: <PRE>extern HTBTree * HTBTree_new PARAMS((HTComparer comp));
1.1       timbl      58: 
                     59: 
                     60: 
2.7       timbl      61: </PRE>
                     62: <H2>Free storage of the tree but not
                     63: of the objects</H2>
                     64: <PRE>extern void HTBTree_free PARAMS((HTBTree* tree));
2.6       secret     65: 
                     66: 
                     67: 
2.7       timbl      68: </PRE>
                     69: <H2>Free storage of the tree and of the
                     70: objects</H2>
                     71: <PRE>extern void HTBTreeAndObject_free PARAMS((HTBTree* tree));
2.6       secret     72: 
                     73: 
1.1       timbl      74: 
2.7       timbl      75: </PRE>
                     76: <H2>Add an object to a binary tree</H2>
                     77: <PRE>
                     78: extern void HTBTree_add PARAMS((HTBTree* tree, void * object));
1.1       timbl      79: 
                     80: 
2.7       timbl      81: </PRE>
                     82: <H2>Find user object for element</H2>
                     83: <PRE>#define HTBTree_object(element)  ((element)->object)
1.1       timbl      84: 
                     85: 
2.7       timbl      86: </PRE>
                     87: <H2>Find next element in depth-first
                     88: order</H2>
                     89: <H3>On entry,</H3>
                     90: <DL>
                     91: <DT>ele
                     92: <DD>if NULL, start with leftmost element.
                     93: if != 0 give next object to the right.
                     94: <DT>returns
                     95: <DD>Pointer to element ot NULL
                     96: if none left.
                     97: </DL>
1.1       timbl      98: 
2.7       timbl      99: <PRE>extern HTBTElement * HTBTree_next PARAMS((HTBTree* tree, HTBTElement * ele));
1.1       timbl     100: 
2.7       timbl     101: </PRE>end</BODY>
Webmaster