.fi
.SH 説明
\fBtsearch\fP(), \fBtfind\fP(), \fBtwalk\fP(), \fBtdelete\fP() は 二分木を操作する関数である。 これらの関数は
-Knuth (6.2.2) Algorithm T に基づいている。 木構造における各ノードの最初のフィールドは、対応するデータ・
-ã\82¢ã\82¤ã\83\86ã\83 ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\81§ã\81\82ã\82\8bã\80\82 (å\8f\82ç\85§å\85\88ã\81®ã\83\87ã\83¼ã\82¿ã\81¯ã\80\81å\91¼ã\81³å\87ºã\81\97ã\83\97ã\83ã\82°ã\83©ã\83 ã\81§ç\94¨æ\84\8fã\81\99ã\82\8bã\80\82) \fIcompar\fP ã\81¯æ¯\94è¼\83ã\83«ã\83¼ã\83\81ã\83³ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿である。
-比較ルーチンは、アイテムへのポインタ 2 つを引き数に持つ。 比較ルーチンの返り値は、1 つ目のアイテムが 2 つ目のアイテムよりも
+Knuth (6.2.2) Algorithm T に基づいている。 木構造における各ノードの最初のフィールドは、対応するデータ
+ã\82¢ã\82¤ã\83\86ã\83 ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼ã\81§ã\81\82ã\82\8bã\80\82 (å\8f\82ç\85§å\85\88ã\81®ã\83\87ã\83¼ã\82¿ã\81¯ã\80\81å\91¼ã\81³å\87ºã\81\97ã\83\97ã\83ã\82°ã\83©ã\83 ã\81§ç\94¨æ\84\8fã\81\99ã\82\8bã\80\82) \fIcompar\fP ã\81¯æ¯\94è¼\83ã\83«ã\83¼ã\83\81ã\83³ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼である。
+比較ルーチンは、アイテムへのポインター 2 つを引き数に持つ。 比較ルーチンの返り値は、1 つ目のアイテムが 2 つ目のアイテムよりも
「小さい、等しい、大きい」によって、 「負、0、正」の整数値でなければならない。
.PP
-\fBtsearch\fP() は、木構造からアイテムを検索する関数である。 \fIkey\fP は、検索するアイテムへのポインタである。 \fIrootp\fP
-ã\81¯æ\9c¨æ§\8bé\80 ã\81®æ ¹ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿である。 木構造がノードを含まない場合、\fIrootp\fP の参照している変数は NULL
-に設定されていなければならない。 木構造にアイテムが見つかった場合、 \fBtsearch\fP() はそのアイテムへのポインタを返す。
-見つからなかった場合は、アイテムを木構造に追加し、 追加したアイテムへのポインタを返す。
+\fBtsearch\fP() ã\81¯ã\80\81æ\9c¨æ§\8bé\80 ã\81\8bã\82\89ã\82¢ã\82¤ã\83\86ã\83 ã\82\92æ¤\9cç´¢ã\81\99ã\82\8bé\96¢æ\95°ã\81§ã\81\82ã\82\8bã\80\82 \fIkey\fP ã\81¯ã\80\81æ¤\9cç´¢ã\81\99ã\82\8bã\82¢ã\82¤ã\83\86ã\83 ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼ã\81§ã\81\82ã\82\8bã\80\82 \fIrootp\fP
+ã\81¯æ\9c¨æ§\8bé\80 ã\81®æ ¹ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼である。 木構造がノードを含まない場合、\fIrootp\fP の参照している変数は NULL
+ã\81«è¨å®\9aã\81\95ã\82\8cã\81¦ã\81\84ã\81ªã\81\91ã\82\8cã\81°ã\81ªã\82\89ã\81ªã\81\84ã\80\82 æ\9c¨æ§\8bé\80 ã\81«ã\82¢ã\82¤ã\83\86ã\83 ã\81\8cè¦\8bã\81¤ã\81\8bã\81£ã\81\9få ´å\90\88ã\80\81 \fBtsearch\fP() ã\81¯ã\81\9dã\81®ã\82¢ã\82¤ã\83\86ã\83 ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼ã\82\92è¿\94ã\81\99ã\80\82
+è¦\8bã\81¤ã\81\8bã\82\89ã\81ªã\81\8bã\81£ã\81\9få ´å\90\88ã\81¯ã\80\81ã\82¢ã\82¤ã\83\86ã\83 ã\82\92æ\9c¨æ§\8bé\80 ã\81«è¿½å\8a ã\81\97ã\80\81 追å\8a ã\81\97ã\81\9fã\82¢ã\82¤ã\83\86ã\83 ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼ã\82\92è¿\94ã\81\99ã\80\82
.PP
\fBtfind\fP() は、 \fBtsearch\fP() に似ているが、 アイテムが見つからなかった場合 NULL を返す点が異なる。
.PP
\fBtdelete\fP() は木構造からアイテムを削除する。 引き数は \fBtsearch\fP() と同じである。
.PP
\fBtwalk\fP() は、二分木を深さ優先 (depth\-first) で、 左から右にたどっていく関数である。 \fIroot\fP
-は起点となるノードへのポインタである。 \fIroot\fP に根以外のノードを指定すると、部分木が対象となる。 \fBtwalk\fP()
-は、ノードを訪れる度にユーザ関数 \fIaction\fP を呼び出す (内部ノードに対しては 3 回、葉に対しては 1 回呼び出しが行われる)。
-\fIaction\fP には以下の順に 3 つの引き数が与えられる。 最初の引き数は訪れたノードへのポインタである。 ノードの構造体は規定されていないが、
-ã\83\9dã\82¤ã\83³ã\82¿ã\82\92è¦\81ç´ ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\81®ã\83\9dã\82¤ã\83³ã\82¿にキャストし、 ノードに格納された要素にアクセスすることができる。
+ã\81¯èµ·ç\82¹ã\81¨ã\81ªã\82\8bã\83\8eã\83¼ã\83\89ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼ã\81§ã\81\82ã\82\8bã\80\82 \fIroot\fP ã\81«æ ¹ä»¥å¤\96ã\81®ã\83\8eã\83¼ã\83\89ã\82\92æ\8c\87å®\9aã\81\99ã\82\8bã\81¨ã\80\81é\83¨å\88\86æ\9c¨ã\81\8c対象ã\81¨ã\81ªã\82\8bã\80\82 \fBtwalk\fP()
+は、ノードを訪れる度にユーザー関数 \fIaction\fP を呼び出す (内部ノードに対しては 3 回、葉に対しては 1 回呼び出しが行われる)。
+\fIaction\fP ã\81«ã\81¯ä»¥ä¸\8bã\81®é \86ã\81« 3 ã\81¤ã\81®å¼\95ã\81\8dæ\95°ã\81\8cä¸\8eã\81\88ã\82\89ã\82\8cã\82\8bã\80\82 æ\9c\80å\88\9dã\81®å¼\95ã\81\8dæ\95°ã\81¯è¨ªã\82\8cã\81\9fã\83\8eã\83¼ã\83\89ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼ã\81§ã\81\82ã\82\8bã\80\82 ã\83\8eã\83¼ã\83\89ã\81®æ§\8bé\80 ä½\93ã\81¯è¦\8få®\9aã\81\95ã\82\8cã\81¦ã\81\84ã\81ªã\81\84ã\81\8cã\80\81
+ã\83\9dã\82¤ã\83³ã\82¿ã\83¼ã\82\92è¦\81ç´ ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼にキャストし、 ノードに格納された要素にアクセスすることができる。
アプリケーションは、この引き数が指す構造体を変更してはならない。 2 番目の引き数には、内部ノードの場合は訪問回数に応じて \fBpreorder\fP,
\fBpostorder\fP, \fBendorder\fP のいずれかの整数が、 葉を最初に訪れた場合は \fBleaf\fP の値が渡される (これらのシンボルは
\fI<search.h>\fP で定義されている)。 3 番目の引き数はノードの深さで、根の場合は深さ 0 である。
子要素を辿った後ということを表している。 よって \fBpost\%order\fP という名前を選ぶのは少し紛らわしい。)
.PP
\fBtdestroy\fP() は \fIroot\fP が指す木構造全体を削除し、 \fBtsearch\fP() 関数で確保されたリソースを全て解放する。
-木構造の各ノードについて、関数 \fIfree_node\fP が呼び出される。 データへのポインタがこの関数の引き数として渡される。
-そのような動作が必要でなければ、 \fIfree_node\fP は何もしない関数へのポインタでなければならない。
+æ\9c¨æ§\8bé\80 ã\81®å\90\84ã\83\8eã\83¼ã\83\89ã\81«ã\81¤ã\81\84ã\81¦ã\80\81é\96¢æ\95° \fIfree_node\fP ã\81\8cå\91¼ã\81³å\87ºã\81\95ã\82\8cã\82\8bã\80\82 ã\83\87ã\83¼ã\82¿ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼ã\81\8cã\81\93ã\81®é\96¢æ\95°ã\81®å¼\95ã\81\8dæ\95°ã\81¨ã\81\97ã\81¦æ¸¡ã\81\95ã\82\8cã\82\8bã\80\82
+ã\81\9dã\81®ã\82\88ã\81\86ã\81ªå\8b\95ä½\9cã\81\8cå¿\85è¦\81ã\81§ã\81ªã\81\91ã\82\8cã\81°ã\80\81 \fIfree_node\fP ã\81¯ä½\95ã\82\82ã\81\97ã\81ªã\81\84é\96¢æ\95°ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼ã\81§ã\81ªã\81\91ã\82\8cã\81°ã\81ªã\82\89ã\81ªã\81\84ã\80\82
.SH 返り値
-\fBtsearch\fP() は、木構造に見つかったアイテムか、 新しく追加したアイテムへのポインタを返す。
-ã\83¡ã\83¢ã\83ªã\81®ä¸\8d足ã\81®ã\81\9fã\82\81ã\82¢ã\82¤ã\83\86ã\83 ã\82\92追å\8a ã\81§ã\81\8dã\81ªã\81\8bã\81£ã\81\9få ´å\90\88ã\81¯ NULL ã\82\92è¿\94ã\81\99ã\80\82 \fBtfind\fP() ã\81¯ã\80\81ã\82¢ã\82¤ã\83\86ã\83 ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿を返す。
+\fBtsearch\fP() ã\81¯ã\80\81æ\9c¨æ§\8bé\80 ã\81«è¦\8bã\81¤ã\81\8bã\81£ã\81\9fã\82¢ã\82¤ã\83\86ã\83 ã\81\8bã\80\81 æ\96°ã\81\97ã\81\8f追å\8a ã\81\97ã\81\9fã\82¢ã\82¤ã\83\86ã\83 ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼ã\82\92è¿\94ã\81\99ã\80\82
+ã\83¡ã\83¢ã\83ªã\83¼ã\81®ä¸\8d足ã\81®ã\81\9fã\82\81ã\82¢ã\82¤ã\83\86ã\83 ã\82\92追å\8a ã\81§ã\81\8dã\81ªã\81\8bã\81£ã\81\9få ´å\90\88ã\81¯ NULL ã\82\92è¿\94ã\81\99ã\80\82 \fBtfind\fP() ã\81¯ã\80\81ã\82¢ã\82¤ã\83\86ã\83 ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼を返す。
一致するアイテムが見つからない場合は NULL を返す。 検索条件に一致する要素が複数ある場合、返される値は不定である。
.PP
-\fBtdelete\fP() は削除したアイテムの親へのポインタを返す。 アイテムが見つからなかった場合は NULL を返す。
+\fBtdelete\fP() ã\81¯å\89\8aé\99¤ã\81\97ã\81\9fã\82¢ã\82¤ã\83\86ã\83 ã\81®è¦ªã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼ã\82\92è¿\94ã\81\99ã\80\82 ã\82¢ã\82¤ã\83\86ã\83 ã\81\8cè¦\8bã\81¤ã\81\8bã\82\89ã\81ªã\81\8bã\81£ã\81\9få ´å\90\88ã\81¯ NULL ã\82\92è¿\94ã\81\99ã\80\82
.PP
\fIrootp\fP が NULL の場合、 \fBtsearch\fP(), \fBtfind\fP(), \fBtdelete\fP() は NULL を返す。
.SH 準拠
SVr4, POSIX.1\-2001. 関数 \fBtdestroy\fP() は GNU の拡張である。
.SH 注意
-\fBtwalk\fP() ã\81¯æ ¹ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\82\92å¼\95ã\81\8dæ\95°ã\81«ã\81¨ã\82\8bã\81\8cã\80\81 ã\81»ã\81\8bã\81®é\96¢æ\95°ã\81¯æ ¹ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿である。
+\fBtwalk\fP() ã\81¯æ ¹ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼ã\82\92å¼\95ã\81\8dæ\95°ã\81«ã\81¨ã\82\8bã\81\8cã\80\81 ã\81»ã\81\8bã\81®é\96¢æ\95°ã\81¯æ ¹ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼ã\81¸ã\81®ã\83\9dã\82¤ã\83³ã\82¿ã\83¼である。
.PP
-\fBtdelete\fP() は、削除したノードの使用していたメモリを解放するが、 ノードに対応するデータのメモリは、ユーザが解放しなければならない。
+\fBtdelete\fP() は、削除したノードの使用していたメモリーを解放するが、
+ノードに対応するデータのメモリーは、ユーザーが解放しなければならない。
.PP
-下のプログラム例は、ユーザ関数が "endorder" か "leaf" を引き数にして 呼び出されて以降は、 \fBtwalk\fP()
+下のプログラム例は、ユーザー関数が "endorder" か "leaf" を引き数にして 呼び出されて以降は、 \fBtwalk\fP()
がそのノードを参照しないことを前提としている。 これは GNU ライブラリの実装では機能するが、System V のマニュアルには存在しない。
.SH 例
以下のプログラムは 12 個の乱数を二分木に挿入した後、 挿入した数を順番に出力する (挿入の際、重複した乱数は 1 つにまとめられる)。
.SH 関連項目
\fBbsearch\fP(3), \fBhsearch\fP(3), \fBlsearch\fP(3) \fBqsort\fP(3)
.SH この文書について
-この man ページは Linux \fIman\-pages\fP プロジェクトのリリース 3.68 の一部
+この man ページは Linux \fIman\-pages\fP プロジェクトのリリース 3.79 の一部
である。プロジェクトの説明とバグ報告に関する情報は
http://www.kernel.org/doc/man\-pages/ に書かれている。
OSDN Git Service
