我被困在一个问题的归纳案例上。
问题:
将树的高度定义为根与任何叶子之间的最大边数。我们认为一棵空树的高度为 -1,由单个节点组成的树的高度为 0。通过归纳证明每个高度为 h 的非空二叉树包含少于 2 (h+1)节点。
So I started:
Base case: h = 0 (Since a non-empty tree consists of a single node
or
more, the first case would be an empty node)
= 2 (0+1) = 2 (1) = 2 当高度为 0 时,树由单个节点组成,所以是的,1 个节点小于 2 个节点。归纳步长 = h 小于或大于 0 这就是我卡住的地方...我知道这句话是正确的,因为高度总是比节点数小 1,我只是不知道如何证明它代数。
提前致谢。