0

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

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

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

4

2 に答える 2

4

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

規範事例

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

誘導ステップ

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

visit(node)

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

preorder(node.left) 

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

preorder(node.right)

と同じnode.left

于 2012-09-25T15:40:11.577 に答える
1

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

于 2012-09-25T15:03:17.203 に答える