0

帰納法を使用して二分木のプロパティを証明するのに問題があります。

Property 1 - A tree with N internal nodes has a maximum height of N+1
    base case - 0 internal nodes has a height of 0
    assume - a tree with k internal nodes has a maximum height of k+1 where k exists in n
    show - true for all k+1 or true for all k-1

Property 2 - A tree with a tree with N internal nodes has N + 1 leaf nodes
    base case - 0 internal nodes has 1 leaf node (null)
    assume - a tree with k internal nodes has k + 1 leaf nodes where k exists in n
    show - true for all k+1 or true for all k-1

私のセットアップは正しいですか？もしそうなら、どうすればこれらのものを実際に見せることができるでしょうか。私が試したことはすべて、結局めちゃくちゃになりました。助けてくれてありがとう

4

1 に答える 1

0

You're missing a few things.

For property 1, your base case must be consistent with what you're trying to prove. So a tree with 0 internal nodes must have a height of at most 0+1=1. This is true: consider a tree with only a root.

For the inductive step, consider a tree with k-1 internal nodes. If its height is at most k (assumed), adding one more node can only raise it to k+1, and no higher. So the k-internal-node tree has height at most k+1.

Property 2 is false. Counterexample:

    5
  4  6
 3    7
2      8

5 internal nodes, 2 leaves.

So there's probably something different you wanted to prove.

于 2012-11-02T06:03:34.117 に答える