已知完全二叉树节点个数求二叉树高度

对于一个完全二叉树，其节点数可以通过遍历树来计算，从根节点开始，每层如果存在右子节点，则节点数加上2，否则加上1，一直遍历到最底层。对于高度，可以通过不断地向左遍历，直到到达叶子节点，记录下经过的层数即可，因为是完全二叉树，所以从根节点到最左侧的叶子节点一定可以到达。算法时间复杂度为O(logn*logn)。

相关问题

已知完全二叉树层数，求完全二叉树叶子结点数

对于一棵完全二叉树来说，它的叶子结点只会出现在最后一层或倒数第二层。如果我们知道完全二叉树的层数为h，那么叶子结点出现的层数就是h-1或h。

现在我们来分析叶子结点的数量。对于最后一层，它的叶子结点数目最多为2^(h-1)个。而对于倒数第二层，它的叶子结点数目可能不满，但最多为2^(h-2)个。因此，完全二叉树的叶子结点数目可以表示为：2^(h-1) + 最后一层叶子结点数目。

我们可以进一步观察最后一层叶子结点的编号规律。根据引用中的信息，最后一个结点的编号必为n，它的父结点为n/2，且为上一层最右边的一个结点。所以我们可以得出，最后一层叶子结点的数量为：n - n/2。

将上述两个结果结合起来，我们可以得到完全二叉树的叶子结点数目公式为：2^(h-1) + n - n/2。

因此，已知完全二叉树的层数h，我们可以通过计算得到它的叶子结点数目。<span class="em">1</span>

完全二叉树已知结点判断深度

完全二叉树是一种特殊的二叉树，其中除了最后一层外，每一层都尽可能地填满节点，并且所有叶子节点都在同一层上。对于给定的完全二叉树中的任意一个节点，我们可以使用其深度信息来确定其位置。

如果有一个节点i，其深度为d（根节点深度为1），那么我们可以通过以下公式计算出它在完全二叉树中的索引位置：

- 如果这是一棵满二叉树（即所有层级都是满的），那么节点i的位置是 \( 2^{(d-1)} \) 到 \( 2^d - 1 \) 之间的整数，因为从左到右填充，根节点是第一个。
- 如果不是满二叉树，但最后一层是从左边开始填充的，那么它的实际位置可能是 \( 2^{(d-1)} + (i - 1) \)，这里假设最左边的空位是0。

所以，如果你知道一个节点的深度d以及它是满二叉树还是非满二叉树，你可以计算出它的确切索引。如果不清楚是否为满二叉树，可以根据节点所在层的剩余空间来推断。