若一棵有n个结点的二叉树,其中所有分支结点的度均为k,该树中的叶子结点个数是______。
A. n(k-1)/k
B. n-k
C. (n+1)/k
D. (nk-n+1)/k
1
设总结点数为n,度为k的节点数为n1,叶子节点数为n0,就有n0*0+n1*k+1=n,其中n1=n-n0,解出来就可得到n0=(nk-n+1)/k
令n=4且只有右孩子,k=1,代入选项
可以通过数学归纳法证明,对于一棵有n个结点的二叉树,其中所有分支结点的度均为k,该树中的叶子结点个数等于(nk-n+1)/k。 当n=1时,只有一个结点,且为叶子节点,满足等式。 假设对于n=k的二叉树成立,则对于n=k+1的二叉树也成立。此时,我们可以将树划分为两部分,一部分为根节点,另一部分为除去根节点的子树。根节点的度数为k,子树中的总结点数为k,叶子结点数为(nk-n+1)/k。所以整棵树中的叶子节点数为(nk-n+1)/k + 1 = (nk-k+n+1)/k = (nk+1-n+k)/k = (nk-n+1)/k + 1。 通过数学归纳法可知,对于一棵有n个结点的二叉树,其中所有分支结点的度均为k,该树中的叶子结点个数是(nk-n+1)/k。
D
用户登录可进行刷题及查看答案
登录后提交答案