두 갈래 나무 한 그루가 완전 두 갈래 나무인지 아닌지를 판단하다

제목: 두 갈래 나무 한 그루가 완전 두 갈래 나무인지 아닌지 판단
아이디어:
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 = data;
	pNew->next = NULL;
	pQ->pTail->next = pNew;
	pQ->pTail = pNew;
	pQ->size++;
}
pNode Dequeue(pQueue pQ)
{
	if(pQ == NULL)
	{
		return NULL;
	}
	pQueueNode pDel = pQ->pHead->next;
	if(pDel == NULL)
	{
		return NULL;
	}else
	{
		pNode result = pDel->queue_data;
		if(pQ->pTail == pDel)
		{
			pQ->pTail = pQ->pHead;
		}
		pQ->pHead->next = pDel->next;
		pQ->size--;
		free(pDel);
		return result;
	}
}
bool isQueueEmpty(pQueue pQ)
{
	return pQ->size == 0;
}
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))
	{
		ptr = Dequeue(&q);
		if(ptr != NULL)
		{
			return false;
		}
	}
	return true;
}
void createTree(pTree *pRoot)
{
	int data;
	cin>>data;
	if(data == -1)
	{
		return;
	}
	*pRoot = (pNode)malloc(sizeof(Node));
	if(*pRoot == NULL)
	{
		exit(-1);
	}
	(*pRoot)->data = data;
	(*pRoot)->left = NULL;
	(*pRoot)->right = NULL;
	createTree(&(*pRoot)->left);
	createTree(&(*pRoot)->right);
}
void displayTree(pTree pT)
{
	if(pT == NULL)
	{
		return;
	}
	cout<<pT->data<<" ";
	if(pT->left)
	{
		displayTree(pT->left);
	}
	if(pT->right)
	{
		displayTree(pT->right);
	}
}
int main()
{
	pTree p = NULL;
	createTree(&p);
	cout<<isCompleteTree(p)<<endl;
	displayTree(p);
	cout<<endl;
	return 0;
}