求n个节点的完全二叉树的高度

完全二叉树的定义是除了最后一层节点不满外，其它层节点都是满的，并且最后一层的节点都集中在左边。

假设这棵完全二叉树的深度为h，那么根据完全二叉树的定义，前h-1层都是满的，每层节点数分别为1, 2, 4, 8, ..., 2^(h-1)，最后一层节点数不满，但也至少有1个节点。

如果完全二叉树的节点个数为n，则最后一层节点数为n - 2^(h-1) + 1，因为前h-1层节点数为2^0 + 2^1 + ... + 2^(h-1) = 2^h - 1，所以有：

n = 2^h - 1 + (n - 2^(h-1) + 1)

化简得：

h = log2(n+1)

因此，完全二叉树的高度为log2(n+1)。

相关问题

假设有一颗三叉树有n个结点，它的最小高度为5，当三叉树有n+1个结点，它的最小高度为6，则有n个结点的二叉树最小高度为

3。

对于一颗三叉树，每个节点最多有三个子节点。当三叉树有n个节点时，最小高度为5，即从根节点到任意叶子节点的最短路径长度为5。当三叉树有n+1个节点时，最小高度为6，即从根节点到任意叶子节点的最短路径长度为6。

而对于二叉树，每个节点最多有两个子节点。由于每个节点的度数减少，相同数量的节点可以形成更深的树。所以，当二叉树有

假设一颗三叉树有n个结点，它的最小高度为5，当三叉树有n+1个结点，它的最小高度为6，则有n个结点的二叉树的最小高度为多少

根据题意，我们可以推断出这颗三叉树的每个节点都有3个子节点。当三叉树有n个节点时，最小高度为5，意味着树的高度为5，但是每个节点都有3个子节点。所以，每一层的节点数都是前一层节点数的3倍。根据这个规律，我们可以得到以下关系：

第1层：1个节点
第2层：3个节点
第3层：9个节点
第4层：27个节点
第5层：81个节点

当三叉树有n+1个节点时，最小高度为6，意味着树的高度为6，同样每个节点都有3个子节点。所以，每一层的节点数仍然是前一层节点数的3倍。根据这个规律，我们可以得到以下关系：

第1层：1个节点
第2层：3个节点
第3层：9个节点
第4层：27个节点
第5层：81个节点
第6层：243个节点

现在我们可以观察到，这些数量恰好是3的幂次方。因此，当二叉树有n个节点时，它的最小高度为log3(n+1)。

所以，n个结点的二叉树的最小高度为log3(n+1)。