计算机二级公共基础二叉树问题

来源：百度知道 编辑：UC知道 时间：2024/06/12 06:49:01
一棵二叉树中共有 70 个叶子结点与 80 个度为1 的结点，则该二叉树中的总结点数为
A）219 B）221 C）229 D）231
请高手解释下

在N个节点的二叉树中，设叶子节点数为No,度为1的节点数为N1，度为2的节点数为N2；

根据二叉树总度数比节点数少1的关系可得到

N1 + 2 x N2 = N ①

又有 N1 + No + N2 = N ②

联合解得 N2 = No - 1 ；

所以根据 N1 = 80，No = 70 ，得N2 = 69

最后 N = 70 + 80 + 69 = 219

本题答案为 A）219

其实只要记住但凡二叉树中，总有 N2 = No - 1 成立就可以了