ページ 1 ／ 1
二分木で再帰を使わない問題
Posted: 2014年4月01日(火) 16:32
by dcba
二分木のすべてのノードをたどり、ノードに格納されている整数の総和を計算したい。以下の問に答えよ。二分木のデータ構造は以下のものを使え。
コード:
struct bintree{
int val;
struct bintree *left,*right;
};
問①
再帰呼び出しを使わず、スタックデータ構造を新たに定義し、これを用いて実現するプログラムを書け。
問②
再帰呼び出しも使わず、新たなデータ構造も追加せず、データ構造bintree中のポインタを変しながら実現する方法を、まず言葉で簡潔に述べ、プログラムを書け。
という問題の答えがわかりません。
構造体で定義されている二分木を、再帰なしでどうやって渡るのかがそもそも思いつきません。
どなたか解答を教えてください。
Re: 二分木で再帰を使わない問題
Posted: 2014年4月01日(火) 16:36
by みけCAT
フォーラムルールをお読みください。
課題の丸投げは禁止されています。
Re: 二分木で再帰を使わない問題
Posted: 2014年4月04日(金) 23:33
by かずま
課題というか、大学院の入学試験の過去問のようです。
平成22年度 東京大学大学院情報理工学系研究科 コンピュータ科学専攻
入学試験問題 専門科目 I
面白そうなので、考えてみました。
再帰呼び出しを使うと、こんなに簡単。
コード:
#include <stdio.h>
struct bintree {
int val;
struct bintree *left, *right;
};
struct bintree tree[6] = {
{ 10, tree + 1, tree + 2 }, // tree[0] root
{ 20, tree + 3, NULL }, // tree[1]
{ 30, tree + 4, tree + 5 }, // tree[2]
{ 40, NULL, NULL }, // tree[3] leaf
{ 50, NULL, NULL }, // tree[4] leaf
{ 60, NULL, NULL }, // tree[5] leaf
};
int sum(const struct bintree *node)
{
return node ? sum(node->left) + node->val + sum(node->right) : 0;
}
int main(void)
{
printf("%d\n", sum(tree));
return 0;
}
スタックを使うとこうなります。
コード:
struct { struct bintree *node; int state; } stack[1000];
int sp = 0;
#define PUSH() (stack[sp].node = node, stack[sp++].state = state)
#define POP() (node = stack[--sp].node, state = stack[sp].state)
int sum(struct bintree *node)
{
int state = 0, s = 0;
PUSH(), state = 1;
while (state)
if (state == 1) {
//s += node->val; // preorder
state++;
if (node->left) PUSH(), state = 1, node = node->left;
}
else if (state == 2) {
s += node->val; // in-order
state++;
if (node->right) PUSH(), state = 1, node = node->right;
}
else {
//s += node->val; // postorder
POP();
}
return s;
}
bintree の中のポインタを変更してよいのなら。
コード:
int sum(struct bintree *node)
{
int s = 0;
struct bintree dummy = { 0 }; // root の dummy parent node
struct bintree *parent = &dummy; // parent node
struct bintree *child; // child node
while (node != &dummy)
if (node->left != parent) {
//s += node->val; // preorder
child = node->left, node->left = parent;
if (child) parent = node, node = child; // 左があれば降りて行く
}
else if (node->right != parent) {
s += node->val; // in-order
child = node->right, node->right = parent;
if (child) parent = node, node = child; // 右があれば降りて行く
}
else {
//s += node->val; // postorder
node = parent, parent = parent->left; // 上に戻る
}
return s;
}
Re: 二分木で再帰を使わない問題
Posted: 2014年4月12日(土) 16:37
by dcba
ありがとうございました！
Re: 二分木で再帰を使わない問題
Posted: 2014年4月12日(土) 17:23
by かずま
例だけ言われてもうれしくありません。
プログラムを理解していることを示すために、
「再帰呼び出しも使わず、新たなデータ構造も追加せず、
データ構造bintree中のポインタを変しながら実現する方法を、
まず言葉で簡潔に述べ、」の部分に答えてください。
また、丸投げ禁止や、出典のない引用などのルール違反も謝罪
してから、解決としましょう。
なお、私のプログラムでは、ポインタを変更したままで、二分木の
データ構造を壊していますが、できたらこれを修復しながら総和を
求めるプログラムにしてください。
Re: 二分木で再帰を使わない問題
Posted: 2014年4月12日(土) 20:42
by かずま
かずま さんが書きました:例だけ言われてもうれしくありません。
訂正します。
例だけ → 礼だけ
Re: 二分木で再帰を使わない問題
Posted: 2014年4月13日(日) 14:20
by dcba
＞プログラムを理解していることを示すために、
＞「再帰呼び出しも使わず、新たなデータ構造も追加せず、
＞データ構造bintree中のポインタを変しながら実現する方法を、
＞まず言葉で簡潔に述べ、」の部分に答えてください。
探索に行くノードへのルートを、その探索が終わったときに戻るべきノードへのルートに付け替える。
＞また、丸投げ禁止や、出典のない引用などのルール違反も謝罪
＞してから、解決としましょう。
申し訳ありませんでした。
Re: 二分木で再帰を使わない問題
Posted: 2014年4月14日(月) 01:44
by かずま
dcba さんが書きました:＞プログラムを理解していることを示すために、
＞「再帰呼び出しも使わず、新たなデータ構造も追加せず、
＞データ構造bintree中のポインタを変しながら実現する方法を、
＞まず言葉で簡潔に述べ、」の部分に答えてください。
探索に行くノードへのルートを、その探索が終わったときに戻るべきノードへのルートに付け替える。
「ノードへのルート」の「ルート」は、根(root) ではなく、
経路(route) ですよね。ちょっと説明が不十分かなあ。
私なら次のように書きます。
コード:
left と right に親のノードへのポインタを入れておき、
left と right の両方の処理が終わったら、親へ戻る。
かずま さんが書きました:
なお、私のプログラムでは、ポインタを変更したままで、二分木の
データ構造を壊していますが、できたらこれを修復しながら総和を
求めるプログラムにしてください。
こちらは、むずかしいようですね。
left と right を壊していたのを元通り修復するコードですが、
次のようにしてみました。
アドレスの下位 1ビットが 0 であることを想定しているので、
行儀の悪いプログラムです。
コード:
#include <stdio.h>
struct bintree {
int val;
struct bintree *left, *right;
};
struct bintree tree[6] = {
{ 10, tree + 1, tree + 2 }, // tree[0] root
{ 20, tree + 3, NULL }, // tree[1]
{ 30, tree + 4, tree + 5 }, // tree[2]
{ 40, NULL, NULL }, // tree[3] leaf
{ 50, NULL, NULL }, // tree[4] leaf
{ 60, NULL, NULL }, // tree[5] leaf
};
typedef long long INT;
int sum(struct bintree *node)
{
int s = 0, left = 0, state = 0;
struct bintree *parent = NULL; // parent node
struct bintree *child; // child node
while (1)
if (state == 0) {
//s += node->val; // preorder
child = node->left;
if (child)
node->left = (struct bintree *)((INT)parent | left),
parent = node, node = child, left = 1;
else state = 1;
}
else if (state == 1) {
s += node->val; // in-order
child = node->right;
if (child)
node->right = (struct bintree *)((INT)parent | left),
parent = node, node = child, left = 0;
else state = 2;
}
else {
//s += node->val; // postorder
if (parent == NULL) break;
child = node, node = parent;
if (left)
parent = (struct bintree *)((INT)node->left & ~ 1),
left = (INT)node->left & 1, node->left = child, state = 1;
else
parent = (struct bintree *)((INT)node->right & ~ 1),
left = (INT)node->right & 1, node->right = child, state = 2;
}
return s;
}
void print(struct bintree *node, int level)
{
if (node) {
print(node->right, level+1);
printf("%*s%d\n", level * 4, "", node->val);
print(node->left, level+1);
}
}
int main(void)
{
print(tree, 0);
printf("sum = %d\n", sum(tree));
print(tree, 0);
return 0;
}
Re: 二分木で再帰を使わない問題
Posted: 2014年4月15日(火) 22:24
by かずま
かずま さんが書きました:dcba さんが書きました:
left と right を壊していたのを元通り修復するコードですが、
次のようにしてみました。
すみません。バグがありました。39行目のセミコロンの前に
, state = 0 を追加して次のようにしてください。
コード:
parent = node, node = child, left = 0, state = 0;
状態を番号で表すのはよくないですね。
コード:
enum { FROM_PARENT, FROM_LEFT, FROM_RIGHT } state = FROM_PARENT;
としておけばよかった。
実行結果
コード:
60
30
50
10
20
40
sum = 210
60
30
50
10
20
40
バグがあるときは、sum = 160 でした。
Re: 二分木で再帰を使わない問題
Posted: 2014年4月16日(水) 23:44
by かずま
木(tree) が空でも 0 を返すように、while (1) を while (node) に変えました。
また、left というフラグを使わないようにしました。
でも、ポインタの下位 1ビットが 0 であるのを利用していることには変わりありません。
コード:
typedef long long INT; // sizeof(struct bintree *) == sizeof(long long)
//typedef int INT; // sizeof(struct bintree *) == sizeof(int)
#define NOT(x) ((struct bintree *)~(INT)(x))
int sum(struct bintree *node)
{
int s = 0, state = 0;
struct bintree *child, *parent = NULL;
while (node)
if (state == 0) { // from parent
//s += node->val; // preorder
child = node->left;
if (child)
node->left = NOT(parent), parent = node, node = child;
else state = 1;
}
else if (state == 1) { // from left child
s += node->val; // in-order
child = node->right;
if (child)
node->right = parent, parent = node, node = child, state = 0;
else state = 2;
}
else { // state == 2, from right child
//s += node->val; // postorder
if (parent == NULL) break;
child = node, node = parent;
if ((INT)node->left & 1)
parent = NOT(node->left), node->left = child, state = 1;
else
parent = node->right, node->right = child;
}
return s;
}