当前位置：首页 > news >正文

数据结构--二叉树相关习题5（判断二叉树是否是完全二叉树）

news 来源：原创 2024/9/20 11:43:50

1.判断二叉树是否是完全二叉树

辨别：

不能使用递归或者算节点个数和高度来判断。

满二叉树可以用高度和节点来判断，因为是完整的。

但是完全二叉树前面是满的，但是最后一层是从左到右连续这种

如果仍然用这种方法的话，如下图两个识别方法是一样的，但是无法准确识别

完全二叉树：前h-1层是满的，最后一层是从左到右连续。

如果走层序那么一定是连续的，也就是说要通过层序遍历来走。

思路：1.层序遍历走，空也进序列。

2.遇到第一个空时开始判断，如果后面都为空则是完全二叉树，若空后面还出席那非空的情况则说明不是完全二叉树。

代码实现：

//判断二叉树是否是完全二叉树
bool TreeComplete(BTNode* root)
{ Queue q;//仍然使用队列去实现QueueInit(&q);if (root)QueuePush(&q,root)while (!QueueEmpty){BTNode* front = QueueFront(&q);QueuePop(&q);//遇到第一个空就可以开始判断，如果队列中还有非空，就不是完全二叉树。if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}while (!QueueEmpty){BTNode* front = QueueFront(&q);QueuePop(&q);//如果仍有非空元素，直接
//		return false;if (front){QueueDestroy(&q);//如果存在非空。return false;}QueueDestroy(&q);return true;
//最终QueueDestroy，再返回}
}

补充队列的一系列实现

void QueueInit(Queue* pq)
{assert(pq);pq->phead =  NULL;pq->ptail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}// 队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);/*QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;if (pq->phead == NULL)pq->ptail = NULL;*/// 一个节点if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else // 多个节点{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}