一棵k叉树中已知一棵树中有n1个度为1的结点,n2个度为2的结点,问该树中有多少个叶子节点?
时间: 2024-04-22 11:22:38 浏览: 164
数据结构6-9章习题(带答案)(1).doc
假设该树中有n个叶子节点,则根据k叉树的性质,该树中一共有n1个度为1的节点,n2个度为2的节点,以及n个叶子节点。因此,可以列出以下方程:
n1 + n2 + n = 总节点数
又因为每个节点的度数都是小于等于k的,因此可以列出以下方程:
n1 + 2n2 + kn = 总节点数
将上述两个方程联立,消去总节点数,得到:
n = (k-2)n2 + 2n1
因此,该树中的叶子节点数为n = (k-2)n2 + 2n1。
阅读全文