Dokusyo-nissi Bessitu

<< 2005/07 >>
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

[Debian Memo] (for Woody)
[sekiyo HPへ]

[はじめてのC] C言語のページ (1)
[その 2] (2)
[その 3] ABC of C
[その 4] CPP World Tutorial (1) (by Prelude) linkrot
[その 5] The Standard C Library (Null)
[その 6] CPP World Tutorial (2) linkrot
[その 7] (3)
[その 8] (4)
[その 9] 作ってわかる Cプログラミング (1)
[その 10] (2)
[その 11] Arrays and Pointers in C
[その 12] Learning GNU C (1)
[その 13] (2)
[その 14] (3)
[その 15] (4)
[その 16] アドレスブック
[K & R 2nd] The C Programming Language (1)
[その 2] (2)
[その 3] (3)
[その 4] (4)
[その 5] (5)
[その 6] (6)

[my bookcase]

(サーチエンジンから 来られた方で 該当する
キーワードが 見つからないときには、上の
はてな検索窓から 再度検索してください ←
[日記] のほうを クリック)

 | 

2005-07-27 φ(-_-)

[]はじめての C

二分木 7

構築したり、二分木から 要素を 削除する 基本的な 操作は 手に入れました。 また、木に 要素が あるかどうかを 調べる コードも あります。

さて、あると 考えたものが、実際に あるのかを、はっきり 確かめる 必要が ありますよね。 それは、木を 渡っていくか、または 各ノードを たどっていき、それで ある作業を 行うことで 可能です。

再帰を 使った 走査 - traversal - 関数による コードでは、上りの - ascending - ソート順で、各ノードの 値を プリントしていきます。 これは inorder 走査とも 呼ばれます ▽

void btree_walk(struct Node *tree)
{
if (tree == NULL)
return;

btree_walk(tree->left);
printf("%d ", tree->data); /* <- ここが inorder */
btree_walk(tree->right);
}

この操作は、再帰を わかっていれば、すぐ 明らかになります。*1

はじめに 左の 分肢を たどっていき、折り返してから - on the way back out - プリントします。 それから、右の 分肢を たどって プリントします。

上の 関数から わかることは、これが 再帰の 実行であって、二分木探索ではないと いうことです。 それで 動き回る - move on - のです。

inorder 走査は、もっとも 一般的な 走査の やり方です。 他に (走査には) postorder と levelorder と preorder とが あります。

postorder は 木を こわしていくのに 役にたちます。 まず 左と 右の 両方の 分肢を 訪れてから、ノードへの 操作を 実行します ▽

void btree_destroy(struct Node *tree)
{
if (tree == NULL)
return;

btree_destroy(tree->left);
btree_destroy(tree->right);
free(tree); /* <- ここが postorder */
}

も一つ 再帰が わかってない ...

*1:小さい node から プリントされていく

 | 

[シラノの新聞]

[枇杷と柿]

[馬葉礼 談話]

[My Links]

[Network Archives]


[かうんた→ 526111]