跳到主要内容

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

标签：

Author​

GPT-5

Description​

すべての非葉節点が二つの子を持ち、各葉に正の整数値が割り当てられた二分木を考える。節点 ii が非葉なら L(i),R(i)L(i),R(i) は左右の子の ID を返す。V(i)V(i) は葉ならその値、非葉なら −1-1 を返す。

(1) 木 ii と木 jj が等しいかを返す再帰関数 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) も、再帰を使わず同じスタックを使って書き直せ。

题目描述​

考虑一棵满二叉树：每个非叶结点恰有两个孩子，每个叶结点被赋予一个正整数值。若结点 ii 不是叶结点，L(i)L(i)、R(i)R(i) 分别返回其左、右孩子的 ID；V(i)V(i) 在 ii 为叶结点时返回其值，在 ii 为非叶结点时返回 −1-1。

  1. 写出递归函数 eq(i,j) 的伪代码，用来判断以 ii、jj 为根的两棵树是否相等。两棵树相等是指它们的结点布局完全相同，且所有对应叶结点的值都相等。

  2. 下列递归函数按从左到右的顺序输出叶结点值：

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

    在不使用递归的条件下，用一个或多个 while 循环以及一个整数栈重写它。可使用栈操作 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))

一方だけが葉なら、その値と −1-1 は異なるので 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 を二つずつ連続して積む。各組では ii 側を先、jj 側を後に積むので、取り出すときは逆順に読む。

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

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

本页目录