完全二叉树的判断代码
时间: 2023-12-01 15:04:47 浏览: 35
以下是判断完全二叉树的代码实现:
```cpp
bool isCompleteTree(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
bool end = false;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node == nullptr) {
end = true;
} else {
if (end) {
return false;
}
q.push(node->left);
q.push(node->right);
}
}
return true;
}
```
该算法使用了层序遍历的思想,将每一层的节点按顺序加入队列中,如果在遍历过程中出现了空节点,那么后面的节点必须全部为空节点才能保证是完全二叉树,否则就不是完全二叉树。
相关问题
完全二叉树判断的伪代码
完全二叉树判断的伪代码如下:
1. 定义一个队列,用于存储待检查的节点。
2. 将根节点入队。
3. 循环执行以下步骤,直到队列为空:
1. 出队一个节点,并检查其左右子节点是否存在。
- 如果左子节点不存在但右子节点存在,返回 false。
- 如果左子节点存在但右子节点不存在,或者上一层已经出现了左右子节点不全的情况,后续的节点必须都是叶子节点,否则返回 false。
2. 如果左子节点存在,则将其入队。
3. 如果右子节点存在,则将其入队。
4. 如果队列为空,且所有节点都满足上述条件,则返回 true,表示是完全二叉树;否则返回 false。
伪代码实现:
```
function isCompleteBinaryTree(root):
queue = new Queue()
queue.enqueue(root)
leafNodeFound = false
while queue is not empty:
node = queue.dequeue()
if node.left is not null:
if leafNodeFound or node.right is null:
return false
queue.enqueue(node.left)
if node.right is not null:
if leafNodeFound:
return false
queue.enqueue(node.right)
else:
leafNodeFound = true
return true
```
注意:上述伪代码假设已经定义了一个队列数据结构,并实现了相应的 enqueue 和 dequeue 操作。
判断是否为完全二叉树代码
判断一棵二叉树是否为完全二叉树的方法有很多,以下是其中一种较为常见的方法:
1. 对于一颗二叉树,按照层次从上到下、从左到右的顺序进行编号,根节点编号为1,其它节点的编号为父节点编号乘2再加上1或2。
2. 对于编号为i的节点,若其有左儿子,则其左儿子的编号为2i;若其有右儿子,则其右儿子的编号为2i+1。
3. 遍历二叉树,若当前节点的编号为i,则:
- 若i=n,则这棵二叉树是完全二叉树;
- 若i>n,则这棵二叉树不是完全二叉树;
- 若i=n-1,则要判断其是否有左子树,若有则这棵二叉树是完全二叉树,否则不是。
以下是一个C++实现的代码示例:
```c++
bool isCompleteTree(TreeNode* root) {
if (root == nullptr) {
return true;
}
queue<pair<TreeNode*, int>> q;
q.emplace(root, 1);
int pre = 0;
while (!q.empty()) {
auto [node, idx] = q.front();
q.pop();
if (pre + 1 != idx) {
return false;
}
pre = idx;
if (node->left != nullptr) {
q.emplace(node->left, idx * 2);
}
if (node->right != nullptr) {
q.emplace(node->right, idx * 2 + 1);
}
}
return true;
}
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)