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-28 φ(-_-)

[]はじめての C

二分木 8

それぞれの 走査は、stack か queue の どちらかを 使うことで、再帰を 用いることなしに、実行させることが できます。 一つの やり方として 反復版で inorder 走査を 書いてみましょう ▽

void tree_walk(struct Node *tree)
{
struct Node *node = tree;
struct Node **stack;
int top = 0;
int height;

height = tree_height(tree) + 1;
stack = malloc(height * sizeof(*stack));

for ( ; ; ) {
while (node != NULL) {
stack[top++] = node;
node = node->left;
}
if (top == 0)
return;
node = stack[--top];
printf("%d ", node->data);
node = node->right;
}
}

多くの場合、反復法は 最良の 選択です。 しかし 経験から いえば、そんな機会は ほんの わずかです。 複雑なことが 求められたと 確信する その時までは、より シンプルな 方法を 用いるのが いいでしょうね。

それと、注意ぶかい 人なら、この 反復版 tree_walk 関数に なにか 潜ませてるのに 気づくでしょう。 そこに 記されてる tree_height 関数って 何なんでしょうか ?

そう、これは 二分木の 高さを 得るための 役にたつ 関数です。

高さ - height - とは、null ポインタに 行き着くまでに たどることのできる ノードの 最大数のことです。

つぎの 木だと、高さは 2 に なります ▽

...4...
.2...6.
1.3.5.7

また、root までの 数を 数えようとするため、tree_walk では、stack に "高さ + 1" 分の ポインタを 割り当てています。

きっと、この tree_height の コードを 見てみたいでしょうね。 それは こうなります ▽

int tree_height(struct Node *tree)
{
int left_height;
int right_height;

if (tree == NULL)
return -1;
left_height = tree_height(tree->left);
right_height = tree_height(tree->right);
if (left_height < right_height)
return right_height + 1;
else
return left_height + 1;
}

この tutorial で 串ざしに - flesh out - しておいた 操作のたぐい - operations - を 使うことで、二分木を 用いて、広い 範囲に わたって 作業を することが できるように なります。 えっ、あざやかだって ? :p

(追記) コードが 一部 まちがっていたので、訂正。(05/9/16)

 | 

[シラノの新聞]

[枇杷と柿]

[馬葉礼 談話]

[My Links]

[Network Archives]


[かうんた→ 537091]