Man*_*yLB 4 logic binary-tree proof nodes induction
我已经能够创建一个证明,表明树中的最大总节点数等于n = 2 ^(h + 1) - 1,逻辑上我知道二叉树的高度是log n(可以绘制它出去看)但是我在构建一个正式的证据时遇到了麻烦,这个证据表明一棵有n片叶子的树至少有"log".我遇到或能够组合的每个证据总是处理完美的二叉树,但我需要适合任何情况的东西.有什么提示可以引导我朝着正确的方向前进
引理:树高的树叶数量h不超过2^h.
证明:证据是通过归纳证明的h.
基本情况:因为h = 0,树只包含一个根节点,也是一个叶子; 在这里n = 1 = 2^0 = 2^h,根据需要.
归纳假设:假设所有高度k或更低的树都比2^k节点少.
感应步骤:我们必须证明高度的树木k+1不超过2^(k+1)树叶.考虑根的左右子树.这些树的高度不超过k整棵树的高度.因此,2^k通过归纳假设,每个叶子最多具有叶子.由于叶子总数只是根子树叶数的总和,我们可以n = 2^k + 2^k = 2^(k+1)根据需要.这证明了这一说法.
定理:n叶子的二叉树至少有高度log(n).
我们在引理中已经注意到,仅由根节点组成的树有一个叶子和高度为零,因此在这种情况下声明是正确的.对于具有更多节点的树,证明是矛盾的.
让我们n = 2^a + b在那里0 < b <= 2^a.现在,假设树的高度小于a + 1,与我们打算证明的定理相反.然后高度最多a.通过引理,高度树中叶子的最大数量a是2^a.但是,我们的树有n = 2^a + b > 2^a叶子,因为0 < b; 矛盾.因此,高度小于的假设a+1必定是不正确的.这证明了这一说法.