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

[]はじめての C

二分木 9

これまで 見てきた 二分木では、すべて、データ構造体の テキスト内で 定義が されています。

より 多くの 制御が 必要と なったとき、例えば、下に 動くだけでなく、双方向リストと 同じように、木の 上方にも 移動させたいことが あります。

そのためには、その ノードの親 - parent - への ポインタが 必要です。 それは 次のように 実装できます ▽

struct Node {
int data;
struct Node *parent;
struct Node *left;
struct Node *right;
};

構造体に シンプルな 変更を 加えることで、別の ポインタを いじれるように なります。

挿入前と 同じ動作 - semantics - を 確保するため、同じように、ちょっとだけ new_node を 変更する 必要が あります ▽

int make_node(struct Node **node, struct Node *parent, int value)
{
*node = malloc(sizeof(**node));
if (*node == NULL)
return 0;

(*node)->data = value;
(*node)->parent = parent;
(*node)->left = NULL;
(*node)->right = NULL;
return 1;
}

注意するのは、親 - parent - に ポインタを 渡すのは、ノードポインタへの ポインタと 同じだと いうことです。

ここでは、空の 木 - empty tree - の 場合に 特別な 処理を 行うことで、挿入が より やさしく できます ▽

int tree_insert(struct Node **tree, int value)
{
struct Node *node;

node = *tree;
if (node == NULL)
return make_node(tree, NULL, value);
for ( ; ; ) {
if (value > node->data) {
if (node->right = NULL)
return make_node(&node->right, node, value);
node = node->right;
}
else if (value < node->data) {
if (node->left == NULL)
return make_node(&node->left, node, value);
node = node->left;
}
else
return 1;
}
}

この操作での 注意点は、null へは ノードを 割り当てられないことです。 そこで、実際に そこへ 行かずに、規則に 則って - play game to - 正確な 位置を 見つけます。

例えば、挿入したい値が 現在の ノードの値より 大きく、node->right が null の 場合は、node->right の アドレスが 欲してる 新しい項目の 場所であり、ノードが 親であることが わかっています。

node->right が null で なければ、ノードが node->right を 指すように セットします。

同じ 手順で、左の 分肢を たどっていきます。



よく できた 参考書の あの 腹のたつ シキタリ - infuriating traditions - に 従って、親ポインタ - parent pointers - の 削除に ついては、あなたがたの 演習の ために、残して おきましょうね。:p



前に 使った 削除用の 関数で、 どうして ノードへの successor を 見つけたかを 覚えていますか ?

あの 関数が 変更できるか オネガイすることは できないでしょうか ?

よろしい、今だと 親ポインタも あって、再帰を 使わずに 木の 上方へと 移動できるので、簡単に それを 書くことが できます ▽

struct Node **successor(struct Node *node)
{
struct Node *heir;

if (node->right != NULL) {
heir = node->right;
while (heir->left != NULL)
heir = heir->left;
}
else {
heir = node->parent;
while (heir != NULL && node == heir->right) {
node = heir;
heir = heir->parent;
}
}
return heir;
}

初めの 部分は tree_remove と まったく いっしょで、次の ところも ほとんど 同じです。その 2番目の ところには、リーフ - 木の ちょうど 一番 下に あたる ノード - を 見つけることが 含まれています。

それで、リーフでない ノードの successor を 見つけて、ノードの 右の 分肢の、さらに その左の 分肢を 全て たどっていきます。

リーフノードの successor を 見つけると、それ以上 進むことが できないところまで、左の 分肢を 上がっていきます。

いま、「でも それじゃ、親ポインタで、一つの 方向に 上がってるだけじゃないか !」と 思ったでしょう。

そうですよ ! しかし、以前 訪れて コード上に 示されていた 方角が、どちらなのかと いうことも、同じく 見失うことが ないのです。

それが どうして 実行されるのか わかるために、このロジックを 紙の上に 書いてみる、ということを 忘れないでください。

二分木の tutorial 初回分は、これで おしまいです。

まだ あるのか ... oLr

 | 

[シラノの新聞]

[枇杷と柿]

[馬葉礼 談話]

[My Links]

[Network Archives]


[かうんた→ 528675]