gdsl_bstree.3

一个通用的C语言实现的数据结构

.TH "Binary search tree manipulation module" 3 "22 Jun 2006" "Version 1.4" "gdsl" \" -*- nroff -*-
.ad l
.nh
.SH NAME
Binary search tree manipulation module \- 
.PP
.SS "Typedefs"

.in +1c
.ti -1c
.RI "typedef gdsl_bstree * \fBgdsl_bstree_t\fP"
.br
.RI "\fIGDSL binary search tree type. \fP"
.in -1c
.SS "Functions"

.in +1c
.ti -1c
.RI "\fBgdsl_bstree_t\fP \fBgdsl_bstree_alloc\fP (const char *NAME, \fBgdsl_alloc_func_t\fP ALLOC_F, \fBgdsl_free_func_t\fP FREE_F, \fBgdsl_compare_func_t\fP COMP_F)"
.br
.RI "\fICreate a new binary search tree. \fP"
.ti -1c
.RI "void \fBgdsl_bstree_free\fP (\fBgdsl_bstree_t\fP T)"
.br
.RI "\fIDestroy a binary search tree. \fP"
.ti -1c
.RI "void \fBgdsl_bstree_flush\fP (\fBgdsl_bstree_t\fP T)"
.br
.RI "\fIFlush a binary search tree. \fP"
.ti -1c
.RI "const char * \fBgdsl_bstree_get_name\fP (const \fBgdsl_bstree_t\fP T)"
.br
.RI "\fIGet the name of a binary search tree. \fP"
.ti -1c
.RI "\fBbool\fP \fBgdsl_bstree_is_empty\fP (const \fBgdsl_bstree_t\fP T)"
.br
.RI "\fICheck if a binary search tree is empty. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_bstree_get_root\fP (const \fBgdsl_bstree_t\fP T)"
.br
.RI "\fIGet the root of a binary search tree. \fP"
.ti -1c
.RI "\fBulong\fP \fBgdsl_bstree_get_size\fP (const \fBgdsl_bstree_t\fP T)"
.br
.RI "\fIGet the size of a binary search tree. \fP"
.ti -1c
.RI "\fBulong\fP \fBgdsl_bstree_get_height\fP (const \fBgdsl_bstree_t\fP T)"
.br
.RI "\fIGet the height of a binary search tree. \fP"
.ti -1c
.RI "\fBgdsl_bstree_t\fP \fBgdsl_bstree_set_name\fP (\fBgdsl_bstree_t\fP T, const char *NEW_NAME)"
.br
.RI "\fISet the name of a binary search tree. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_bstree_insert\fP (\fBgdsl_bstree_t\fP T, void *VALUE, int *RESULT)"
.br
.RI "\fIInsert an element into a binary search tree if it's not found or return it. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_bstree_remove\fP (\fBgdsl_bstree_t\fP T, void *VALUE)"
.br
.RI "\fIRemove an element from a binary search tree. \fP"
.ti -1c
.RI "\fBgdsl_bstree_t\fP \fBgdsl_bstree_delete\fP (\fBgdsl_bstree_t\fP T, void *VALUE)"
.br
.RI "\fIDelete an element from a binary search tree. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_bstree_search\fP (const \fBgdsl_bstree_t\fP T, \fBgdsl_compare_func_t\fP COMP_F, void *VALUE)"
.br
.RI "\fISearch for a particular element into a binary search tree. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_bstree_map_prefix\fP (const \fBgdsl_bstree_t\fP T, \fBgdsl_map_func_t\fP MAP_F, void *USER_DATA)"
.br
.RI "\fIParse a binary search tree in prefixed order. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_bstree_map_infix\fP (const \fBgdsl_bstree_t\fP T, \fBgdsl_map_func_t\fP MAP_F, void *USER_DATA)"
.br
.RI "\fIParse a binary search tree in infixed order. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_bstree_map_postfix\fP (const \fBgdsl_bstree_t\fP T, \fBgdsl_map_func_t\fP MAP_F, void *USER_DATA)"
.br
.RI "\fIParse a binary search tree in postfixed order. \fP"
.ti -1c
.RI "void \fBgdsl_bstree_write\fP (const \fBgdsl_bstree_t\fP T, \fBgdsl_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)"
.br
.RI "\fIWrite the element of each node of a binary search tree to a file. \fP"
.ti -1c
.RI "void \fBgdsl_bstree_write_xml\fP (const \fBgdsl_bstree_t\fP T, \fBgdsl_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)"
.br
.RI "\fIWrite the content of a binary search tree to a file into XML. \fP"
.ti -1c
.RI "void \fBgdsl_bstree_dump\fP (const \fBgdsl_bstree_t\fP T, \fBgdsl_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)"
.br
.RI "\fIDump the internal structure of a binary search tree to a file. \fP"
.in -1c
.SH "Typedef Documentation"
.PP 
.SS "typedef struct gdsl_bstree* \fBgdsl_bstree_t\fP"
.PP
GDSL binary search tree type. 
.PP
This type is voluntary opaque. Variables of this kind could'nt be directly used, but by the functions of this module. 
.PP
Definition at line 53 of file gdsl_bstree.h.
.SH "Function Documentation"
.PP 
.SS "\fBgdsl_bstree_t\fP gdsl_bstree_alloc (const char * NAME, \fBgdsl_alloc_func_t\fP ALLOC_F, \fBgdsl_free_func_t\fP FREE_F, \fBgdsl_compare_func_t\fP COMP_F)"
.PP
Create a new binary search tree. 
.PP
Allocate a new binary search tree data structure which name is set to a copy of NAME. The function pointers ALLOC_F, FREE_F and COMP_F could be used to respectively alloc, free and compares elements in the tree. These pointers could be set to NULL to use the default ones:
.IP "\(bu" 2
the default ALLOC_F simply returns its argument
.IP "\(bu" 2
the default FREE_F does nothing
.IP "\(bu" 2
the default COMP_F always returns 0
.PP
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
nothing 
.RE
.PP
\fBParameters:\fP
.RS 4
\fINAME\fP The name of the new binary tree to create 
.br
\fIALLOC_F\fP Function to alloc element when inserting it in a binary tree 
.br
\fIFREE_F\fP Function to free element when removing it from a binary tree 
.br
\fICOMP_F\fP Function to compare elements into the binary tree 
.RE
.PP
\fBReturns:\fP
.RS 4
the newly allocated binary search tree in case of success. 
.PP
NULL in case of insufficient memory. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_free()\fP 
.PP
\fBgdsl_bstree_flush()\fP 
.PP
\fBgdsl_alloc_func_t\fP 
.PP
\fBgdsl_free_func_t\fP 
.PP
\fBgdsl_compare_func_t\fP 
.RE
.PP

.SS "void gdsl_bstree_free (\fBgdsl_bstree_t\fP T)"
.PP
Destroy a binary search tree. 
.PP
Deallocate all the elements of the binary search tree T by calling T's FREE_F function passed to \fBgdsl_bstree_alloc()\fP. The name of T is deallocated and T is deallocated itself too.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |T| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to deallocate 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_alloc()\fP 
.PP
\fBgdsl_bstree_flush()\fP 
.RE
.PP

.SS "void gdsl_bstree_flush (\fBgdsl_bstree_t\fP T)"
.PP
Flush a binary search tree. 
.PP
Deallocate all the elements of the binary search tree T by calling T's FREE_F function passed to \fBgdsl_rbtree_alloc()\fP. The binary search tree T is not deallocated itself and its name is not modified.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |T| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to flush 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_alloc()\fP 
.PP
\fBgdsl_bstree_free()\fP 
.RE
.PP

.SS "const char* gdsl_bstree_get_name (const \fBgdsl_bstree_t\fP T)"
.PP
Get the name of a binary search tree. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t 
.RE
.PP
\fBPostcondition:\fP
.RS 4
The returned string MUST NOT be freed. 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to get the name from 
.RE
.PP
\fBReturns:\fP
.RS 4
the name of the binary search tree T. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_set_name\fP () 
.RE
.PP

.SS "\fBbool\fP gdsl_bstree_is_empty (const \fBgdsl_bstree_t\fP T)"
.PP
Check if a binary search tree is empty. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to check 
.RE
.PP
\fBReturns:\fP
.RS 4
TRUE if the binary search tree T is empty. 
.PP
FALSE if the binary search tree T is not empty. 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_bstree_get_root (const \fBgdsl_bstree_t\fP T)"
.PP
Get the root of a binary search tree. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to get the root element from 
.RE
.PP
\fBReturns:\fP
.RS 4
the element at the root of the binary search tree T. 
.RE
.PP

.SS "\fBulong\fP gdsl_bstree_get_size (const \fBgdsl_bstree_t\fP T)"
.PP
Get the size of a binary search tree. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to get the size from 
.RE
.PP
\fBReturns:\fP
.RS 4
the size of the binary search tree T (noted |T|). 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_get_height()\fP 
.RE
.PP

.SS "\fBulong\fP gdsl_bstree_get_height (const \fBgdsl_bstree_t\fP T)"
.PP
Get the height of a binary search tree. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( |T| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to compute the height from 
.RE
.PP
\fBReturns:\fP
.RS 4
the height of the binary search tree T (noted h(T)). 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_get_size()\fP 
.RE
.PP

.SS "\fBgdsl_bstree_t\fP gdsl_bstree_set_name (\fBgdsl_bstree_t\fP T, const char * NEW_NAME)"
.PP
Set the name of a binary search tree. 
.PP
Change the previous name of the binary search tree T to a copy of NEW_NAME.
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to change the name 
.br
\fINEW_NAME\fP The new name of T 
.RE
.PP
\fBReturns:\fP
.RS 4
the modified binary search tree in case of success. 
.PP
NULL in case of insufficient memory. 
.RE
.PP
\fBSee also:\fP