• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1<!-- ##### SECTION Title ##### -->
2Balanced Binary Trees
3
4<!-- ##### SECTION Short_Description ##### -->
5a sorted collection of key/value pairs optimized for searching
6and traversing in order
7
8<!-- ##### SECTION Long_Description ##### -->
9<para>
10The #GTree structure and its associated functions provide a sorted collection
11of key/value pairs optimized for searching and traversing in order.
12</para>
13<para>
14To create a new #GTree use g_tree_new().
15</para>
16<para>
17To insert a key/value pair into a #GTree use g_tree_insert().
18</para>
19<para>
20To lookup the value corresponding to a given key, use g_tree_lookup() and
21g_tree_lookup_extended().
22</para>
23<para>
24To find out the number of nodes in a #GTree, use g_tree_nnodes().
25To get the height of a #GTree, use g_tree_height().
26</para>
27<para>
28To traverse a #GTree, calling a function for each node visited in the
29traversal, use g_tree_foreach().
30</para>
31<para>
32To remove a key/value pair use g_tree_remove().
33</para>
34<para>
35To destroy a #GTree, use g_tree_destroy().
36</para>
37
38<!-- ##### SECTION See_Also ##### -->
39<para>
40
41</para>
42
43<!-- ##### SECTION Stability_Level ##### -->
44
45
46<!-- ##### STRUCT GTree ##### -->
47<para>
48The <structname>GTree</structname> struct is an opaque data structure representing a
49<link linkend="glib-Balanced-Binary-Trees">Balanced Binary Tree</link>.
50It should be accessed only by using the following functions.
51</para>
52
53
54<!-- ##### FUNCTION g_tree_new ##### -->
55<para>
56
57</para>
58
59@key_compare_func:
60@Returns:
61
62
63<!-- ##### FUNCTION g_tree_new_with_data ##### -->
64<para>
65
66</para>
67
68@key_compare_func:
69@key_compare_data:
70@Returns:
71
72
73<!-- ##### FUNCTION g_tree_new_full ##### -->
74<para>
75
76</para>
77
78@key_compare_func:
79@key_compare_data:
80@key_destroy_func:
81@value_destroy_func:
82@Returns:
83
84
85<!-- ##### FUNCTION g_tree_insert ##### -->
86<para>
87
88</para>
89
90@tree:
91@key:
92@value:
93
94
95<!-- ##### FUNCTION g_tree_replace ##### -->
96<para>
97
98</para>
99
100@tree:
101@key:
102@value:
103
104
105<!-- ##### FUNCTION g_tree_nnodes ##### -->
106<para>
107
108</para>
109
110@tree:
111@Returns:
112
113
114<!-- ##### FUNCTION g_tree_height ##### -->
115<para>
116
117</para>
118
119@tree:
120@Returns:
121
122
123<!-- ##### FUNCTION g_tree_lookup ##### -->
124<para>
125
126</para>
127
128@tree:
129@key:
130@Returns:
131
132
133<!-- ##### FUNCTION g_tree_lookup_extended ##### -->
134
135
136@tree:
137@lookup_key:
138@orig_key:
139@value:
140@Returns:
141
142
143<!-- ##### FUNCTION g_tree_foreach ##### -->
144<para>
145
146</para>
147
148@tree:
149@func:
150@user_data:
151
152
153<!-- ##### FUNCTION g_tree_traverse ##### -->
154<para>
155
156</para>
157
158@tree:
159@traverse_func:
160@traverse_type:
161@user_data:
162
163
164<!-- ##### USER_FUNCTION GTraverseFunc ##### -->
165<para>
166Specifies the type of function passed to g_tree_traverse().
167It is passed the key and value of each node, together with
168the @user_data parameter passed to g_tree_traverse().
169If the function returns %TRUE, the traversal is stopped.
170</para>
171
172@key: a key of a #GTree node.
173@value: the value corresponding to the key.
174@data: user data passed to g_tree_traverse().
175@Returns: %TRUE to stop the traversal.
176
177
178<!-- ##### ENUM GTraverseType ##### -->
179<para>
180Specifies the type of traveral performed by g_tree_traverse(),
181g_node_traverse() and g_node_find().
182</para>
183
184@G_IN_ORDER: vists a node's left child first, then the node itself, then its
185  right child. This is the one to use if you want the output sorted according
186  to the compare function.
187@G_PRE_ORDER: visits a node, then its children.
188@G_POST_ORDER: visits the node's children, then the node itself.
189@G_LEVEL_ORDER: is not implemented for
190  <link linkend="glib-Balanced-Binary-Trees">Balanced Binary Trees</link>.
191  For <link linkend="glib-N-ary-Trees">N-ary Trees</link>, it vists the root
192  node first, then its children, then its grandchildren, and so on. Note that
193  this is less efficient than the other orders.
194
195<!-- ##### FUNCTION g_tree_search ##### -->
196<para>
197
198</para>
199
200@tree:
201@search_func:
202@user_data:
203@Returns:
204
205
206<!-- ##### FUNCTION g_tree_remove ##### -->
207<para>
208
209</para>
210
211@tree:
212@key:
213@Returns:
214
215
216<!-- ##### FUNCTION g_tree_steal ##### -->
217<para>
218
219</para>
220
221@tree:
222@key:
223@Returns:
224
225
226<!-- ##### FUNCTION g_tree_destroy ##### -->
227<para>
228
229</para>
230
231@tree:
232
233
234