-.\" Hey Emacs! This file is -*- nroff -*- source.
.\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
.\"
+.\" %%%LICENSE_START(VERBATIM)
.\" Permission is granted to make and distribute verbatim copies of this
.\" manual provided the copyright notice and this permission notice are
.\" preserved on all copies.
.\"
.\" Formatted or processed versions of this manual, if unaccompanied by
.\" the source, must acknowledge the copyright and authors of this work.
+.\" %%%LICENSE_END
.\"
.\"*******************************************************************
.\"
.\" This file was generated with po4a. Translate the source file.
.\"
.\"*******************************************************************
-.TH TSEARCH 3 2008\-09\-23 GNU "Linux Programmer's Manual"
+.TH TSEARCH 3 2012\-08\-03 GNU "Linux Programmer's Manual"
.SH 名前
tsearch, tfind, tdelete, twalk, tdestroy \- 二分木 (binary tree) の操作
.SH 書式
.PP
\fBtdelete\fP() は木構造からアイテムを削除する。 引数は \fBtsearch\fP() と同じである。
.PP
-\fBtwalk\fP() は、二分木を深さ優先 (depth\-first) で、 左から右にたどっていく関数である。 \fIroot\fP
-は起点となるノードへのポインタである。 \fIroot\fP に根以外のノードを指定すると、部分木が対象となる。 \fBtwalk\fP()
-は、ノードを訪れる度に (つまり、内部ノードに対しては 3 回、葉に対しては 1 回) ユーザ関数 \fIaction\fP を呼び出す。
-\fIaction\fP には以下の順に 3 つの引数が与えられる。 最初の引数は訪れたノードへのポインタである。 2
-つ目の引数には、内部ノードの場合は訪問回数に応じて \fBpreorder\fP, \fBpostorder\fP, \fBendorder\fP が、 葉の場合は
-\fBleaf\fP が与えられる。 (これらのシンボルは \fI<search.h>\fP で定義されている。) 3
-つ目の引数はノードの深さで、根の場合は 0 である。
+\fBtwalk\fP() performs depth\-first, left\-to\-right traversal of a binary tree.
+\fIroot\fP points to the starting node for the traversal. If that node is not
+the root, then only part of the tree will be visited. \fBtwalk\fP() calls the
+user function \fIaction\fP each time a node is visited (that is, three times
+for an internal node, and once for a leaf). \fIaction\fP, in turn, takes three
+arguments. The first argument is a pointer to the node being visited. The
+structure of the node is unspecified, but it is possible to cast the pointer
+to a pointer\-to\-pointer\-to\-element in order to access the element stored
+within the node. The application must not modify the structure pointed to
+by this argument. The second argument is an integer which takes one of the
+values \fBpreorder\fP, \fBpostorder\fP, or \fBendorder\fP depending on whether this
+is the first, second, or third visit to the internal node, or the value
+\fBleaf\fP if this is the single visit to a leaf node. (These symbols are
+defined in \fI<search.h>\fP.) The third argument is the depth of the
+node; the root node has depth zero.
.PP
(より一般的には、\fBpreorder\fP, \fBpostorder\fP, \fBendorder\fP は \fBpreorder\fP, \fBinorder\fP,
\fBpostorder\fP として知られている: それぞれ、子要素を辿る前・最初の子要素を辿った後かつ 2 番目の子要素を辿る前・
.SH 注意
\fBtwalk\fP() は根へのポインタを引数にとるが、 ほかの関数は根へのポインタへのポインタである。
.PP
-\fBtwalk\fP() においては、\fBpostorder\fP は 「左の部分木の後で、右の部分木の前」を意味している。 しかし、人によってはこれを
-"inorder" と呼んで、 "postorder" を「両方の部分木の後」とする場合もある。
-.PP
\fBtdelete\fP() は、削除したノードの使用していたメモリを解放するが、 ノードに対応するデータのメモリは、ユーザが解放しなければならない。
.PP
下のプログラム例は、ユーザ関数が "endorder" か "leaf" を引数にして 呼び出されて以降は、 \fBtwalk\fP()
srand(time(NULL));
for (i = 0; i < 12; i++) {
- ptr = (int *) xmalloc(sizeof(int));
+ ptr = xmalloc(sizeof(int));
*ptr = rand() & 0xff;
val = tsearch((void *) ptr, &root, compare);
if (val == NULL)
.SH 関連項目
\fBbsearch\fP(3), \fBhsearch\fP(3), \fBlsearch\fP(3) \fBqsort\fP(3)
.SH この文書について
-この man ページは Linux \fIman\-pages\fP プロジェクトのリリース 3.41 の一部
+この man ページは Linux \fIman\-pages\fP プロジェクトのリリース 3.50 の一部
である。プロジェクトの説明とバグ報告に関する情報は
http://www.kernel.org/doc/man\-pages/ に書かれている。
OSDN Git Service
