Linux程序员手册 第3部分
更新日期： 2020-06-09

名称

tsearch，tfind，tdelete，twalk，tdestroy-管理二进制搜索树

语法

#include <search.h>

typedef enum { preorder, postorder, endorder, leaf } VISIT;

void *tsearch(const void *key, void **rootp,
                int (*compar)(const void *, const void *));

void *tfind(const void *key, void *const *rootp,
                int (*compar)(const void *, const void *));

void *tdelete(const void *key, void **rootp,
                int (*compar)(const void *, const void *));

void twalk(const void *root,
                void (*action)(const void *nodep, VISIT which,
                               int depth));

#define _GNU_SOURCE         /* See feature_test_macros(7) */
#include <search.h>

void twalk_r(const void *root,
                void (*action)(const void *nodep, VISIT which,
                               void *closure),
                void *closure);

void tdestroy(void *root, void (*free_node)(void *nodep));

说明

tsearch()，tfind()，twalk()和tdelete()管理二进制搜索树。它们是从Knuth(6.2.2)算法T推广而来的。树的每个节点中的第一个字段是指向相应数据项的指针。 (调用程序必须存储实际数据。)比较点指向比较例程，该例程需要指向两个项目的指针。它应返回一个负数，零值或正数的整数，具体取决于第一项是否小于，等于或大于第二项。

tsearch()在树中搜索项目。关键点指向要搜索的项目。 rootp指向一个变量，该变量指向树的根。如果树为空，则rootp指向的变量应设置为NULL。如果在树中找到该项目，则tsearch()返回一个指向相应树节点的指针。 (换句话说，tsearch()返回一个指向数据项的指针。)如果找不到该项目，则tsearch()将其添加，并返回一个指向相应树节点的指针。

tfind()类似于tsearch()，不同之处在于如果未找到该项目，则tfind()返回NULL。

tdelete()从树中删除一个项目。其参数与tsearch()相同。

twalk()执行二叉树的深度优先，从左到右遍历。根指向遍历的起始节点。如果该节点不是根节点，则仅访问树的一部分。每次访问节点时，twalk()都会调用用户函数操作(即，内部节点访问3次，叶子访问一次)。反过来，动作需要三个参数。第一个参数是指向要访问的节点的指针。节点的结构未指定，但是可以将指针转换为指向元素的指针，以访问存储在节点内的元素。应用程序不得修改此参数所指向的结构。第二个参数是一个整数，它取值顺序，后序或终止顺序之一，具体取决于这是对内部节点的第一次访问，第二次或第三次访问，或者值叶子(如果这是对叶子节点的单次访问) 。 (这些符号在中定义。)第三个参数是节点的深度。根节点的深度为零。

(更常见的是，预购，后购和终止购货被称为预购，订购和后购：在拜访孩子之前，第一次之后，第二次之前以及拜访孩子之后。因此，对名字postorder的选择相当混乱。 )

twalk_r()与twalk()类似，但是不使用depth参数，而是将闭合参数指针传递给操作回调的每次调用，而不会更改。该指针可用于以线程安全的方式在回调函数之间传递信息，而无需求助于全局变量。

tdestroy()删除根指向的整个树，从而释放tsearch()函数分配的所有资源。对于每个树节点中的数据，将调用函数free_node。指向数据的指针作为函数的参数传递。如果不需要进行此类工作，则free_node必须指向不执行任何操作的函数。

返回值

tsearch()返回指向树中匹配节点或新添加节点的指针，如果没有足够的内存来添加该项，则返回NULL。 tfind()返回指向该节点的指针，如果找不到匹配项，则返回NULL。如果有多个与键匹配的项目，则未指定返回节点的项目。

tdelete()返回指向已删除节点的父节点的指针，如果未找到该项目，则返回NULL。如果删除的节点是根节点，则tdelete()返回一个不能访问的悬空指针。

如果rootp在输入时为NULL，则tsearch()，tfind()和tdelete()也会返回NULL。

版本

从2.30版开始，glibc中提供了twalk_r()。

属性

有关本节中使用的术语的说明，请参见attribute(7)。

遵循规范

POSIX.1-2001，POSIX.1-2008，SVr4。函数tdestroy()和twalk_r()是GNU扩展。

备注

twalk()使用指向根的指针，而其他函数使用指向指向根的变量的指针。

tdelete()释放树中节点所需的内存。用户负责为相应的数据释放内存。

该示例程序取决于以下事实：在使用参数" endorder"或" leaf"调用用户函数后，twalk()不再进一步引用节点。这适用于GNU库实现，但System V文档中没有。

示例

下面的程序将十二个随机数插入二叉树中，其中重复的数字被折叠，然后按顺序打印数字。

#define _GNU_SOURCE     /* Expose declaration of tdestroy() */
#include <search.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

static void *root = NULL;

static void *
xmalloc(unsigned n)
{
    void *p;
    p = malloc(n);
    if (p)
        return p;
    fprintf(stderr, "insufficient memory\n");
    exit(EXIT_FAILURE);
}

static int
compare(const void *pa, const void *pb)
{
    if (*(int *) pa < *(int *) pb)
        return -1;
    if (*(int *) pa > *(int *) pb)
        return 1;
    return 0;
}

static void
action(const void *nodep, VISIT which, int depth)
{
    int *datap;

    switch (which) {
    case preorder:
        break;
    case postorder:
        datap = *(int **) nodep;
        printf("%6d\n", *datap);
        break;
    case endorder:
        break;
    case leaf:
        datap = *(int **) nodep;
        printf("%6d\n", *datap);
        break;
    }
}

int
main(void)
{
    int i, *ptr;
    void *val;

    srand(time(NULL));
    for (i = 0; i < 12; i++) {
        ptr = xmalloc(sizeof(int));
        *ptr = rand() & 0xff;
        val = tsearch((void *) ptr, &root, compare);
        if (val == NULL)
            exit(EXIT_FAILURE);
        else if ((*(int **) val) != ptr)
            free(ptr);
    }
    twalk(root, action);
    tdestroy(root, free);
    exit(EXIT_SUCCESS);
}

另外参见

bsearch(3)，hsearch(3)，lsearch(3)，qsort(3)

出版信息

这个页面是Linux手册页项目5.08版的一部分。有关项目的说明、有关报告错误的信息以及此页面的最新版本，请访问https://www.kernel.org/doc/man-pages/。