4_10_GLib库入门与实践_平衡二叉树

大家好，我是讯享网，很高兴认识大家。

简介

数据结构

平衡二叉树的数据结构GTree是不透明结构体，只能作为整体使用，无法直接引用其内部变量。

typedef struct _GTree GTree;

讯享网

函数列表

讯享网GTree * g_tree_new () GTree * g_tree_ref () void g_tree_unref () GTree * g_tree_new_with_data () GTree * g_tree_new_full () void g_tree_insert () void g_tree_replace () gint g_tree_nnodes () gint g_tree_height () gpointer g_tree_lookup () gboolean g_tree_lookup_extended () void g_tree_foreach () void g_tree_traverse () gpointer g_tree_search () gboolean g_tree_remove () gboolean g_tree_steal () void g_tree_destroy ()

函数功能分类

创建
GTree * g_tree_new ()
GTree * g_tree_new_with_data ()
GTree * g_tree_new_full ()

销毁
void g_tree_destroy ()

插入
void g_tree_insert ()

遍历
void g_tree_foreach ()

测高
gint g_tree_height ()

测节点个数
gint g_tree_nnodes ()

删除
gboolean g_tree_remove ()

移出
gboolean g_tree_steal ()

替代
void g_tree_replace ()

查找
gpointer g_tree_lookup ()
gboolean g_tree_lookup_extended ()

搜索
gpointer g_tree_search ()

引用和解引用
GTree * g_tree_ref ()
void g_tree_unref ()

函数功能说明及综合演示

基本数据类型键值的创建插入遍历销毁

本例演示三种情况的二叉树节点：

key为int类型，value为int类型
key为int类型，value为char类型
key为char类型，value为char类型

示例代码如下：
源码见glib_examples\glib_btree\glib_btree_basic_basic_type

#include <glib.h> gint _int_cmp(gint a, gint b) { 
    return a - b; } gboolean _foreach_int_int_func (gpointer key, gpointer value, gpointer data) { 
    g_print("key:%d, value:%d user_data:%s \n", GPOINTER_TO_INT(key), GPOINTER_TO_INT(value), (gchar *)data); return 0; } gint gtree_test_int_int_data(void) { 
    GTree *tree = NULL; tree = g_tree_new((GCompareFunc)_int_cmp); if(NULL == tree) { 
    g_print("g_tree_new return NULL \n"); return 0; } g_tree_insert(tree, GINT_TO_POINTER(6), GINT_TO_POINTER(6)); g_tree_insert(tree, GINT_TO_POINTER(8), GINT_TO_POINTER(8)); g_tree_insert(tree, GINT_TO_POINTER(2), GINT_TO_POINTER(2)); g_tree_foreach(tree, _foreach_int_int_func, "int-int"); g_tree_destroy(tree); return 0; } gboolean _foreach_int_char_func (gpointer key, gpointer value, gpointer data) { 
    gchar *val = value; g_print("key:%c, value:%c user_data:%s \n", GPOINTER_TO_INT(key), (char)*val, (gchar *)data); return 0; } gint gtree_test_int_char_data(void) { 
    GTree *tree = NULL; gint i = 0; gchar str[3] = "abc"; tree = g_tree_new((GCompareFunc)_int_cmp); if(NULL == tree) { 
    g_print("g_tree_new return NULL \n"); return 0; } for(i=0; i<3; i++) { 
    g_tree_insert(tree, GINT_TO_POINTER(str[i]), &str[i]); } g_tree_foreach(tree, _foreach_int_char_func, "int-char"); g_tree_destroy(tree); return 0; } gboolean _foreach_char_char_func (gpointer key, gpointer value, gpointer data) { 
    char *k = key; char *v = value; g_print("key:%c, value:%c user_data:%s \n", (char)*k, (char)*v, (gchar *)data); return 0; } gint gtree_test_char_char_data(void) { 
    GTree *tree = NULL; gint i = 0; gchar str[3] = "abc"; tree = g_tree_new((GCompareFunc)strcmp); if(NULL == tree) { 
    g_print("g_tree_new return NULL \n"); return 0; } for(i=0; i<3; i++) { 
    g_tree_insert(tree, &str[i], &str[i]); } g_tree_foreach(tree, _foreach_char_char_func, "char-char"); g_tree_destroy(tree); return 0; } gint main(gint argc, gchar **argv) { 
    gtree_test_int_int_data(); gtree_test_int_char_data(); gtree_test_char_char_data(); return 0; }

运行结果：

讯享网[root@centos7_6 glib_btree_basic_basic_type]# ./glib_btree_basic_basic_type key:2, value:2 user_data:int-int key:6, value:6 user_data:int-int key:8, value:8 user_data:int-int key:a, value:a user_data:int-char key:b, value:b user_data:int-char key:c, value:c user_data:int-char key:a, value:a user_data:char-char key:b, value:b user_data:char-char key:c, value:c user_data:char-char

字符串类型键值的创建插入遍历销毁

本示例演示的是key和value都是字符串类型的情形。
示例代码如下：
源码见glib_examples\glib_btree\glib_btree_basic_string_type

#include <glib.h> gboolean _foreach_str_str_func (gpointer key, gpointer value, gpointer data) { 
    g_print("key:%s, value:%s user_data:%s \n", (char *)key, (char *)value, (gchar *)data); return 0; } void _str_str_key_destroy_func(gpointer data) { 
    if(NULL != data) { 
    g_free(data); } } void _str_str_value_destroy_func(gpointer data) { 
    if(NULL != data) { 
    g_free(data); } } gint gtree_test_str_str_data(void) { 
    GTree *tree = NULL; gint i = 0; tree = g_tree_new_full((GCompareDataFunc)strcmp,NULL,_str_str_key_destroy_func,_str_str_value_destroy_func); if(NULL == tree) { 
    g_print("g_tree_new return NULL \n"); return 0; } for(i=0; i<3; i++) { 
    g_tree_insert(tree, (gpointer)g_strdup_printf("key-%d", i), (gpointer)g_strdup_printf("value-%d", i)); } g_tree_foreach(tree, _foreach_str_str_func, "str-str"); g_tree_destroy(tree); return 0; } gint main(gint argc, gchar **argv) { 
    gtree_test_str_str_data(); return 0; }

运行结果：

讯享网[root@centos7_6 glib_btree_basic_string_type]# ./glib_btree_basic_string_type key:key-0, value:value-0 user_data:str-str key:key-1, value:value-1 user_data:str-str key:key-2, value:value-2 user_data:str-str

结构体类型键值的创建插入遍历销毁

本示例演示key为字符串，value为自定义结构体类型的情形。
示例代码如下：
源码见glib_examples\glib_btree\glib_btree_basic_struct_type

#include <glib.h> typedef struct my_data_tag { 
    int id; char *name; }my_data_t; gboolean _foreach_str_struct_func (gpointer key, gpointer value, gpointer data) { 
    g_print("key:%s, id:%d, value:%s user_data:%s \n", \ (char *)key, ((my_data_t *)value)->id, ((my_data_t *)value)->name, (gchar *)data); return 0; } void _str_struct_key_destroy_func(gpointer data) { 
    if(NULL != data) { 
    g_free(data); } } void _str_struct_value_destroy_func(gpointer data) { 
    my_data_t *my_data = data; if(NULL != my_data) { 
    if(NULL != my_data->name) { 
    g_free(my_data->name); } g_free(my_data); } } gint gtree_test_str_struct_data(void) { 
    GTree *tree = NULL; my_data_t *my_data[3]; gint i = 0; tree = g_tree_new_full((GCompareDataFunc)strcmp,NULL,_str_struct_key_destroy_func,_str_struct_value_destroy_func); if(NULL == tree) { 
    g_print("g_tree_new return NULL \n"); return 0; } for(i=0; i<3; i++) { 
    my_data[i] = g_new0(my_data_t,1); my_data[i]->id = i*10; my_data[i]->name = g_strdup_printf("name-%d", i*100); g_tree_insert(tree, (gpointer)g_strdup_printf("key-%d", i), (gpointer)my_data[i]); } g_tree_foreach(tree, _foreach_str_struct_func, "str-struct"); g_tree_destroy(tree); return 0; } gint main(gint argc, gchar **argv) { 
    gtree_test_str_struct_data(); return 0; }

运行结果：

讯享网[root@centos7_6 glib_btree_basic_struct_type]# ./glib_btree_basic_struct_type key:key-0, id:0, value:name-0 user_data:str-struct key:key-1, id:10, value:name-100 user_data:str-struct key:key-2, id:20, value:name-200 user_data:str-struct

节点个数与高度

获取平衡二叉树节点个数g_tree_height与树高度g_tree_nnodes。

示例代码如下：
源码见glib_examples\glib_btree\glib_btree_height_nnodes

#include <glib.h> gboolean _traverse_str_str_func (gpointer key, gpointer value, gpointer data) { 
    g_print("key:%s, value:%s user_data:%s \n", (char *)key, (char *)value, (gchar *)data); return 0; } void _str_str_key_destroy_func(gpointer data) { 
    if(NULL != data) { 
    g_free(data); } } void _str_str_value_destroy_func(gpointer data) { 
    if(NULL != data) { 
    g_free(data); } } gint gtree_test_str_str_data(void) { 
    GTree *tree = NULL; gint i = 0; tree = g_tree_new_full((GCompareDataFunc)strcmp,NULL,_str_str_key_destroy_func,_str_str_value_destroy_func); if(NULL == tree) { 
    g_print("g_tree_new return NULL \n"); return 0; } for(i=0; i<30; i++) { 
    g_tree_insert(tree, (gpointer)g_strdup_printf("key-%d", i), (gpointer)g_strdup_printf("value-%d", i)); } g_tree_foreach(tree, _traverse_str_str_func, "str-str"); g_print("nnodes:%d, height:%d \n", g_tree_nnodes(tree), g_tree_height(tree)); g_tree_destroy(tree); return 0; } gint main(gint argc, gchar **argv) { 
    gtree_test_str_str_data(); return 0; }

运行结果：

讯享网

讯享网[root@centos7_6 glib_btree_height_nnodes]# ./glib_btree_height_nnodes key:key-0, value:value-0 user_data:str-str key:key-1, value:value-1 user_data:str-str key:key-10, value:value-10 user_data:str-str key:key-11, value:value-11 user_data:str-str key:key-12, value:value-12 user_data:str-str key:key-13, value:value-13 user_data:str-str key:key-14, value:value-14 user_data:str-str key:key-15, value:value-15 user_data:str-str key:key-16, value:value-16 user_data:str-str key:key-17, value:value-17 user_data:str-str key:key-18, value:value-18 user_data:str-str key:key-19, value:value-19 user_data:str-str key:key-2, value:value-2 user_data:str-str key:key-20, value:value-20 user_data:str-str key:key-21, value:value-21 user_data:str-str key:key-22, value:value-22 user_data:str-str key:key-23, value:value-23 user_data:str-str key:key-24, value:value-24 user_data:str-str key:key-25, value:value-25 user_data:str-str key:key-26, value:value-26 user_data:str-str key:key-27, value:value-27 user_data:str-str key:key-28, value:value-28 user_data:str-str key:key-29, value:value-29 user_data:str-str key:key-3, value:value-3 user_data:str-str key:key-4, value:value-4 user_data:str-str key:key-5, value:value-5 user_data:str-str key:key-6, value:value-6 user_data:str-str key:key-7, value:value-7 user_data:str-str key:key-8, value:value-8 user_data:str-str key:key-9, value:value-9 user_data:str-str nnodes:30, height:6

删除

将一个节点从树删除
示例代码如下：
源码见glib_examples\glib_btree\glib_btree_remove

#include <glib.h> gboolean _traverse_str_str_func (gpointer key, gpointer value, gpointer data) { 
    g_print("key:%s, value:%s user_data:%s \n", (char *)key, (char *)value, (gchar *)data); return 0; } void _str_str_key_destroy_func(gpointer data) { 
    if(NULL != data) { 
    g_free(data); } } void _str_str_value_destroy_func(gpointer data) { 
    if(NULL != data) { 
    g_free(data); } } gint gtree_test_str_str_data(void) { 
    GTree *tree = NULL; gint i = 0; tree = g_tree_new_full((GCompareDataFunc)strcmp,NULL,_str_str_key_destroy_func,_str_str_value_destroy_func); if(NULL == tree) { 
    g_print("g_tree_new return NULL \n"); return 0; } for(i=0; i<3; i++) { 
    g_tree_insert(tree, (gpointer)g_strdup_printf("key-%d", i), (gpointer)g_strdup_printf("value-%d", i)); } g_tree_foreach(tree, _traverse_str_str_func, "str-str"); g_tree_remove(tree, (gconstpointer)"key-1"); g_tree_foreach(tree, _traverse_str_str_func, "str-str-after-remove"); g_tree_destroy(tree); return 0; } gint main(gint argc, gchar **argv) { 
    gtree_test_str_str_data(); return 0; }

运行结果：

讯享网[root@centos7_6 glib_btree_remove]# ./glib_btree_remove key:key-0, value:value-0 user_data:str-str key:key-1, value:value-1 user_data:str-str key:key-2, value:value-2 user_data:str-str key:key-0, value:value-0 user_data:str-str-after-remove key:key-2, value:value-2 user_data:str-str-after-remove

移出

将一个节点从树移出，与删除不同的是，移出的节点，不会调用释放函数，悄无声息，因此，这个移出函数起名steal，有悄悄地移动之意。
示例代码如下：
源码见glib_examples\glib_btree\glib_btree_steal

#include <glib.h> #define BTREE_LEN 3 gboolean _traverse_str_str_func (gpointer key, gpointer value, gpointer data) { 
    g_print("key:%s, value:%s user_data:%s \n", (char *)key, (char *)value, (gchar *)data); return 0; } void _str_str_key_destroy_func(gpointer data) { 
    if(NULL != data) { 
    g_free(data); } } void _str_str_value_destroy_func(gpointer data) { 
    if(NULL != data) { 
    g_free(data); } } gint gtree_test_str_str_data(void) { 
    GTree *tree = NULL; gchar *key[BTREE_LEN] = { 
   NULL}; gchar *val[BTREE_LEN] = { 
   NULL}; gint i = 0; tree = g_tree_new_full((GCompareDataFunc)strcmp,NULL,_str_str_key_destroy_func,_str_str_value_destroy_func); if(NULL == tree) { 
    g_print("g_tree_new return NULL \n"); return 0; } for(i=0; i<BTREE_LEN; i++) { 
    key[i] = g_strdup_printf("key-%d", i); val[i] = g_strdup_printf("value-%d", i); g_tree_insert(tree, (gpointer)key[i], (gpointer)val[i]); } g_tree_foreach(tree, _traverse_str_str_func, "str-str"); g_tree_steal(tree, (gconstpointer)"key-1"); g_tree_foreach(tree, _traverse_str_str_func, "str-str-after-steal"); g_print("key[1]:%s, val[1]:%s \n", key[1], val[1]); g_free(key[1]); g_free(val[1]); g_tree_destroy(tree); return 0; } gint main(gint argc, gchar **argv) { 
    gtree_test_str_str_data(); return 0; }

运行结果：

讯享网[root@centos7_6 glib_btree_steal]# ./glib_btree_steal key:key-0, value:value-0 user_data:str-str key:key-1, value:value-1 user_data:str-str key:key-2, value:value-2 user_data:str-str key:key-0, value:value-0 user_data:str-str-after-steal key:key-2, value:value-2 user_data:str-str-after-steal key[1]:key-1, val[1]:value-1

移出的节点若不再使用，一定要注意释放内存，避免内存泄露。
下面示例演示先在二叉树中找到一个节点，然后将节点移出，再释放的流程。涉及到的函数为g_tree_lookup_extended和g_tree_steal。
示例代码如下：
源码见glib_examples\glib_btree\glib_btree_steal2

#include <glib.h> gboolean _traverse_str_str_func (gpointer key, gpointer value, gpointer data) { 
    g_print("key:%s, value:%s user_data:%s \n", (char *)key, (char *)value, (gchar *)data); return 0; } void _str_str_key_destroy_func(gpointer data) { 
    if(NULL != data) { 
    g_free(data); } } void _str_str_value_destroy_func(gpointer data) { 
    if(NULL != data) { 
    g_free(data); } } gint gtree_test_str_str_data(void) { 
    GTree *tree = NULL; gchar *ori_key = NULL, *value = NULL; gboolean ret = FALSE; gint i = 0; tree = g_tree_new_full((GCompareDataFunc)strcmp,NULL,_str_str_key_destroy_func,_str_str_value_destroy_func); if(NULL == tree) { 
    g_print("g_tree_new return NULL \n"); return 0; } for(i=0; i<3; i++) { 
    g_tree_insert(tree, (gpointer)g_strdup_printf("key-%d", i), (gpointer)g_strdup_printf("value-%d", i)); } g_tree_foreach(tree, _traverse_str_str_func, "str-str"); ret = g_tree_lookup_extended(tree, (gconstpointer)"key-1", (gpointer *)&ori_key, (gpointer *)&value); if(ret) { 
    g_tree_steal(tree, (gconstpointer)"key-1"); g_print("ori_key:%s, value:%s \n", ori_key, value); g_free(ori_key); g_free(value); } g_tree_foreach(tree, _traverse_str_str_func, "str-str-after-steal-and-free"); g_tree_destroy(tree); return 0; } gint main(gint argc, gchar **argv) { 
    gtree_test_str_str_data(); return 0; }

运行结果：

讯享网[root@centos7_6 glib_btree_steal2]# ./glib_btree_steal2 key:key-0, value:value-0 user_data:str-str key:key-1, value:value-1 user_data:str-str key:key-2, value:value-2 user_data:str-str ori_key:key-1, value:value-1 key:key-0, value:value-0 user_data:str-str-after-steal-and-free key:key-2, value:value-2 user_data:str-str-after-steal-and-free

查找

根据给定key从二叉树中找到元素对应的值。

// 给定key查找该key是否在二叉树中，如果在，则返回其对应的value gpointer g_tree_lookup (GTree *tree, gconstpointer key); // 给定key，查找该key是否在二叉树中存在，如果存在，返回key和value gboolean g_tree_lookup_extended (GTree *tree, gconstpointer lookup_key, gpointer *orig_key, gpointer *value);

示例代码如下：
源码见glib_examples\glib_btree\glib_btree_lookup

讯享网#include <glib.h> gboolean _traverse_str_str_func (gpointer key, gpointer value, gpointer data) { 
    g_print("key:%s, value:%s user_data:%s \n", (char *)key, (char *)value, (gchar *)data); return 0; } void _str_str_key_destroy_func(gpointer data) { 
    if(NULL != data) { 
    g_free(data); } } void _str_str_value_destroy_func(gpointer data) { 
    if(NULL != data) { 
    g_free(data); } } gint gtree_test_str_str_data(void) { 
    GTree *tree = NULL; gchar *val1 = NULL, *val2 = NULL; gchar *ori_key = NULL, *val3 = NULL; gboolean ret = FALSE; gint i = 0; tree = g_tree_new_full((GCompareDataFunc)strcmp,NULL,_str_str_key_destroy_func,_str_str_value_destroy_func); if(NULL == tree) { 
    g_print("g_tree_new return NULL \n"); return 0; } for(i=0; i<3; i++) { 
    g_tree_insert(tree, (gpointer)g_strdup_printf("key-%d", i), (gpointer)g_strdup_printf("value-%d", i)); } g_tree_foreach(tree, _traverse_str_str_func, "str-str"); val1 = (gchar *)g_tree_lookup(tree, (gchar *)"key-1"); if(NULL != val1) { 
    g_print("value of key-1 is %s \n", val1); } else { 
    g_print("can not find key-1 \n"); } val2 = (gchar *)g_tree_lookup(tree, (gchar *)"key-9"); if(NULL != val2) { 
    g_print("value of key-9 is %s \n", val1); } else { 
    g_print("can not find key-9 \n"); } g_tree_foreach(tree, _traverse_str_str_func, "str-str-after-lookup"); ret = g_tree_lookup_extended(tree, (gchar *)"key-1", (gpointer *)&ori_key, (gpointer *)&val3); if(ret) { 
    g_print("found! ori_key:%s, value:%s \n", ori_key, val3); } g_tree_foreach(tree, _traverse_str_str_func, "str-str-after-lookup_extended"); g_tree_destroy(tree); return 0; } gint main(gint argc, gchar **argv) { 
    gtree_test_str_str_data(); return 0; }

运行结果：

[root@centos7_6 glib_btree_lookup]# ./glib_btree_lookup key:key-0, value:value-0 user_data:str-str key:key-1, value:value-1 user_data:str-str key:key-2, value:value-2 user_data:str-str value of key-1 is value-1 can not find key-9 key:key-0, value:value-0 user_data:str-str-after-lookup key:key-1, value:value-1 user_data:str-str-after-lookup key:key-2, value:value-2 user_data:str-str-after-lookup found! ori_key:key-1, value:value-1 key:key-0, value:value-0 user_data:str-str-after-lookup_extended key:key-1, value:value-1 user_data:str-str-after-lookup_extended key:key-2, value:value-2 user_data:str-str-after-lookup_extended

搜索(已勘误)

(无法得到正确结果，待勘误！！！已勘误，原因见下述专题)
(无法得到正确结果，待勘误！！！已勘误，原因见下述专题)
(无法得到正确结果，待勘误！！！已勘误，原因见下述专题)
调用者自己提供要搜索的目标key及搜索对比函数，如果不能找到，则返回NULL，如果可以找到，则返回该key对应的value。

讯享网gpointer g_tree_search (GTree *tree, GCompareFunc search_func, gconstpointer user_data);

示例代码如下：
源码见glib_examples\glib_btree\glib_btree_search

#include <glib.h> gboolean _traverse_str_str_func (gpointer key, gpointer value, gpointer data) { 
    g_print("key:%s, value:%s user_data:%s \n", (char *)key, (char *)value, (gchar *)data); return 0; } void _str_str_key_destroy_func(gpointer data) { 
    if(NULL != data) { 
    g_free(data); } } void _str_str_value_destroy_func(gpointer data) { 
    if(NULL != data) { 
    g_free(data); } } gint _str_cmp(gchar *a, gchar *b) { 
    g_print("a:%s b:%s\n", a, b); return strcmp(a,b); } static gint my_compare (gconstpointer a, gconstpointer b) { 
    const char *cha = a; const char *chb = b; g_print("cha:%s chb:%s \n", cha, chb); return strcmp(cha, chb); // 修改为return strcmp(chb, cha);可得到正确结果，原因见本章专题一节 } gint gtree_test_str_str_data(void) { 
    GTree *tree = NULL; gchar *value = NULL; gint i = 0; tree = g_tree_new_full((GCompareDataFunc)strcmp,NULL,_str_str_key_destroy_func,_str_str_value_destroy_func); if(NULL == tree) { 
    g_print("g_tree_new return NULL \n"); return 0; } for(i=0; i<5; i++) { 
    g_tree_insert(tree, (gpointer)g_strdup_printf("key-%d", i*10), (gpointer)g_strdup_printf("value-%d", i)); } g_tree_foreach(tree, _traverse_str_str_func, "str-str"); value = (gchar *)g_tree_search(tree,(GCompareFunc)my_compare,(gconstpointer)"key-30"); if(NULL != value) { 
    g_print("key: key-30, value:%s \n", value); } else { 
    g_print("can not found key in tree \n"); } g_tree_destroy(tree); return 0; } gint main(gint argc, gchar **argv) { 
    gtree_test_str_str_data(); return 0; }

运行结果：

讯享网[root@centos7_6 glib_btree_search]# ./glib_btree_search key:key-0, value:value-0 user_data:str-str key:key-10, value:value-1 user_data:str-str key:key-20, value:value-2 user_data:str-str key:key-30, value:value-3 user_data:str-str key:key-40, value:value-4 user_data:str-str cha:key-10 chb:key-30 cha:key-0 chb:key-30 can not found key in tree

结果显示无法搜索到，本程序有问题，待解决（已解决，原因见下述专题）！！！

专题

二叉树的搜索

在上面的章节中，有一个例子演示了二叉树的搜索。最开始这个例子是不成功的，后经网友提示，找到了原因，问题出在了自定义搜索函数上。

这个搜索函数，和其他数据结构（如链表、队列、散列）的搜索函数有什么不一样吗？
在之前介绍的自定义搜索函数中，如果a比b大，返回的就是正值，如果a比b小，返回的就是负值。
而二叉树的自定义搜索函数，如果a比b大，则需要返回负值，如果a比b小，则需要返回正值。
返回值正好相反。

如果仅从对库的使用角度上看，只需要找到gtree的自测代码，比葫芦画瓢自己写一个即可。测试代码为glib/tests/tree.c，这个文件是针对二叉树数据结构提供的一系列函数的测试代码，其中my_search函数就是自定义搜索函数。

static gint my_search (gconstpointer a, gconstpointer b) { 
    return my_compare (b, a); // 注意参数顺序 }

如果想进一步了解其中的原因，可以查看g_tree_search的函数说明。

The @search_func is called with a pointer to the key of a key/value pair in the tree, and the passed in @user_data.
If @search_func returns 0 for a key/value pair, then the corresponding value is returned as the result of g_tree_search().
If @search_func returns -1, searching will proceed among the key/value pairs that have a smaller key;
if @search_func returns 1, searching will proceed among the key/value pairs that have a larger key.
翻译：
使用指向树中键/值对的键的指针和传入的@user_data来调用@search_func。
如果@search_func为键/值对返回0，那么相应的值将作为g_tree_search()的结果返回。
如果@search_func返回-1，则将在具有较小关键字的关键字/值对之间进行搜索；
如果@search_func返回1，则将在具有较大关键字的关键字/值对之间进行搜索。

讯享网static gpointer g_tree_node_search (GTreeNode *node, GCompareFunc search_func, gconstpointer data) { 
    gint dir; if (!node) return NULL; while (1) { 
    dir = (* search_func) (node->key, data); if (dir == 0) // 自定义搜索函数返回0，说明要查找的数据data和节点的键相等，返回节点的值。说明已找到。 return node->value; else if (dir < 0) // 自定义搜索函数返回小于0，则继续查找左侧子树。 { 
    if (!node->left_child) return NULL; node = node->left; } else //自定义搜索函数返回大于0，则继续查找右侧子树。 { 
    if (!node->right_child) return NULL; node = node->right; } } }

当给定的节点小于树中节点值时，此时应该继续搜索左侧子树，因此需要返回-1，如果此时返回了1，则会在右侧子树搜索，右侧子树的所有节点值都大于给定节点，将搜索不到结果。

这取决于平衡二叉树的特点，平衡二叉树又叫平衡二叉搜索树，是一种特殊的二叉搜索树。搜索树的特点是左节点小于根节点而右节点大于根节点（不考虑子节点为空），平衡二叉树不但有上述特点，还有独有特点，即左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树（不考虑空树）。

那么如何更直观地证明GLib的二叉树是一种平衡二叉树呢？
可以使用g_tree_traverse这个在2.56中已废弃的函数。g_tree_traverse提供了三种对二叉树进行遍历的方法：
G_PRE_ORDER：先根遍历，先序遍历，前序遍历
G_IN_ORDER：中根遍历，中序遍历
G_POST_ORDER：后根遍历，后续遍历
将12345这五个数通过g_tree_insert插入二叉树，再进行遍历，得到结果如下：
先根遍历：2-1-4-3-5
中根遍历：1-2-3-4-5
后根遍历：1-3-5-4-2

 2 / \ 1 4 / \ 3 5

根据上述遍历结果画图可以发现其符合平衡二叉搜索树的特点。

4_10_GLib库入门与实践_平衡二叉树

简介

数据结构

函数列表

函数功能分类

函数功能说明及综合演示

基本数据类型键值的创建插入遍历销毁

字符串类型键值的创建插入遍历销毁

结构体类型键值的创建插入遍历销毁

节点个数与高度

删除

移出

查找

搜索(已勘误)

专题

二叉树的搜索

相关推荐