Question

证明二叉树的第i层上至多有2的i-1次方个结点

证明二叉树的第i层上至多有2的i-1次方个结点

Answer 1

第1层1个，为2^(1-1)
二叉树每个结点至多2个孩子，因此
第二层最多2 *1 = 2^(2-1)
第三层最多2*2= 2^(3-1)
....
第i层上至多有2的i-1次方个结点

Answer 2

证明二叉树的第i层上至多有2^(i-1)个结点
当i = 1时，第i层有2^(1-1)=2^0=1成立。
嗯，因为我数出来了，真的只有一个。而算出来也是只有一个，所以成立
假设当i = k是，第k层有2^（k-1）个节点
那么，第k+1层为2^(k-1) * 2 =2^(k-1) *2^1 =2^(k-1+1) = 2^((k+1)-1),符合预期，成立
这里左边的等式为什么是2^(k-1) * 2 呢？
因为第k层是2^(k-1) ，那么因为二叉树最多只有两个子节点，也就是说，所有的第k层的子节点都可以生成两个子节点，故要在第k层乘以2.
哈哈，答案我也不知道对不对，但我觉得是比较合理的