二分木で再帰を使わない問題

[dcba]

二分木のすべてのノードをたどり、ノードに格納されている整数の総和を計算したい。以下の問に答えよ。二分木のデータ構造は以下のものを使え。

コード:

struct  bintree{
int val;
struct bintree *left,*right;
};

問①
再帰呼び出しを使わず、スタックデータ構造を新たに定義し、これを用いて実現するプログラムを書け。
問②
再帰呼び出しも使わず、新たなデータ構造も追加せず、データ構造bintree中のポインタを変しながら実現する方法を、まず言葉で簡潔に述べ、プログラムを書け。

という問題の答えがわかりません。
構造体で定義されている二分木を、再帰なしでどうやって渡るのかがそもそも思いつきません。
どなたか解答を教えてください。

[みけCAT]

フォーラムルールをお読みください。
課題の丸投げは禁止されています。

[かずま]

課題というか、大学院の入学試験の過去問のようです。
平成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;
}

[dcba]

ありがとうございました！

[かずま]

例だけ言われてもうれしくありません。

プログラムを理解していることを示すために、
「再帰呼び出しも使わず、新たなデータ構造も追加せず、
データ構造bintree中のポインタを変しながら実現する方法を、
まず言葉で簡潔に述べ、」の部分に答えてください。

また、丸投げ禁止や、出典のない引用などのルール違反も謝罪
してから、解決としましょう。

なお、私のプログラムでは、ポインタを変更したままで、二分木の
データ構造を壊していますが、できたらこれを修復しながら総和を
求めるプログラムにしてください。

[かずま]

例だけ言われてもうれしくありません。

訂正します。
例だけ → 礼だけ

[dcba]

＞プログラムを理解していることを示すために、
＞「再帰呼び出しも使わず、新たなデータ構造も追加せず、
＞データ構造bintree中のポインタを変しながら実現する方法を、
＞まず言葉で簡潔に述べ、」の部分に答えてください。

探索に行くノードへのルートを、その探索が終わったときに戻るべきノードへのルートに付け替える。


＞また、丸投げ禁止や、出典のない引用などのルール違反も謝罪
＞してから、解決としましょう。

申し訳ありませんでした。

[かずま]

＞プログラムを理解していることを示すために、
＞「再帰呼び出しも使わず、新たなデータ構造も追加せず、
＞データ構造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;
}

[かずま]

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 でした。

[かずま]

木(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;
}