数据结构详解——堆与二叉树

​

树的概念

树是一种非线性的数据结构，它是由n（n >= 0）个有限结点组成的一个具有层次关系的集合。它看起来像一个倒挂的树。
二叉树最上面的结点被称为根节点，根节点没有前驱结点，也就是根结点之上没有节点。除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。树形结构中的子树之间不能有交集，也就是一个节点不能有两个前驱。树是递归定义的。

树有很多引申出的概念，下面是一些常用的。

树的表示方法

由于树是非线性的数据结构，表示树时，既要保存树的值，又要保存结点之间的关系，有一种非常巧妙的方法叫做左孩子右兄弟表示法，定义一个结构体，里面定义一个指向其第一个孩子的指针，再定义一个指向其兄弟的指针。

typedef int DataType;
struct Node
{
    struct Node* firstChild1;    // 第一个孩子结点
    struct Node* pNextBrother;   // 指向其下一个兄弟结点
    DataType data;               // 结点中的数据域
};

二叉树的概念

二叉树是一种特殊的树，它是结点的一个有限集合，该结点要么为空，要么就是由一个根结点加上两颗分别被称为左子树和右子树的二叉树组成。二叉树不存在度大于2的结点，二叉树的子树有左右之分，因此二叉树是有序树。

特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k -1 ，则它就是满二叉树。

2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点。

2. 若规定根结点的层数为1，则深度为h的二叉树的最大结点数是2^h-1。

3. 对任何一棵二叉树, 如果度为0其叶结n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1，如何去理解这句话呢，其实很简单，在二叉树最开始只有一个根节点时，度为0的就有1个，度为2的有0个，每增加一个度为1的就会消灭一个度为0的，产生一个度为1的和一个度为0的，度为0的数目不会变，也因此度为1的结点数我们无法求得，而每增加一个度为2的，就会消灭一个度为0的，增加一个度为2的和两个度为0的，一前一后相抵消的话相当于度为0的因为度为2的加一自己也加了一。于是乎度为0的永远比度为2的大1。

4. 若规定根结点的层数为1，具有n个结点的满二叉树的深度，h=log_2(n+1)。 (log_2(n+1)是log以2为底，n+1的对数)

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0开始编号，则对于序号为i的结点有：

（1）若i>0，i位置结点的双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点

（2） 若i>0，i位置的左孩子节点为：2i+1，右孩子结点为：2i+2。

（3）高度为h的完全二叉树，节点数量范围为[2^(h-1), 2^h-1]。

二叉树的存储结构

顺序存储

顺序存储就是利用数组来存储，这种存储方式只适用于完全二叉树，普通二叉树会有空间上的浪费，毕竟既然使用数组了，数与数之间必然就要有强逻辑，只有完全二叉树这种父结点与孩子结点都可一一对应的这种才合适，普通的就要将空出的结点的空间浪费。使用数组表示完全二叉树的这种数据结构我们称为堆（Heap）。

链式存储

链式存储就是利用来链来存储，也就是使用指针，使用指针的话就相对好处理很多，对于二叉链来说，链表中的每个节结点都由三个变量组成，数据和左右指针。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
	struct BinTreeNode* left;   // 指向当前结点左孩子
	struct BinTreeNode* right;  // 指向当前结点右孩子
	BTDataType data;            // 当前结点值域
};

堆的概念与结构

如果有一个关键码的集合K = {0，1， 2，…，n-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：i<= 2i+1 且 i<= 2i+2(i >= 2i+1 且 i>= 2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

堆的性质

堆中某个结点的值总是不大于或不小于其父结点的值

堆总是一棵完全二叉树。

堆的实现

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

#include<stdlib.h>

#include<assert.h>

#include<errno.h>

#include<string.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;
//堆的创建
void HeapInit(Heap* php);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
//扩容
void Expansion(Heap* hp);
//交换
void swap(int* a, int* b);
//向上交换
void raise(HPDataType* a, int n);
//向下交换
void down(HPDataType* a, int n);

定义了一个结构体用来保存堆的头指针，堆的尺寸和堆的存储元素数量

#include"heap.h"

void HeapInit(Heap* php)
{
	assert(php);
	Heap* ptr = (HPDataType*)calloc(8, sizeof(HPDataType));
	if (ptr == NULL)
	{
		perror("HeapInit:calloc");
		return;
	}
	php->_a = ptr;
	php->_capacity = 8;
	php->_size = 0;
}

void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = 0;
	hp->_size = 0;
}

void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	Expansion(hp);
	hp->_a[hp->_size] = x;
	++hp->_size;
	raise(hp->_a,hp->_size);
}

void raise(HPDataType* a, int n)//向上调整算法
{
	int child = n;
	int parents = child / 2;
	while (child > 1)
	{
		if (a[child - 1] > a[parents - 1])
		{
			swap(&(a[child - 1]), &(a[parents - 1]));
			child = parents;
			parents = child / 2;
		}
		else
		{
			break;
		}
	}
}

void Expansion(Heap* hp)
{
	assert(hp);
	if (hp->_capacity == hp->_size)
	{
		Heap* ptr = (Heap*)realloc(hp->_a, sizeof(HPDataType) * hp->_capacity * 2);
		if (ptr == NULL)
		{
			perror("Expansion:realloc");
			return;
		}
		hp->_a = ptr;
		hp->_capacity *= 2;
	}
}

void HeapPop(Heap* hp)
{
	assert(hp && hp->_size);
	swap(hp->_a, &(hp->_a[hp->_size - 1]));
	--hp->_size;
	down(hp->_a, hp->_size);
}

void down(HPDataType* a, int n)//向下调整算法
{
	int parents = 1;
	int child = parents * 2;
	while (child <= n)
	{
		if (child + 1 <= n && a[child - 1] < a[child])
		{
			++child;
		}
		if (a[child - 1] > a[parents - 1])
		{
			swap(&(a[child - 1]), &(a[parents - 1]));
			parents = child;
			child = parents * 2;
		}
		else
		{
			break;
		}
	}
}

void swap(int* a, int* b)//交换算法
{
	int ex = *a;
	*a = *b;
	*b = ex;
}

int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}

int HeapEmpty(Heap* hp)
{
	assert(hp);
	if (hp->_size == 0)
	{
		return 0;
	}
	return 1;
}

HPDataType HeapTop(Heap* hp)
{
	assert(hp && HeapEmpty(hp));
	return hp->_a[0];
}

堆的初始化

void HeapInit(Heap* php)
{
	assert(php);
	Heap* ptr = (HPDataType*)calloc(8, sizeof(HPDataType));
	if (ptr == NULL)
	{
		perror("HeapInit:calloc");
		return;
	}
	php->_a = ptr;
	php->_capacity = 8;
	php->_size = 0;
}

由于堆是一个数组，为了充分的利用空间，我采用动态数组的方式，对于传入的堆指针，calloc动态开辟内存，检验之后设置好头指针，尺寸和元素数量就行了。

入堆

void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	Expansion(hp);
	hp->_a[hp->_size] = x;
	++hp->_size;
	raise(hp->_a,hp->_size);
}

对于进入的元素，首先用扩容函数进行扩容，之后将其插入到队尾，再将存储的元素数++，之后进入排序函数对插入后的堆进行排序。

堆的扩容

void Expansion(Heap* hp)
{
	assert(hp);
	if (hp->_capacity == hp->_size)
	{
		Heap* ptr = (Heap*)realloc(hp->_a, sizeof(HPDataType) * hp->_capacity * 2);
		if (ptr == NULL)
		{
			perror("Expansion:realloc");
			return;
		}
		hp->_a = ptr;
		hp->_capacity *= 2;
	}
}

常规的动态数组的扩容方式。

向上调整算法

void raise(HPDataType* a, int n)//向上调整算法
{
	int child = n;
	int parents = child / 2;
	while (child > 1)
	{
		if (a[child - 1] > a[parents - 1])
		{
			swap(&(a[child - 1]), &(a[parents - 1]));
			child = parents;
			parents = child / 2;
		}
		else
		{
			break;
		}
	}
}

对于之前的入堆函数，我将数据插入到队尾，这时要对堆进行排序，就要用到向上调整函数，其原理就要利用到堆的性质，即父节点要比子节点大（大堆）或者小（小堆），对于插入到堆的尾部的元素，我们就是要一步一步地找到其对应的父节点，与之比较，如果父节点比他大（大堆）或比他小（小堆），就交换两个数，直到父节点比他小（大堆）或者大（小堆）为止，我们就完成了排序。对于具体的实现方法，首先我们需要明白的是，堆的理想样式与数组是有一些出入的，对于堆，我们会让其从1开始计数，而数组是从0开始计数的，这两种计数方式计算父子结点的方式不同。对于从1开始的堆，父节点 = 子节点 / 2，子节点1 = 父节点 * 2 ，子节点2 = 父节点 * 2 + 1。对于从0开始的堆，父节点 = （子节点 - 1） / 2，子节点1 = 父节点 * 2 + 1 ，子节点2 = 父节点 * 2 + 2。所以在排序时我们要注意到这一点，我这里采用的是将父节点和子节点按一般堆的表示方式即从1开始计数，在数组计算时将其减一表示正确的位置，其实也可以在一开始就按从0开始计算，这样就不用减一了，按习惯来。引入两个新变量后，将child表示为新入堆元素的位置，parents表示为child的父节点，，之后用while循环反复执行检验父子节点并交换的操作，当插入元素来到根结点或者找到比它大（大堆）或者小（小堆）时就停止。

出堆（最顶端元素）

void HeapPop(Heap* hp)
{
	assert(hp && hp->_size);
	swap(hp->_a, &(hp->_a[hp->_size - 1]));
	--hp->_size;
	down(hp->_a, hp->_size);
}

删除堆中最顶端的元素，也就是根结点，这其实是有点麻烦的，对于堆来说，删除其末端的元素，其实是最为简单的，下一次存入时覆盖就行，他不会破坏整体的排序。而对于顶端，如果用一般的处理方式，贸然用memmove函数或循环等方法将后面的元素向前移动来覆盖是不行的，堆中的数据排序有着强逻辑，整体移动这么多元素会破坏这种关系，所以我先将顶段元素与末端元素交换，将size–，之后我们用向下调整算法对其进行排序，完成顶端元素的删除。

向下调整算法

void down(HPDataType* a, int n)//向下调整算法
{
	int parents = 1;
	int child = parents * 2;
	while (child <= n)
	{
		if (child + 1 <= n && a[child - 1] < a[child])
		{
			++child;
		}
		if (a[child - 1] > a[parents - 1])
		{
			swap(&(a[child - 1]), &(a[parents - 1]));
			parents = child;
			child = parents * 2;
		}
		else
		{
			break;
		}
	}
}

对于出堆（顶端元素）函数中，我们需要用到向下调整函数，在入堆操作中，我使用向上调整算法，将入堆元素与其父节点进行比较，向上交换。向下调整函数与之相反，交换首尾元素后，将顶端元素（根结点）与其子节点进行比较，如果比其小（大堆）或者大（小堆）就交换，直到比子节点大（大堆）或者小（小堆）或者超出堆的元素数量为止。具体的实现方式与向上调整方式类似，有一点需要特别注意，在向上调整算法中，元素只需要找到其父节点就行，父节点就一个，而在向下调整算法中，与之比较的子节点有两个，那我们就要保证与其比较的是最大（大堆）或者最小（小堆），所以在正式进行父子结点比较时，还要加一个if语句选出最大的子节点，与此同时也要时刻注意堆的越界情况，child和child+1都要<=n。

二叉树的实现

#include "queue.h"

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<assert.h>

#include<errno.h>

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

#include"BinaryTree.h"



BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
	if (a[(*pi)] == '#' || !a)
	{
		++(*pi);
		return NULL;
	}
	BTNode* newnode = (BTNode*)calloc(1, sizeof(BTNode));
	newnode->_data = a[(*pi)++];
	newnode->_left = BinaryTreeCreate(a, pi);
	newnode->_right = BinaryTreeCreate(a, pi);
	return newnode;
}

void BinaryTreeDestory(BTNode** root)
{
	if (!*root)
		return;
	BinaryTreeDestory(&((*root)->_left));
	BinaryTreeDestory(&((*root)->_right));
	free(*root);
	*root = NULL;
}

int BinaryTreeSize(BTNode* root)
{
	if (!root)
		return 0;
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (!root)
		return 0;
	if (!root->_left && !root->_right)
		return 1;
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	--k;
	if (!root)
	{
		return 0;
	}
	if (k == 0)
		return 1;
	return BinaryTreeLevelKSize(root->_left, k) + BinaryTreeLevelKSize(root->_right, k);
}

//int BTLKSize(BTNode* root, int* k)
//{
//	--*k;
//	if (*k == 0)
//		return 1;
//	int ck = *k;
//	return BTLKSize(root->_left, &ck) + BTLKSize(root->_right, k);
//}
 
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (!root)
		return NULL;
	if (root->_data == x)
		return root;
	BTNode* left = BinaryTreeFind(root->_left, x);
	if (left)
		return left;
	return BinaryTreeFind(root->_right, x);
}

void BinaryTreePrevOrder(BTNode* root)//前
{
	if (!root)
	{
		printf("# ");
		return;
	}
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

void BinaryTreeInOrder(BTNode* root)//中
{
	if (!root)
	{
		printf("# ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);
}

void BinaryTreePostOrder(BTNode* root)//后
{
	if (!root)
	{
		printf("# ");
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c ", root->_data);
}

void BinaryTreeLevelOrder(BTNode* root)
{
	if (!root)
		return;
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* curr = QueueFront(&q);
		printf("%c ", curr->_data);
		QueuePop(&q);
		if(curr->_left)
			QueuePush(&q, curr->_left);
		if(curr->_right)
			QueuePush(&q, curr->_right);
	}
	QueueDestory(&q);
}

int BinaryTreeComplete(BTNode* root)
{
	Queue qu;
	BTNode* cur;
	int tag = 0;
	QueueInit(&qu);
	QueuePush(&qu, root);
	while (!QueueIsEmpty(&qu))
	{
		cur = QueueTop(&qu);
		putchar(cur->_data);
		if (cur->_right && !cur->_left)
			return 0;
		if (tag && (cur->_right || cur->_left))
			return 0;
		if (cur->_left)
			QueuePush(&qu, cur->_left);
		if (cur->_right)
			QueuePush(&qu, cur->_right);
		else
			tag = 1;
		QueuePop(&qu);
	}
	QueueDestory(&qu);
	return 1;
}

二叉树的创建

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
	if (a[(*pi)] == '#' || !a)
	{
		++(*pi);
		return NULL;
	}
	BTNode* newnode = (BTNode*)calloc(1, sizeof(BTNode));
	newnode->_data = a[(*pi)++];
	newnode->_left = BinaryTreeCreate(a, pi);
	newnode->_right = BinaryTreeCreate(a, pi);
	return newnode;
}

在二叉树的实现过程中需要时刻用到两路归并的思想，也就是分成两路的递归，传入的参数是字符串数组和计数用的整形指针，他在初始时解引用的值为0，以此来计数。对于递归函数，其开头当然是写递归的结束条件，当数组为字符’#‘或’\0’时结束递归（'#'表示空结点），返回NULL。之后就是创建结点，给结点赋值，之后引用函数本身给左右子节点地址赋值以此形成递归。

二叉树的销毁

void BinaryTreeDestory(BTNode** root)
{
	if (!*root)
		return;
	BinaryTreeDestory(&((*root)->_left));
	BinaryTreeDestory(&((*root)->_right));
	free(*root);
	*root = NULL;
}

对于二叉树的销毁，传参有两种形式，一种是传根节点的指针，一种是传根节点的二级指针，这两者的区别是传二级指针的话可以在函数内就完成指针free后的置空，而传一级指针就不行，需要手动置空，我这里用的是二级指针，用二级指针的话就要注意解引用。这个函数也是一个二路归并函数，先判断递归结束的条件（指针为空），引用自己对左右指针进行销毁，注意先要引用自己销毁左右指针，再销毁自己，先销毁自己的话就i丢失了左右指针的地址了。

二叉树的元素数

int BinaryTreeSize(BTNode* root)
{
	if (!root)
		return 0;
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

二叉树没法像堆一样直接得出元素的数量，需要遍历求和才行，这里我同样采用二路归并，先给出递归结束的条件，返回0，之后再return语句中引用自己求和就行。

二叉树的叶子节点数

int BinaryTreeLeafSize(BTNode* root)
{
	if (!root)
		return 0;
	if (!root->_left && !root->_right)
		return 1;
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

叶子节点就是没有子节点的结点，同样的，递归先给出递归结束的条件，这里有两种情况，一种是遇到了左右子节点都为空节点的叶子节点返回1，一种是遇到了空节点返回0，这里有人会疑惑为什么判断为叶子节点就返回了为什么还会遇到空结点，这是因为会有一个子节点为空另一个子节点正常的情况。之后我们同样利用return语句计算总数。

二叉树第k层结点个数

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	--k;
	if (!root)
	{
		return 0;
	}
	if (k == 0)
		return 1;
	return BinaryTreeLevelKSize(root->_left, k) + BinaryTreeLevelKSize(root->_right, k);
}

我们计算二叉树第k层结点个数的原理就是每访问一层就将k–，当k减为0就到达了k层，此时如果不为空结点就返回1。 首先为了避免k值过大出现非法访问的情况，设置一个遇到空结点return 0的if语句，之后设置递归结束的条件，即k值减为0时返回1。

二叉树中寻找值为x的结点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (!root)
		return NULL;
	if (root->_data == x)
		return root;
	BTNode* left = BinaryTreeFind(root->_left, x);
	if (left)
		return left;
	return BinaryTreeFind(root->_right, x);
}

同样的，先给出递归结束的条件，当结点为空时返回NULL，当结点为要找的数时返回结点地址，之后我们先引用自己对左子树进行寻找，返回结果赋值给left，if语句判断left不为空就返回left，不是就返回引用自己对右子树的寻找结果，因为已经找完了左子树了，右子树就算没找到也是返回NULL，所以直接返回右子树的结果就行。

二叉树的前中后序遍历

void BinaryTreePrevOrder(BTNode* root)//前
{
	if (!root)
	{
		printf("# ");
		return;
	}
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

void BinaryTreeInOrder(BTNode* root)//中
{
	if (!root)
	{
		printf("# ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);
}

void BinaryTreePostOrder(BTNode* root)//后
{
	if (!root)
	{
		printf("# ");
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c ", root->_data);
}

所谓前中后序遍历，就是对父结点，左子树，右子树的访问顺序，前序遍历就是先访问根结点，再从左至右访问左右子树，中序遍历就是根结点在中间，左子树在左，右子树在右，后序遍历就是先从左至右访问左右子树，最后再访问根结点。前中后序遍历的实现很简单，理解了之前的二路归并就很容易实现。

二叉树的层序遍历

void BinaryTreeLevelOrder(BTNode* root)
{
	if (!root)
		return;
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* curr = QueueFront(&q);
		printf("%c ", curr->_data);
		QueuePop(&q);
		if(curr->_left)
			QueuePush(&q, curr->_left);
		if(curr->_right)
			QueuePush(&q, curr->_right);
	}
}

层序遍历顾名思义就是就是按照层的顺序逐层遍历二叉树，这相比较于二叉树的前中后序遍历要麻烦得多，因为二叉树只层与层之间有链接，同层元素之间的并没有强联系。这里有一种巧妙的方法，那就是用队列来实现。先引入队列的数据结构，我引入了我之前完成的队列。先将二叉树的根结点入队列，然后根据队列先进先出的特点，每出一个元素就在队列尾部按从左到右插入左右子节点，如此往复，知道队列为空，如此就完成了二叉树的层序遍历。下面是图解。

判断二叉树是否为完全二叉树

int BinaryTreeComplete(BTNode* root)
{
	Queue qu;
	BTNode* cur;
	int tag = 0;
	QueueInit(&qu);
	QueuePush(&qu, root);
	while (!QueueIsEmpty(&qu))
	{
		cur = QueueTop(&qu);
		putchar(cur->_data);
		if (cur->_right && !cur->_left)
			return 0;
		if (tag && (cur->_right || cur->_left))
			return 0;
		if (cur->_left)
			QueuePush(&qu, cur->_left);
		if (cur->_right)
			QueuePush(&qu, cur->_right);
		else
			tag = 1;
		QueuePop(&qu);
	}
	QueueDestory(&qu);
	return 1;
}

根据完全二叉树的定义，我们明白完全二叉树直到结束为止到要排满的二叉树，对于如何检验，我们首先要明白在这种情况下使用队列来遍历是一个很好的选择，因为队列是层序遍历，完全二叉的检验也是按层序检验有没有缺子节点，之后要明确何种情况下才能判断其不是完全二叉树，一种是出现左节点为空时，完全二叉要么左右节点都为空，要么只有右为空，所以左为空一定不是完全二叉；再者就是右为空的情况，但我们明白右为空本身并不一定就不是完全二叉，但右为空一定意味着完全二叉已经到了末尾，之后如果出现不为空的节点，就一定能判断其不是完全二叉了，我使用了一个tag变量来记录，将其初始化为0，第一次遇到右为0时将其赋值为1，之后当tag为1且左右子节点有一个不为空时就可以认定其不为完全二叉树了。

​