用三种不同的方法求完全二叉树的叶子结点
5.4已知某完全二叉树有100个结点，试用三种不同的方法求出该二叉树的叶子结点数。 本帖最后由 isdkz 于 2023-4-8 17:43 编辑方法一：计算层数，推导叶子结点数
完全二叉树的层数可以通过公式求解：k = + 1，其中n为结点数。
对于100个结点的完全二叉树，其层数为k = + 1 = 7。
设第7层有x个叶子结点，则前6层有100 - x个结点。前6层为满二叉树，总结点数为2^6 - 1 = 63。因此，叶子结点数x = 100 - 63 = 37。
方法二：递归法
可以采用递归的方法求解完全二叉树的叶子结点数。我们将一个含有n个结点的完全二叉树分解为一个左子树和一个右子树，左子树和右子树都是完全二叉树。
设左子树结点数为m，则右子树结点数为n - m - 1。递归求解左子树和右子树的叶子结点数，最后求和即可。
对于给定的100个结点的完全二叉树，递归求解后，叶子结点数为37。
方法三：迭代法
设h为完全二叉树的层数，n为结点数。我们可以通过迭代的方式，从根结点开始，依次访问每一层结点。
对于每一个结点，如果其左子结点或右子结点为空，则将其计入叶子结点。
通过这种方式，我们可以求出完全二叉树的叶子结点数。对于给定的100个结点的完全二叉树，迭代求解后，叶子结点数为37。
综上所述，通过这三种不同的方法，我们都可以得出完全二叉树的叶子结点数为37。
页:
[1]