二叉树的广度优先遍历和题目

二叉树广度优先遍历利用队列。

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
typedef BTNode* QDataType;
 // 链式结构：表示队列 
typedef struct QueueNode 
{ 
    struct QueueNode* next; 
    QDataType data; 
}QueueNode;
// 队列的结构 两个指针分别记录链表的头和尾
typedef struct Queue 
{ 
	QueueNode* head; 
	QueueNode* tail; 
}Queue;
// 广度优先遍历 1.先把根入队列 2.出队头的数据,把他的下一层入进去
// 特点:借助队列的先进先出性质,上一层出的时候带入下一层 队列的代码参考前面的博客
void LevelOrder(BTNode* root)
{
	 Queue q;
	 QueueInit(&q);
	 if(root)
	 	QueuePush(&q, root);
	 
	 while(!QueueEmpty(&q))
	 {
	 	BTNode* front = QueueFront(&q); 
	 	QueuePop(&q);
	 	printf("%d ",front->left);
	 	if(front->left)
	 		QueuePush(&q, front->left);
	 	if(front->right)
	 		QueuePush(&q, front->right);
	 }
	 QueueDestory(&q);
}
// 判断二叉树是否为完全二叉树 完全二叉树按层序走,节点是连续的,当出到NULL之后后面全是NULL就是完全二叉树,
// 如果后面有非空,那么就不是,说明节点层序走,非空节点不连续
bool BinaryTreeComplete(BTNode* root)
{
	 Queue q;
	 QueueInit(&q);
	 if(root)
	 	QueuePush(&q, root);
	 while(!QueueEmpty(&q))
	 {
	 	BTNode* front = QueueFront(&q);
	 	QueuePop(&q);
	 	if(front == NULL)
	 	{
	 		break;
	 	}
	 	QueuePush(root->left);
	 	QueuePush(root->right)l
	 }
	 while(!QueueEmpty(&q))
	 {
	 	BTNode* front = QueueFront(&q);
	 	QueuePop(&q);
	 	if(front)
	 		return false;
	 }
	 QueueDestory(&q);
	 return true;
}
// 创建节点
BTNode* CreateTreeNode (BTDataType x)
{
	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
	n1->data = x;
	n1->left = NULL;
	n1->right = NULL:
	return node;
}
int main()
{
	// 手动连接上图中的树
	BTNode* A = CreateTreeNode('A');
	BTNode* B = CreateTreeNode('B');
	BTNode* C = CreateTreeNode('C');
	BTNode* D = CreateTreeNode('D');
	BTNode* E = CreateTreeNode('E');
	BTNode* F = CreateTreeNode('F');
	A->left = B;
	A->right = C;
	B->left = D;
	C->left = E;
	c->right = F;
	// 二级做法BinaryTreeDestory(&A);
	// 一级做法
	BinaryTreeDestory(A);
	A = NULL;
}