跳到主要内容

東京工業大学 情報理工学院 数理・計算科学系 2018年8月実施 午前 問9

标签：

Author​

GPT-5

Description​

すべての非葉節点が二つの子を持ち、各葉に正の整数値が割り当てられた二分木を考える。節点 が非葉なら は左右の子の ID を返す。 は葉ならその値、非葉なら を返す。

(1) 木 と木 が等しいかを返す再帰関数 eq(i,j) の擬似コードを示せ。二つの木が等しいとは、節点配置が同じで、対応する葉の値がすべて等しいことをいう。

(2) 葉の値を左から右へ出力する次の再帰関数を、再帰を使わず、一つ以上の while 文と整数スタックを使って書き直せ。

tr(i):
    if V(i) == -1:
        tr(L(i))
        tr(R(i))
    else:
        print V(i)

スタック操作として、空かを返す E()、値を積む U(v)、最上部を取り除いて返す O() を使用してよい。

(3) eq(i,j) も、再帰を使わず同じスタックを使って書き直せ。

Kai​

(1)​

eq(i, j):
    vi = V(i)
    vj = V(j)

    if vi != -1 or vj != -1:
        return vi == vj

    return eq(L(i), L(j)) and eq(R(i), R(j))

一方だけが葉なら、その値と は異なるので false となる。両方が葉なら葉の値を比較し、両方が内部節点なら左右の部分木を再帰的に比較する。

(2)​

右の子を先に積み、左の子を後に積めば、LIFO のスタックから左部分木が先に取り出される。

tr_iterative(i):
    U(i)

    while not E():
        p = O()
        if V(p) == -1:
            U(R(p))
            U(L(p))
        else:
            print V(p)

(3)​

比較する節点 ID を二つずつ連続して積む。各組では 側を先、 側を後に積むので、取り出すときは逆順に読む。

eq_iterative(i, j):
    U(i)
    U(j)

    while not E():
        q = O()
        p = O()
        vp = V(p)
        vq = V(q)

        if vp != -1 or vq != -1:
            if vp != vq:
                return false
        else:
            # 右の組を先、左の組を後に積む
            U(R(p))
            U(R(q))
            U(L(p))
            U(L(q))

    return true

内部節点では必ず二組、葉では零組を追加するため、スタックには常に完全な節点対が保存される。

目录