证明在任意非空二叉树T上,分支结点数等于叶子结点数的条件是二叉树T上度为1的结点只有1个。
时间: 2024-04-03 17:32:08 浏览: 50
二叉树叶子结点个数计算.doc
设二叉树T上的分支结点数为b,叶子结点数为l,度为1的结点数为d1。我们需要证明以下命题:
当且仅当二叉树T上度为1的结点只有1个时,有b = l。
证明:
1. 当二叉树T上度为1的结点只有1个时,可以将二叉树T分为三部分:根节点、度为1的结点和叶子结点。由于度为1的结点只有1个,所以根节点和叶子结点的数量相等,即l = b / 2。因此有b = 2l,即b = l。
2. 当二叉树T上度为1的结点有多个时,设度为1的结点数为d1,则二叉树T上的结点总数为n = l + b + d1 + 1。因为度为1的结点只有1个时,n = 2l + 1,所以当d1 > 1时,n > 2l + 1,即b > l,不满足b = l的条件。
综上所述,当且仅当二叉树T上度为1的结点只有1个时,有b = l。
阅读全文