计算揭秘：768个结点的完全二叉树中叶结点个数究竟几何？

在一棵完全二叉树中，度为 1 的结点个数最多为 1 个。 设完全二叉树的结点数为 n，度为 0（叶子结点）的个数为 n0，度为 1 的个数为 n1，度为 2 的个数为 n2 。 则有 n = n0 + n1 + n2 ，又因为 n2 = n0 - 1 ，且 n = 768 ，所以 n0 + n1 + n0 - 1 = 768 ，即 2n0 + n1 - 1 = 768 。 因为完全二叉树度为 1 的结点个数要么是 0 要么是 1 ，所以分别讨论： 当 n1 = 0 时，2n0 - 1 = 768 ，2n0 = 769 ，n0 不是整数，不符合。 当 n1 = 1 时，2n0 + 1 - 1 = 768 ，2n0 = 768 ，n0 = 384 。 所以该完全二叉树中叶结点的个数是 384 个。 ######[AI写代码神器 | 271点数解答 | 2024-11-13 00:55:05]