设二叉树采用二叉链表存储,设计非递归算法判断根结点为T的二叉树是否为完全二叉树。
时间: 2024-02-27 20:59:09 浏览: 101
编写算法判别给定二叉树是否为完全二叉树
可以使用层次遍历的方式来判断二叉树是否为完全二叉树。
具体过程如下:
1. 如果二叉树为空,则返回false。
2. 定义一个标记flag,初始值为false。
3. 对根结点进行层次遍历,如果遍历到某个结点的左右子树都不为空,且flag为true,则返回false;如果遍历到某个结点的左子树为空,或者左右子树都为空,则将flag设置为true;如果遍历到某个结点的左子树不为空,右子树为空,则将flag设置为true,并继续遍历。
4. 如果遍历完整个二叉树,都没有返回false,则说明该二叉树是完全二叉树,返回true。
代码实现如下:
```python
def isCompleteTree(root):
if not root:
return False
flag = False
queue = [root]
while queue:
node = queue.pop(0)
if node.left:
if flag:
return False
queue.append(node.left)
else:
flag = True
if node.right:
if flag:
return False
queue.append(node.right)
else:
flag = True
return True
```
其中,queue用于存储当前层的结点,flag用于标记是否出现了左子树为空或左右子树都为空的情况。如果出现,则后面的结点必须满足左右子树都为空,否则就不是完全二叉树。
阅读全文