首页 > 代码库 > 判断一棵二叉树是否是完全二叉树

判断一棵二叉树是否是完全二叉树

2024-07-18 10:41:05   222人阅读

题目：判断一棵二叉树是否是完全二叉树
思路：
1.首先明确完全二叉树的概念。完全二叉树除最后一层外，所有层结点数均达到最大值，最后一层结点连续集中在最左边。空树也是完全二叉树。
2.我们可以通过层序遍历的方式遍历这个二叉树，使用一个队列存储遍历的结点。可以利用最后一层的结点集中在左侧这个特性解题，具体看代码：


代码：

bool isCompleteTree(pTree pT)
{
	Queue q;
	initQueue(&q);
	Enqueue(&q,pT);//根入队
	pNode ptr = NULL;
	while((ptr = Dequeue(&q)) != NULL)//不断出队，直到遇到空
	{
		Enqueue(&q,ptr->left);//入队左孩子，空结点也同样入队
		Enqueue(&q,ptr->right);//入队右孩子
	}
	while(!isQueueEmpty(&q))//如果队列非空，那么留在队列中的必然都是NULL结点
	{
		ptr = Dequeue(&q);
		if(ptr != NULL)//如果存在非null结点，说明不是完全二叉树
		{
			return false;
		}
	}
	return true;
}
完整代码：
/*
判断是否是完全二叉树
by Rowandjj
2014/8/19
*/
#include<iostream>
using namespace std;
typedef struct _NODE_
{
	int data;
	struct _NODE_ *left;
	struct _NODE_ *right;
}Node,*pNode,*pTree;
typedef struct _QUEUENODE_
{
	pNode queue_data;
	struct _QUEUENODE_ *next;
}QueueNode,*pQueueNode;
typedef struct _QUEUE_
{
	pQueueNode pHead;
	pQueueNode pTail;
	int size;
}Queue,*pQueue;
void initQueue(pQueue pQ)
{
	pQ->pHead = pQ->pTail = (pQueueNode)malloc(sizeof(QueueNode));
	if(!pQ->pTail)
	{
		exit(-1);
	}
	pQ->pHead->next = NULL;
	pQ->size = 0;
}
void Enqueue(pQueue pQ,pNode data)
{
	if(pQ == NULL)
	{
		return;
	}
	pQueueNode pNew = (pQueueNode)malloc(sizeof(QueueNode));
	if(!pNew)
	{
		exit(-1);
	}
	pNew->queue_data = http://www.mamicode.com/data;>


联系
我们