\fBtsearch\fP(), \fBtfind\fP(), \fBtwalk\fP(), \fBtdelete\fP() は 二分木を操作する関数である。 これらの関数は
Knuth (6.2.2) Algorithm T に基づいている。 木構造における各ノードの最初のフィールドは、対応するデータ・
アイテムへのポインタである。 (参照先のデータは、呼び出しプログラムで用意する。) \fIcompar\fP は比較ルーチンへのポインタである。
-比較ルーチンは、アイテムへのポインタ 2 つを引数に持つ。 比較ルーチンの返り値は、1 つ目のアイテムが 2 つ目のアイテムよりも
+比較ルーチンは、アイテムへのポインタ 2 つを引き数に持つ。 比較ルーチンの返り値は、1 つ目のアイテムが 2 つ目のアイテムよりも
「小さい、等しい、大きい」によって、 「負、0、正」の整数値でなければならない。
.PP
\fBtsearch\fP() は、木構造からアイテムを検索する関数である。 \fIkey\fP は、検索するアイテムへのポインタである。 \fIrootp\fP
.PP
\fBtfind\fP() は、 \fBtsearch\fP() に似ているが、 アイテムが見つからなかった場合 NULL を返す点が異なる。
.PP
-\fBtdelete\fP() は木構造からアイテムを削除する。 引数は \fBtsearch\fP() と同じである。
+\fBtdelete\fP() は木構造からアイテムを削除する。 引き数は \fBtsearch\fP() と同じである。
.PP
-\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.
+\fBtwalk\fP() は、二分木を深さ優先 (depth\-first) で、 左から右にたどっていく関数である。 \fIroot\fP
+は起点となるノードへのポインタである。 \fIroot\fP に根以外のノードを指定すると、部分木が対象となる。 \fBtwalk\fP()
+は、ノードを訪れる度にユーザ関数 \fIaction\fP を呼び出す (内部ノードに対しては 3 回、葉に対しては 1 回呼び出しが行われる)。
+\fIaction\fP には以下の順に 3 つの引き数が与えられる。 最初の引き数は訪れたノードへのポインタである。 ノードの構造体は規定されていないが、
+ポインタを要素へのポインタのポインタにキャストし、 ノードに格納された要素にアクセスすることができる。
+アプリケーションは、この引き数が指す構造体を変更してはならない。 2 番目の引き数には、内部ノードの場合は訪問回数に応じて \fBpreorder\fP,
+\fBpostorder\fP, \fBendorder\fP のいずれかの整数が、 葉を最初に訪れた場合は \fBleaf\fP の値が渡される (これらのシンボルは
+\fI<search.h>\fP で定義されている)。 3 番目の引き数はノードの深さで、根の場合は深さ 0 である。
.PP
(より一般的には、\fBpreorder\fP, \fBpostorder\fP, \fBendorder\fP は \fBpreorder\fP, \fBinorder\fP,
\fBpostorder\fP として知られている: それぞれ、子要素を辿る前・最初の子要素を辿った後かつ 2 番目の子要素を辿る前・
子要素を辿った後ということを表している。 よって \fBpost\%order\fP という名前を選ぶのは少し紛らわしい。)
.PP
\fBtdestroy\fP() は \fIroot\fP が指す木構造全体を削除し、 \fBtsearch\fP() 関数で確保されたリソースを全て解放する。
-木構造の各ノードについて、関数 \fIfree_node\fP が呼び出される。 データへのポインタがこの関数の引数として渡される。
+木構造の各ノードについて、関数 \fIfree_node\fP が呼び出される。 データへのポインタがこの関数の引き数として渡される。
そのような動作が必要でなければ、 \fIfree_node\fP は何もしない関数へのポインタでなければならない。
.SH 返り値
\fBtsearch\fP() は、木構造に見つかったアイテムか、 新しく追加したアイテムへのポインタを返す。
.SH 準拠
SVr4, POSIX.1\-2001. 関数 \fBtdestroy\fP() は GNU の拡張である。
.SH 注意
-\fBtwalk\fP() は根へのポインタを引数にとるが、 ほかの関数は根へのポインタへのポインタである。
+\fBtwalk\fP() は根へのポインタを引き数にとるが、 ほかの関数は根へのポインタへのポインタである。
.PP
\fBtdelete\fP() は、削除したノードの使用していたメモリを解放するが、 ノードに対応するデータのメモリは、ユーザが解放しなければならない。
.PP
-下のプログラム例は、ユーザ関数が "endorder" か "leaf" を引数にして 呼び出されて以降は、 \fBtwalk\fP()
+下のプログラム例は、ユーザ関数が "endorder" か "leaf" を引き数にして 呼び出されて以降は、 \fBtwalk\fP()
がそのノードを参照しないことを前提としている。 これは GNU ライブラリの実装では機能するが、System V のマニュアルには存在しない。
.SH 例
以下のプログラムは 12 個の乱数を二分木に挿入した後、 挿入した数を順番に出力する (挿入の際、重複した乱数は 1 つにまとめられる)。
OSDN Git Service
