algorithm - プレオーダーツリートラバーサルアルゴリズムが終了したことを証明する方法は?

Question

構造帰納法は、アルゴリズムの終了特性を証明する通常の方法だと思いますが、ツリーアルゴリズムの帰納法によって証明するのはそれほど簡単ではありません。今、私は事前注文ツリートラバーサルアルゴリズムが終了可能であることを証明するのに苦労しています:

preorder(node)
  if node == null then return
  visit(node)
  preorder(node.left) 
  preorder(node.right)

どのように証明すればよいですか？

score 4 · Accepted Answer

木の高さの強い誘導によって。

規範事例

アルゴリズムは高さ 0 のツリーで終了します。これは、高さ 0 のツリーには子のないルートがあるためです。visit(node)ルート上は単一のステップであり、両方であるため、にアクセスしnode.leftてnode.right終了しますNULL。

高さのすべての木で事前順序トラバーサルが終了すると仮定すると、高さの0, 1, 2, .. nすべての木で終了することが証明されn+1ます。それを見てみましょう：

visit(node)

ワンステップなので終了。

preorder(node.left)

ツリーの高さがである場合、高さn+1はnode.left高々のツリーでnあり、強い帰納的仮説により、事前順序トラバーサルは高さがより小さいか等しいツリーで終了するため、終了しますn。

preorder(node.right)

と同じnode.left。

score 1 · Accepted Answer

ツリーにはサイクルが含まれていません。サイクルがあった場合、アルゴリズムは永久に実行されます。したがって、サイクルがないことが証明の重要なポイントです。他のポイントは左または右であり、メモリの制約によって最終的に null を指すようにバインドされます。