数据结构之《二叉树》(下)

在二叉树(中)了解了堆的相关概念后还实现了堆，并且还实现了堆排序，以及解决了TOP-K问题。接下来在本篇中将继续学习二叉树中的链式结构，会学习二叉树中的前、中、后三种遍历并实现链式结构的二叉树，接下来就开始本篇的学习吧！
 

1.链式二叉树的结构

要实现链式结构的二叉树，首先就要将二叉树的结构设计好，也就是要将二叉树结点的结构设计好；要将各结点关联起来通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 ，其结构如下：

typedef int BTDataType;
// 二叉树链式结构
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType val;

}BTNode;

在实现链式结构的二叉树的程序中是将程序的文件分为以下三个文件

2.二叉树的创建

由于在实现链式结构的二叉树中不同于堆一样都是完全二叉树，因此这就使得二叉树的结构较为多样，这时我们就不再去像前面顺序结构的二叉树一样实现插入删除等功能，直接手动的创建一个二叉树，该函数的返回值就为二叉树的根结点

BTNode* CreateTree()
{
	BTNode* node1 = NewNode(1);
	BTNode* node2 = NewNode(2);
	BTNode* node3 = NewNode(3);
	BTNode* node4 = NewNode(4);
	BTNode* node5 = NewNode(5);

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	return node1;
}

3. 前中后序遍历

在实现了链式二叉树的结构后接下来就可以来实现二叉树的前中后序遍历，在此之前先来了解前中后序遍历的概念

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
（1）前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发生在遍历其左右树之前

访问顺序为：根结点、左子树、右子树
（2）中序遍历(Inorder Traversal)：访问根结点的操作发生在遍历其左右子树之中（间）
访问顺序为：左子树、根结点、右子树
（3）后序遍历(Postorder Traversal)：访问根结点的操作发生在遍历其左右子树之后
访问顺序为：左子树、右子树、根结点

来通过以下的二叉树示例来进一步理解以上的遍历规则
前序遍历： 
在以上图示的二叉树中，若要进行前序遍历则先要访问跟结点A，之后再访问A的左结点B，之后访问B的左结点D，再访问D的左节点再访问D的右结点，因为D的左节点和右结点都为NULL所以返回去访问B的右结点，因为B的右结点为NULL所以返回去访问A的右结点C，之后访问C的左结点E，再访问E的左节点再访问E的右结点，因为E的左节点和右结点都为NULL所以返回去访问F结点

因此通过以上分析就可以得出前序遍历结果为： A  B  D  C  E  F

中序遍历:
在以上图示的二叉树中，若要进行中序遍历则先要访问跟结点D的左结点，但因为D的左右结点都为NULL，所以先访问结点D，之后访问D的跟结点B，因为B的右结点为NULL,再访问B的跟结点A，之后因为E的左右结点都为NULL，所以先访问结点E，再访问E的跟节点C，之后访问C的右结点F

 因此通过以上分析就可以得出中序遍历结果为：D  B  A  E  C  F

后序遍历:
在以上图示的二叉树中，若要进行后序遍历则先要访问跟结点D的左结点，但因为D的左结点为NULL，之后再访问D的右结点，但因为D的右结点为NULL所以先访问结点D，之后访问B的右结点，但因为B的右结点为NULL，所以之后访问结点B,之后因为E的左右结点都为NULL，所以先访问结点E，之后再访问C的右节点F，再访问节点C，最后再访问C的跟结点A

因此通过以上分析就可以得出中序遍历结果为：D  B  E  F  C  A

完成了以上二叉树的示例的分析接下来我们就来试着实现前中后序遍历的代码

3.1前序遍历

先是在Tree.h文件内完成前序遍历函数的声明

//前序遍历
void PreOrder(BTNode* root);

将该函数命名为PreOrder，函数的参数是指向二叉树结点的结构体指针

之后就是在Tree.c内完成函数的定义

以下前序遍历函数是一个递归函数，递归的结束的结束条件是当访问的结点值为NULL时
使用printf将结点内的值打印出

//前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}

图解遍历

我们来通过以下示例将前序遍历的的递归过程完整的展示一遍

以下就是该二叉树在前序遍历函数中的函数递归栈帧图，在这当中红色的线表示递推过程，绿色的线表示回归的过程 

 3.2中序遍历

先是在Tree.h文件内完成中序遍历函数的声明

//中序遍历
void InOrder(BTNode* root);

将该函数命名为InOrder，函数的参数是指向二叉树结点的结构体指针

之后就是在Tree.c内完成函数的定义
以下中序遍历函数是一个递归函数，递归的结束的结束条件是当访问的结点值为NULL时
使用printf将结点内的值打印出

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

图解遍历

我们来通过以下示例将中序遍历的的递归过程完整的展示一遍

以下就是该二叉树在中序遍历函数中的函数递归栈帧图，在这当中红色的线表示递推过程，绿色的线表示回归的过程 

3.3后序遍历 

先是在Tree.h文件内完成后序遍历函数的声明

//后序遍历
void PostOrder(BTNode* root);

将该函数命名为PostOrder，函数的参数是指向二叉树结点的结构体指针

之后就是在Tree.c内完成函数的定义
以下后序遍历函数是一个递归函数，递归的结束的结束条件是当访问的结点值为NULL时
使用printf将结点内的值打印出

//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

图解遍历

我们来通过以下示例将后序遍历的的递归过程完整的展示一遍

以下就是该二叉树在后序遍历函数中的函数递归栈帧图，在这当中红色的线表示递推过程，绿色的线表示回归的过程 

4.结点个数以及高度等

在实现了链式二叉树的结构和前中后序遍历后接下来我们来试着实现一些求二叉树结点，层次等的函数

4.1二叉树结点个数

先是在Tree.h文件内完成二叉树结点个数函数的声明

// 二叉树结点个数
int BinaryTreeSize(BTNode* root);

 将该函数命名为BinaryTreeSize,函数的参数是指向二叉树结点的结构体指针

之后就是在Tree.c内完成函数的定义

在求二叉树的函数中你可能会想到用一个变量size来作结点个数的计数变量，那么我们就试着使用这种方法来实现二叉树结点个数的个数

int BinaryTreeLeafSize(BTNode* root,int size)
{
	if (root == 0)
	{
		return 0;
	}
	size++;
	BinaryTreeLeafSize(root->left,size) ;
	BinaryTreeLeafSize(root->right,size);
    return size;
}

以上就是按照这种想法来实现的函数，但其实以上的函数是存在非常明显的问题的，你能观察出问题吗？

问题就是以上的函数使用传size的值这就会让函数在递归过程中在各个函数栈帧中size的改变不会影响到其兄弟结点的size值，因此就需要对以上函数做出改变

int BinaryTreeLeafSize(BTNode* root,int* psize)
{
	if (root == 0)
	{
		return 0;
	}
	(*psize)++;
	BinaryTreeLeafSize(root->left,psize) ;
	BinaryTreeLeafSize(root->right,psize);
    return *psize;
}

以上就是改变后的函数，将计数的变量size传值改为传址，这样就可以让每个函数栈帧内*psize的改变影响到其兄弟结点的函数栈帧。

但以上这种算法需要在调用函数前创建一个用于计数的变量，而且在每次调用完函数BinaryTreeLeafSize后还需要将用于计数的变量重新赋值为0，否则就会使得下一次调用函数得到的结点个数还会包含上一次调用函数得到的结点个数，因此这种算法是不太好的，我们需要在思考其他的算法

以下就是就是不使用计数的方法来实现的函数，是将二叉树的结点直接返回
函数递归的结束条件就是当结点为NULL时

// 二叉树结点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

以上函数在以下示例中就会如下形式递归

4.2 二叉树叶子结点个数 

要实现求二叉树中的叶子结点个数函数首先来复习一下什么是叶子结点

我们知道度为0的结点称为叶结点，叶子结点的特征就是无孩子结点也就是其链式结构当中结点内两个指针都指向NULL，例如在以下示例的叶子节点就是结点3、结点5、结点6

复习了叶子结点的概念接下来就可以来实现函数代码了
 

先是在Tree.h文件内完成二叉树叶子结点个数函数的声明

// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);

 将该函数命名为BinaryTreeLeafSize,函数的参数是指向二叉树结点的结构体指针

之后就是在Tree.c内完成函数的定义 

以下函数也是通过函数递归的方式来实现的，递归的结束条件是当结点为NULL时，此时就返回0
当结点的左孩子和右孩子都为NULL就返回1

// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right==NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);

}

4.3二叉树第k层结点个数 

首先先来通过一个示例来复习第k层节点数的概念，例如以下示例二叉树中第三层节点数就为3

 要实现函数先是在Tree.h文件内完成二叉树第k层结点个数函数的声明

// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);

 将该函数命名为BinaryTreeLeafSize,函数的参数有两个，第一个是指向二叉树结点的结构体指针，第二个是想要得到的二叉树节点数的层序号

之后就是在Tree.c内完成函数的定义 
以下函数也是通过函数递归的方式来实现的，递归的结束条件是当结点为NULL时，此时就返回0
在函数中当调用该函数时k值都减1，当k值为1是就表明该1结点是在第k层就返回1

// 二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLevelKSize(root->right,k-1);
}

4.4二叉树的深度/高度 

在实现二叉树的高度/深度函数前先来复习一下高度/深度的概念，树的高度或深度就表示树中结点的最大层次

例如以下示例二叉树中深度就为3

 要实现函数先是在Tree.h文件内完成二叉树的深度函数的声明

//⼆叉树的深度/高度
int BinaryTreeDepth(BTNode* root);

将该函数命名为BinaryTreeDepth,函数的参数是指向二叉树结点的结构体指针

之后就是在Tree.c内完成函数的定义 
在二叉树中的深度就为左子树的深度或者右子树的深度再加上1，在这当中取左右子树中深度大的一边，以下代码中使用三目操作符 ？：来实现

//⼆叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int L = BinaryTreeDepth(root->left);
	int R = BinaryTreeDepth(root->right);

	return L> R ? 1 + L : 1 +R;
}

4.5二叉树查找值为x的结点 

先是在Tree.h文件内完成查找值为x的结点函数的声明

// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

将该函数命名为BinaryTreeFind，函数的参数有两个，第一个是指向二叉树结点的结构体指针，第二个是要查找的数据

之后就是在Tree.c内完成函数的定义 
在以下函数中如果找到了值为x的结点也就是当root->val等于x时就返回这个结点的指针，并且在函数在左子树中找到就不会再去右结点中查找

// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == x)
	{
		return root;
	}
	BTNode* tmp1=BinaryTreeFind(root->left,x);
	if (tmp1 != NULL)
	{
		return tmp1;
	}

	BTNode*tmp2=BinaryTreeFind(root->right, x);
	if (tmp2 != NULL)
	{
		return tmp2;
	}
	return NULL;
}

4.6二叉树的销毁 

先是在Tree.h文件内完成二叉树的销毁函数的声明

// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);

将该函数命名为BinaryDestory，函数的的参数为指向结点的结构体指针的地址
由于要在释放结点空间后将指针置为NULL，因此函数的参数为二级指针，这样就可以使得形参的改变影响实参，不用再手动置指针为NULL

之后就是在Tree.c内完成函数的定义 
在此函数中是使用后序遍历的方式使得能找到结点的孩子结点，在此之后再释放结点

// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));

	free(*root);
	*root = NULL;
}

5.层序遍历 

在本篇开始我们实现了前中后序遍历，接下来我们接着来实现层序遍历，先来了解层序遍历的概念
 

设二叉树的根结点所在层数为1，层序遍历就是从所在二叉树的根结点出发，首先访问第⼀层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历 

在层序遍历中由于要将二叉树中的结点按照层序来遍历，这就使得我们不能再像之前的遍历一样使用函数递归的方法来实现，这时就要再思考其他的方法

在此我们实现层序遍历需要额外借助数据结构：队列 

在此使用队列是来完成以下操作：
先将二叉树中的根结点入队列，之后读取对头元素后出队列，若结点的左、右孩子结点存在，就将孩子结点入队列，之后重复以上操作直到队列为空

注：在实现层序遍历的代码前先要将之前实现的队列文件Queue.c和Queue.h添加到程序当中

 并且要将之前的队列当中定义队列的结构的结构体中的数据类型改为指针类型BinaryTreeNode*

//队列结构的定义
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
	QDataType data;//节点内的数据
	struct QueueNode* next;//指向下一个节点的指针

}QueueNode;

完成以上操作就可以来实现层序遍历的代码了

//层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//将二叉树根节点入队
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头
		BTNode* tmp=QueueFront(&q);
		printf("%d ", tmp->val);
		//出队
		QueuePop(&q);
		if (tmp->left)
		{
			QueuePush(&q, tmp->left);
		}
		if (tmp->right)
		{
			QueuePush(&q, tmp->right);
		}
	}
	QueueDestory(&q);//销毁队列

}

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

之前我们了解了完全二叉树相关的概念和性质，那么如果要写一个函数来判断是否为完全二叉树该如何来实现呢？

 接下来就来看看完全二叉树和非完全二叉树层序遍历的有什么不同，来看以下示例

以上为非完全二叉树，层序遍历结果为A B C D NULL E F NULL NULL NULL NULL NULL NULL 

而在以上完全二叉树中，层序遍历结果就为A B C D F E NULL NULL NULL NULL NULL NULL NULL

通过以上两个二叉树的示例就可以得出如果一个二叉树是完全二叉树则在层序遍历时当遍历到NULL时二叉树二叉树所有有效结点都已经遍历完，而如果是非完全二叉树就会在层序遍历中遍历到NULL后二叉树可能还有有效结点没有遍

接下来就来实现判断是否是完全二叉树的代码，以下函数和层序遍历一样也是用到队列，但和层序遍历中有所不同，无论结点的孩子结点为不为空都入队列。当取出的队头元素为NULL时就跳出第一个while循环，之后的while循环用来判断队列剩下的是否还有有效元素，有则说明该二叉树不是完全二叉树

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* tmp = QueueFront(&q);
		QueuePop(&q);
		if (tmp == NULL)
		{
			break;
		}
		QueuePush(&q,tmp->left);
		QueuePush(&q, tmp->right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* tmp = QueueFront(&q);
		QueuePop(&q);
		if (tmp != NULL)
		{
			QueueDestory(&q);//销毁队列
			return false;
		}
	}
	QueueDestory(&q);//销毁队列
	return true;

}

 7.完整代码

Tree.h

#define  _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int BTDataType;
// 二叉树链式结构
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType val;

}BTNode;


//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//层序遍历
void LevelOrder(BTNode* root);



// 二叉树结点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//⼆叉树的深度/高度
int BinaryTreeDepth(BTNode* root);
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);

Tree.c

#include"Tree.h"
#include"Queue.h"


//前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}


//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}



//层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//将二叉树根节点入队
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头
		BTNode* tmp=QueueFront(&q);
		printf("%d ", tmp->val);
		//出队
		QueuePop(&q);
		if (tmp->left)
		{
			QueuePush(&q, tmp->left);
		}
		if (tmp->right)
		{
			QueuePush(&q, tmp->right);
		}
	}
	QueueDestory(&q);

}



// 二叉树结点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right==NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);

}



// 二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLevelKSize(root->right,k-1);
}



//⼆叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int L = BinaryTreeDepth(root->left);
	int R = BinaryTreeDepth(root->right);

	return L> R ? 1 + L : 1 +R;
}


// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == x)
	{
		return root;
	}
	BTNode* tmp1=BinaryTreeFind(root->left,x);
	if (tmp1 != NULL)
	{
		return tmp1;
	}

	BTNode*tmp2=BinaryTreeFind(root->right, x);
	if (tmp2 != NULL)
	{
		return tmp2;
	}
	return NULL;
}


// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;

}

 test.c

#include"Tree.h"


BTNode* NewNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->left = newnode->right = NULL;
	newnode->val = x;
	return newnode;
}


BTNode* CreateTree()
{
	BTNode* node1 = NewNode(1);
	BTNode* node2 = NewNode(2);
	BTNode* node3 = NewNode(3);
	BTNode* node4 = NewNode(4);
	BTNode* node5 = NewNode(5);

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	return node1;
}


void testTree()
{
	BTNode* node1=CreateTree();
	
	
	PreOrder(node1);
	printf("\n");
	InOrder(node1);
	printf("\n");
	PostOrder(node1);

	printf("结点个数：%d\n",BinaryTreeSize(node1));
	printf("叶子结点个数：%d\n", BinaryTreeLeafSize(node1));
	printf("第k层结点个数：%d\n", BinaryTreeLevelKSize(node1,3));
	printf("深度：%d\n", BinaryTreeDepth(node1));
    BTNode* find=BinaryTreeFind(node1,13);
	printf("%s", find== NULL ? "找不到!" : "找到了");

	LevelOrder(node1);
	bool d=BinaryTreeComplete(node1);
	printf("%s", d == true ? "是完全二叉树" : "不是完全二叉树");

	BinaryTreeDestory(&node1);
}

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//队列结构的定义
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
	QDataType data;//节点内的数据
	struct QueueNode* next;//指向下一个节点的指针

}QueueNode;

typedef struct Queue
{
	struct QueueNode* phead;//指向第一个节点的指针
	struct QueueNode* ptail;//指向尾节点的指针
	int size;//节点的个数

}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//取队列头数据
QDataType QueueFront(Queue* pq);
//取队列尾数据
QDataType QueueBack(Queue* pq);
//队列有效数据个数
int QueueSize(Queue* pq);

Queue.c

#include"Queue.h"

//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

//销毁队列
void QueueDestory(Queue* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* Next = pcur->next;
		free(pcur);
		pcur = Next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL && pq->ptail == NULL;
}



//入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}





//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QueueNode* Next = pq->phead->next;
		free(pq->phead);
		pq->phead = Next;
	}
	pq->size--;

}

//取队列头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

//取队列尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;

}

//队列有效数据个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

以上就是二叉树(下)的全部内容了，本篇之后我们就学习完了二叉树的所有基本知识，接下来将会在之后的篇章中写一些二叉树相关的算法题，未完待续……