已知一棵完全二叉树共有999个结点，试求以下问题，并给出求解

[问答题]

已知一棵完全二叉树共有999个结点，试求以下问题，并给出求解过程。 (1) 树的高度 (2) 叶子结点数

Scout201906210957273

用完全二叉树的特点 i<=n/2向下取整 i为分支结点否则为叶子结点

所以根据题目信息 999/2向下取整=499 999-499=500个叶子结点

发表于 2019-12-05 16:53:56 回复(0)

江冷易水寒

分支节点数：n/2 向下取整；叶子节点=n-分支节点

树的高度：[log₂n]向下取整+1

完全二叉树性质：

性质1：二叉树第i层上的结点数目最多为 2^i-1 (i≥1)。
性质2：深度为k的二叉树至多有2^k-1个结点(k≥1)。
性质3：包含n个结点的二叉树的高度至少为[log₂n]向下取整+1。
性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

性质4证明：

对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。
证明：假设度为1的结点个数为n1，结点总数为n，B为二叉树中的分支数。
因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：
n=n0+n1+n2
（1）
再查看一下分支数。在二叉树中，除根结点之外，每个结点都有一个从上向下的分支指向，所以，总的结点个数n与分支数B之间的关系为：n=B+1。
又因为在二叉树中，度为1的结点产生1个分支，度为2的结点产生2个分支，所以分支数B可以表示为：B=n1+2n2。
将此式代入上式，得：
n=n1+2n2+1
（2）
用（1）式减去（2）式，并经过调整后得到：n0=n2+1。

编辑于 2022-03-09 08:39:47 回复(0)