Glib实例学习（5）平衡二叉树

1：概述
   平衡二叉树：对有序序列的一种优化，可以用来高效的查找和遍历等的一种树形结构。

2：原型

GTree* g_tree_new (GCompareFunc key_compare_func);
GTree* g_tree_new_with_data (GCompareDataFunc key_compare_func,
                                                         gpointer key_compare_data);
GTree* g_tree_new_full (GCompareDataFunc key_compare_func,
                                                         gpointer key_compare_data,
                                                         GDestroyNotify key_destroy_func,
                                                         GDestroyNotify value_destroy_func);
void g_tree_insert (GTree *tree,
                                                         gpointer key,
                                                         gpointer value);
void g_tree_replace (GTree *tree,
                                                         gpointer key,
                                                         gpointer value);
gint g_tree_nnodes (GTree *tree);
gint g_tree_height (GTree *tree);
gpointer g_tree_lookup (GTree *tree,
                                                         gconstpointer key);
gboolean g_tree_lookup_extended (GTree *tree,
                                                         gconstpointer lookup_key,
                                                         gpointer *orig_key,
                                                         gpointer *value);
void g_tree_foreach (GTree *tree,
                                                         GTraverseFunc func,
                                                         gpointer user_data);
gpointer g_tree_search (GTree *tree,
                                                         GCompareFunc search_func,
                                                         gconstpointer user_data);
gboolean g_tree_remove (GTree *tree,
                                                         gconstpointer key);
gboolean g_tree_steal (GTree *tree,
                                                         gconstpointer key);
void g_tree_destroy (GTree *tree);

3：实例

#include <stdio.h>
#include <glib.h>
#include <glib/gprintf.h>

struct map {
    int key;
    char *value;
} m[10] = {
    {0,"zero"},
    {1,"one"},
    {2,"two"},
    {3,"three"},
    {4,"four"},
    {5,"five"},
    {6,"six"},
    {7,"seven"},
    {8,"eight"},
    {9,"nine"},
};
typedef struct map map;

static gint
myCompare(gconstpointer p1, gconstpointer p2)
{
    const char *a = p1;
    const char *b = p2;

    return *a - *b;
}

static gint
mySearch(gconstpointer p1, gconstpointer p2)
{
    return myCompare(p1, p2);
}

static gint
myTraverse(gpointer key, gpointer value, gpointer fmt)
{
    g_printf(fmt, *(gint*)key, (gchar*)value);

    return FALSE;
}

static void
test_avl_tree(void)
{
    GTree *tree;
    gint i;

// GTree* g_tree_new(GCompareFunc key_compare_func);
    tree = g_tree_new(myCompare);

// void g_tree_insert(GTree *tree, gpointer key, gpointer value);
    for (i = 0; i < sizeof(m)/sizeof(m[0]); i++)
        g_tree_insert(tree, &m[i].key, m[i].value);

// void g_tree_foreach(GTree *tree, GTraverseFunc func, gpointer user_data);
    g_printf("Now the tree:\n");
    g_tree_foreach(tree, myTraverse, "Key:\t%d\t\tVaule:\t%s\n");
// gint g_tree_nnodes(GTree *tree);
    g_printf("The tree should have '%d' items now.\t\tResult: %d.\n", 10, g_tree_nnodes(tree));
// gint g_tree_height(GTree *tree);
    g_printf("The height of tree is '%d' now.\n", g_tree_height(tree));

// void g_tree_replace(GTree *tree, gpointer key, gpointer value);
    g_tree_replace(tree, &m[3].key, "3333");
    g_printf("Now the vaule of '%d' should be '3333' now.\n", m[3].key);
    g_tree_foreach(tree, myTraverse, "Key:\t%d\t\tVaule:\t%s\n");

    gchar *tmp = NULL;
// gpointer g_tree_lookup(GTree *tree, gconstpointer key);
    g_printf("Now the vaule of '%d' should be '%s' now[lookup].\n",
            m[3].key,
            (tmp = (gchar *)g_tree_lookup(tree, &m[3].key)) != NULL ? tmp : NULL);

// gboolean g_tree_remove(GTree *tree, gconstpointer key);
    gboolean b = g_tree_remove(tree, &m[3].key);
    g_printf("The key '%d' has %sbeen found and removed now.\n", m[3].key, b ? "" : "NOT");

// gpointer g_tree_search(GTree *tree, GCompareFunc search_func, gconstpointer user_data);
    g_printf("Now the vaule which should be removed of '%d' should be '%s' now[search].\n",
            m[3].key,
            (tmp = (gchar *)g_tree_search(tree, mySearch, &m[3].key)) != NULL ? tmp : NULL);

    g_printf("Now the tree look like:\n");
    g_tree_foreach(tree, myTraverse, "Key:\t%d\t\tVaule:\t%s\n");

// void g_tree_destroy(GTree *tree);
    g_tree_destroy(tree);
}

int
main(void)
{
    printf("BEGIN:\n************************************************************\n");

    test_avl_tree();

    printf("\n************************************************************\nDONE\n");

    return 0;
}

4：结果

BEGIN:
************************************************************
Now the tree:
Key: 0 Vaule: zero
Key: 1 Vaule: one
Key: 2 Vaule: two
Key: 3 Vaule: three
Key: 4 Vaule: four
Key: 5 Vaule: five
Key: 6 Vaule: six
Key: 7 Vaule: seven
Key: 8 Vaule: eight
Key: 9 Vaule: nine
The tree should have '10' items now. Result: 10.
The height of tree is '4' now.
Now the vaule of '3' should be '3333' now.
Key: 0 Vaule: zero
Key: 1 Vaule: one
Key: 2 Vaule: two
Key: 3 Vaule: 3333
Key: 4 Vaule: four
Key: 5 Vaule: five
Key: 6 Vaule: six
Key: 7 Vaule: seven
Key: 8 Vaule: eight
Key: 9 Vaule: nine
Now the vaule of '3' should be '3333' now[lookup].
The key '3' has been found and removed now.
Now the vaule which should be removed of '3' should be '(null)' now[search].
Now the tree look like:
Key: 0 Vaule: zero
Key: 1 Vaule: one
Key: 2 Vaule: two
Key: 4 Vaule: four
Key: 5 Vaule: five
Key: 6 Vaule: six
Key: 7 Vaule: seven
Key: 8 Vaule: eight
Key: 9 Vaule: nine

************************************************************
DONE

5：小结

• 创建： g_tree_new()
• 插入： g_tree_insert()
• 查找： g_tree_lookup() g_tree_search()
• 删除： g_tree_remove()
  
• 属性： g_tree_nnodes() g_tree_height()
• 遍历： g_tree_foreach()
• 销毁： g_tree_destroy()