binary-tree - 使用归纳证明二叉树属性

Question

我在使用归纳法证明二叉树属性时遇到了麻烦：

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

我的设置正确吗？如果是这样，我该如何展示这些东西。我所尝试的一切最终都变得一团糟。谢谢您的帮助

Answer 1

你错过了一些东西。

对于属性 1，您的基本情况必须与您要证明的内容一致。因此，具有 0 个内部节点的树的高度必须最多为 0+1=1。这是真的：考虑一棵只有根的树。

对于归纳步​​骤，考虑具有 k-1 个内部节点的树。如果它的高度最多为k（假设），再增加一个节点只能将它提升到k+1，不能更高。所以 k-internal-node 树的高度最多为 k+1。

属性 2 为假。反例：

    5
  4  6
 3    7
2      8

5个内部节点，2个叶子。

所以你可能想证明一些不同的东西。