用Python代码判断一棵树是否为完全二叉树。
时间: 2023-06-07 10:08:21 浏览: 137
python 平衡二叉树实现代码示例
可以使用层次遍历方法对二叉树进行遍历,在遍历的过程中,对于每一个节点,记录它的编号。对于编号为i的节点,如果它有左孩子,那么左孩子的编号就是2*i,如果它有右孩子,那么右孩子的编号就是2*i+1。如果一个节点的编号不是2*i或2*i+1,那么它就不是完全二叉树。以下是Python代码:
```
def isCompleteBinaryTree(root):
if not root:
return True
queue = [(root, 1)]
count = 1
while queue:
node, num = queue.pop(0)
if num != count:
return False
count += 1
if node.left:
queue.append((node.left, 2*num))
if node.right:
queue.append((node.right, 2*num+1))
return True
```
在这段代码中,queue中存储每个节点以及它的编号,count表示当前处理到的节点的编号。对于每个节点,将它的左孩子和右孩子加入到queue中。当queue为空时,遍历结束,如果遍历到的节点编号不连续,那么它就不是完全二叉树。
阅读全文