设二叉树采用二叉链表存储,设计非递归算法判断根结点为T的二叉树是否为完全二叉树。
时间: 2024-02-27 11:58:19 浏览: 82
可以采用层序遍历的方式进行判断。具体算法如下:
1. 从根节点开始,将根节点入队。
2. 如果当前节点有左子树,将左子树入队;如果当前节点没有左子树但有右子树,则该树不是完全二叉树,返回false。
3. 如果当前节点有右子树,将右子树入队。
4. 如果当前节点没有左子树也没有右子树,则该节点之后的所有节点必须都是叶子节点,否则该树不是完全二叉树,返回false。
5. 重复步骤2~4,直到队列为空。
6. 如果程序能够执行到这一步,说明该树是完全二叉树,返回true。
以下是具体的实现代码(假设树的节点结构体为Node,队列结构体为Queue):
```
bool isCompleteTree(Node* T) {
if (T == NULL) return true;
Queue q;
q.push(T);
bool flag = false;
while (!q.empty()) {
Node* cur = q.front();
q.pop();
if (cur->left != NULL) {
if (flag) return false;
q.push(cur->left);
} else {
flag = true;
}
if (cur->right != NULL) {
if (flag) return false;
q.push(cur->right);
} else {
flag = true;
}
}
return true;
}
```
阅读全文