📄 glib-balanced-binary-trees.html
字号:
<html xmlns:cf="http://docbook.sourceforge.net/xmlns/chunkfast/1.0"><head><meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"><title>Balanced Binary Trees</title><meta name="generator" content="DocBook XSL Stylesheets V1.69.0"><link rel="start" href="index.html" title="GLib Reference Manual"><link rel="up" href="glib-data-types.html" title="GLib Data Types"><link rel="prev" href="glib-Byte-Arrays.html" title="Byte Arrays"><link rel="next" href="glib-N-ary-Trees.html" title="N-ary Trees"><meta name="generator" content="GTK-Doc V1.4 (XML mode)"><link rel="stylesheet" href="style.css" type="text/css"><link rel="chapter" href="glib.html" title="GLib Overview"><link rel="chapter" href="glib-fundamentals.html" title="GLib Fundamentals"><link rel="chapter" href="glib-core.html" title="GLib Core Application Support"><link rel="chapter" href="glib-utilities.html" title="GLib Utilities"><link rel="chapter" href="glib-data-types.html" title="GLib Data Types"><link rel="chapter" href="tools.html" title="GLib Tools"><link rel="index" href="ix01.html" title="Index"><link rel="index" href="ix02.html" title="Index of deprecated symbols"><link rel="index" href="ix03.html" title="Index of new symbols in 2.2"><link rel="index" href="ix04.html" title="Index of new symbols in 2.4"><link rel="index" href="ix05.html" title="Index of new symbols in 2.6"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><table class="navigation" width="100%" summary="Navigation header" cellpadding="2" cellspacing="2"><tr valign="middle"><td><a accesskey="p" href="glib-Byte-Arrays.html"><img src="left.png" width="24" height="24" border="0" alt="Prev"></a></td><td><a accesskey="u" href="glib-data-types.html"><img src="up.png" width="24" height="24" border="0" alt="Up"></a></td><td><a accesskey="h" href="index.html"><img src="home.png" width="24" height="24" border="0" alt="Home"></a></td><th width="100%" align="center">GLib Reference Manual</th><td><a accesskey="n" href="glib-N-ary-Trees.html"><img src="right.png" width="24" height="24" border="0" alt="Next"></a></td></tr></table><div class="refentry" lang="en"><a name="glib-Balanced-Binary-Trees"></a><div class="titlepage"></div><div class="refnamediv"><table width="100%"><tr><td valign="top"><h2><span class="refentrytitle">Balanced Binary Trees</span></h2><p>Balanced Binary Trees — a sorted collection of key/value pairs optimized for searchingand traversing in order.</p></td><td valign="top" align="right"></td></tr></table></div><div class="refsynopsisdiv"><h2>Synopsis</h2><pre class="synopsis">#include <glib.h> <a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a>;<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a>* <a href="glib-Balanced-Binary-Trees.html#g-tree-new">g_tree_new</a> (<a href="glib-Doubly-Linked-Lists.html#GCompareFunc">GCompareFunc</a> key_compare_func);<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a>* <a href="glib-Balanced-Binary-Trees.html#g-tree-new-with-data">g_tree_new_with_data</a> (<a href="glib-Doubly-Linked-Lists.html#GCompareDataFunc">GCompareDataFunc</a> key_compare_func, <a href="glib-Basic-Types.html#gpointer">gpointer</a> key_compare_data);<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a>* <a href="glib-Balanced-Binary-Trees.html#g-tree-new-full">g_tree_new_full</a> (<a href="glib-Doubly-Linked-Lists.html#GCompareDataFunc">GCompareDataFunc</a> key_compare_func, <a href="glib-Basic-Types.html#gpointer">gpointer</a> key_compare_data, <a href="glib-Datasets.html#GDestroyNotify">GDestroyNotify</a> key_destroy_func, <a href="glib-Datasets.html#GDestroyNotify">GDestroyNotify</a> value_destroy_func);void <a href="glib-Balanced-Binary-Trees.html#g-tree-insert">g_tree_insert</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree, <a href="glib-Basic-Types.html#gpointer">gpointer</a> key, <a href="glib-Basic-Types.html#gpointer">gpointer</a> value);void <a href="glib-Balanced-Binary-Trees.html#g-tree-replace">g_tree_replace</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree, <a href="glib-Basic-Types.html#gpointer">gpointer</a> key, <a href="glib-Basic-Types.html#gpointer">gpointer</a> value);<a href="glib-Basic-Types.html#gint">gint</a> <a href="glib-Balanced-Binary-Trees.html#g-tree-nnodes">g_tree_nnodes</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree);<a href="glib-Basic-Types.html#gint">gint</a> <a href="glib-Balanced-Binary-Trees.html#g-tree-height">g_tree_height</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree);<a href="glib-Basic-Types.html#gpointer">gpointer</a> <a href="glib-Balanced-Binary-Trees.html#g-tree-lookup">g_tree_lookup</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree, <a href="glib-Basic-Types.html#gconstpointer">gconstpointer</a> key);<a href="glib-Basic-Types.html#gboolean">gboolean</a> <a href="glib-Balanced-Binary-Trees.html#g-tree-lookup-extended">g_tree_lookup_extended</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree, <a href="glib-Basic-Types.html#gconstpointer">gconstpointer</a> lookup_key, <a href="glib-Basic-Types.html#gpointer">gpointer</a> *orig_key, <a href="glib-Basic-Types.html#gpointer">gpointer</a> *value);void <a href="glib-Balanced-Binary-Trees.html#g-tree-foreach">g_tree_foreach</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree, <a href="glib-Balanced-Binary-Trees.html#GTraverseFunc">GTraverseFunc</a> func, <a href="glib-Basic-Types.html#gpointer">gpointer</a> user_data);void <a href="glib-Balanced-Binary-Trees.html#g-tree-traverse">g_tree_traverse</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree, <a href="glib-Balanced-Binary-Trees.html#GTraverseFunc">GTraverseFunc</a> traverse_func, <a href="glib-Balanced-Binary-Trees.html#GTraverseType">GTraverseType</a> traverse_type, <a href="glib-Basic-Types.html#gpointer">gpointer</a> user_data);<a href="glib-Basic-Types.html#gboolean">gboolean</a> (<a href="glib-Balanced-Binary-Trees.html#GTraverseFunc">*GTraverseFunc</a>) (<a href="glib-Basic-Types.html#gpointer">gpointer</a> key, <a href="glib-Basic-Types.html#gpointer">gpointer</a> value, <a href="glib-Basic-Types.html#gpointer">gpointer</a> data);enum <a href="glib-Balanced-Binary-Trees.html#GTraverseType">GTraverseType</a>;<a href="glib-Basic-Types.html#gpointer">gpointer</a> <a href="glib-Balanced-Binary-Trees.html#g-tree-search">g_tree_search</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree, <a href="glib-Doubly-Linked-Lists.html#GCompareFunc">GCompareFunc</a> search_func, <a href="glib-Basic-Types.html#gconstpointer">gconstpointer</a> user_data);void <a href="glib-Balanced-Binary-Trees.html#g-tree-remove">g_tree_remove</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree, <a href="glib-Basic-Types.html#gconstpointer">gconstpointer</a> key);void <a href="glib-Balanced-Binary-Trees.html#g-tree-steal">g_tree_steal</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree, <a href="glib-Basic-Types.html#gconstpointer">gconstpointer</a> key);void <a href="glib-Balanced-Binary-Trees.html#g-tree-destroy">g_tree_destroy</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree);</pre></div><div class="refsect1" lang="en"><a name="id3171249"></a><h2>Description</h2><p>The <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> structure and its associated functions provide a sorted collectionof key/value pairs optimized for searching and traversing in order.</p><p>To create a new <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> use <a href="glib-Balanced-Binary-Trees.html#g-tree-new"><code class="function">g_tree_new()</code></a>.</p><p>To insert a key/value pair into a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> use <a href="glib-Balanced-Binary-Trees.html#g-tree-insert"><code class="function">g_tree_insert()</code></a>.</p><p>To lookup the value corresponding to a given key, use <a href="glib-Balanced-Binary-Trees.html#g-tree-lookup"><code class="function">g_tree_lookup()</code></a> and<a href="glib-Balanced-Binary-Trees.html#g-tree-lookup-extended"><code class="function">g_tree_lookup_extended()</code></a>.</p><p>To find out the number of nodes in a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, use <a href="glib-Balanced-Binary-Trees.html#g-tree-nnodes"><code class="function">g_tree_nnodes()</code></a>.To get the height of a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, use <a href="glib-Balanced-Binary-Trees.html#g-tree-height"><code class="function">g_tree_height()</code></a>.</p><p>To traverse a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, calling a function for each node visited in thetraversal, use <a href="glib-Balanced-Binary-Trees.html#g-tree-foreach"><code class="function">g_tree_foreach()</code></a>.</p><p>To remove a key/value pair use <a href="glib-Balanced-Binary-Trees.html#g-tree-remove"><code class="function">g_tree_remove()</code></a>.</p><p>To destroy a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, use <a href="glib-Balanced-Binary-Trees.html#g-tree-destroy"><code class="function">g_tree_destroy()</code></a>.</p></div><div class="refsect1" lang="en"><a name="id3171439"></a><h2>Details</h2><div class="refsect2" lang="en"><a name="id3171445"></a><h3><a name="GTree"></a>GTree</h3><a class="indexterm" name="id3171455"></a><pre class="programlisting">typedef struct _GTree GTree;</pre><p>The <span class="structname">GTree</span> struct is an opaque data structure representing a<a href="glib-Balanced-Binary-Trees.html" title="Balanced Binary Trees">Balanced Binary Tree</a>.It should be accessed only by using the following functions.</p></div><hr><div class="refsect2" lang="en"><a name="id3171484"></a><h3><a name="g-tree-new"></a>g_tree_new ()</h3><a class="indexterm" name="id3171494"></a><pre class="programlisting"><a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a>* g_tree_new (<a href="glib-Doubly-Linked-Lists.html#GCompareFunc">GCompareFunc</a> key_compare_func);</pre><p>Creates a new <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.</p><p></p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><em class="parameter"><code>key_compare_func</code></em> :</span></td><td> the function used to order the nodes in the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>. It should return values similar to the standard <code class="function">strcmp()</code> function - 0 if the two arguments are equal, a negative value if the first argument comes before the second, or a positive value if the first argument comes after the second.</td></tr><tr><td><span class="term"><span class="emphasis"><em>Returns</em></span> :</span></td><td> a new <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3171593"></a><h3><a name="g-tree-new-with-data"></a>g_tree_new_with_data ()</h3><a class="indexterm" name="id3171603"></a><pre class="programlisting"><a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a>* g_tree_new_with_data (<a href="glib-Doubly-Linked-Lists.html#GCompareDataFunc">GCompareDataFunc</a> key_compare_func, <a href="glib-Basic-Types.html#gpointer">gpointer</a> key_compare_data);</pre><p>Creates a new <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> with a comparison function that accepts user data.See <a href="glib-Balanced-Binary-Trees.html#g-tree-new"><code class="function">g_tree_new()</code></a> for more details.</p><p></p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><em class="parameter"><code>key_compare_func</code></em> :</span></td><td> <code class="function">qsort()</code>-style comparison function.</td></tr><tr><td><span class="term"><em class="parameter"><code>key_compare_data</code></em> :</span></td><td> data to pass to comparison function.</td></tr><tr><td><span class="term"><span class="emphasis"><em>Returns</em></span> :</span></td><td> a new <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3171724"></a><h3><a name="g-tree-new-full"></a>g_tree_new_full ()</h3><a class="indexterm" name="id3171735"></a><pre class="programlisting"><a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a>* g_tree_new_full (<a href="glib-Doubly-Linked-Lists.html#GCompareDataFunc">GCompareDataFunc</a> key_compare_func, <a href="glib-Basic-Types.html#gpointer">gpointer</a> key_compare_data, <a href="glib-Datasets.html#GDestroyNotify">GDestroyNotify</a> key_destroy_func, <a href="glib-Datasets.html#GDestroyNotify">GDestroyNotify</a> value_destroy_func);</pre><p>Creates a new <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> like <a href="glib-Balanced-Binary-Trees.html#g-tree-new"><code class="function">g_tree_new()</code></a> and allows to specify functions to free the memory allocated for the key and value that get called when removing the entry from the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.</p><p></p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><em class="parameter"><code>key_compare_func</code></em> :</span></td><td> <code class="function">qsort()</code>-style comparison function.</td></tr><tr><td><span class="term"><em class="parameter"><code>key_compare_data</code></em> :</span></td><td> data to pass to comparison function.</td></tr><tr><td><span class="term"><em class="parameter"><code>key_destroy_func</code></em> :</span></td><td> a function to free the memory allocated for the key used when removing the entry from the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> or <code class="literal">NULL</code> if you don't want to supply such a function.</td></tr><tr><td><span class="term"><em class="parameter"><code>value_destroy_func</code></em> :</span></td><td> a function to free the memory allocated for the value used when removing the entry from the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> or <code class="literal">NULL</code> if you don't want to supply such a function.</td></tr><tr><td><span class="term"><span class="emphasis"><em>Returns</em></span> :</span></td><td> a new <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3171941"></a><h3><a name="g-tree-insert"></a>g_tree_insert ()</h3><a class="indexterm" name="id3171951"></a><pre class="programlisting">void g_tree_insert (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree, <a href="glib-Basic-Types.html#gpointer">gpointer</a> key, <a href="glib-Basic-Types.html#gpointer">gpointer</a> value);</pre><p>Inserts a key/value pair into a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>. If the given key already exists in the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> its corresponding value is set to the new value. If you supplied a value_destroy_func when creating the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, the old value is freed using that function. If you supplied a <em class="parameter"><code>key_destroy_func</code></em> when creating the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, the passed key is freed using that function.</p><p>The tree is automatically 'balanced' as new key/value pairs are added,so that the distance from the root to every leaf is as small as possible.</p><p></p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -