求n个节点的完全二叉树的高度
时间: 2023-06-13 12:05:10 浏览: 167
完全二叉树的定义是除了最后一层节点不满外,其它层节点都是满的,并且最后一层的节点都集中在左边。
假设这棵完全二叉树的深度为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)。
相关问题
c语言求完全二叉树节点个数
在C语言中,求完全二叉树节点个数可以采用以下方法:
1. 定义一个结构体表示二叉树节点,包含左右子节点指针和节点值等信息。
```
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
```
2. 定义一个函数countNodes,用于计算完全二叉树节点个数,函数参数为指向根节点的指针。
```
int countNodes(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = 0, rightHeight = 0;
struct TreeNode *left = root, *right = root;
while (left) {
leftHeight++;
left = left->left;
}
while (right) {
rightHeight++;
right = right->right;
}
if (leftHeight == rightHeight) {
return (1 << leftHeight) - 1;
} else {
return countNodes(root->left) + countNodes(root->right) + 1;
}
}
```
3. 在countNodes函数中,首先判断根节点是否为空,如果为空则返回0。否则,分别计算左右子树的高度leftHeight和rightHeight。如果leftHeight等于rightHeight,则说明该二叉树是满二叉树,节点个数为(2^leftHeight)-1,直接返回。否则,递归计算左右子树的节点个数,加上根节点1即可。
注意:这里使用了位运算,1<<n等价于2^n。
一棵具有 n 个结点的完全二叉树的树高度(深度)是
通过完全二叉树的性质,我们知道一棵具有 n 个结点的完全二叉树的树高度(深度)为 ⌊log2n⌋+1(其中 ⌊x⌋ 表示不超过 x 的最大整数)。这是因为对于一棵深度为 h 的完全二叉树,它的叶子节点数目为 2^h 个,而一棵具有 n 个结点的完全二叉树,其叶子节点数目一定在 2^(h-1) 到 2^h 之间,因此有 2^(h-1) <= n < 2^h,两边同时取 log2,得到 h-1 <= log2n < h,再加上 1 即可得到上述结论。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)