初阶数据结构之---二叉树链式结构（二叉树的构建，二叉树的前序，中序，后序和层序遍历，计算二叉树结点个数，第k层结点个数，叶子结点个数，判断是否为完全二叉树）

引言

本篇博客是初阶数据结构树的收尾，将会讲掉基本二叉树链式结构的具体内容和实现，包括二叉树的构建，前序遍历，中序遍历，后序遍历和层序遍历，计算二叉树结点个数，第k层结点个数，二叉树叶子结点个数，以及判断一个二叉树是否为完全二叉树。话不多说，开始我们今天的内容。

二叉树链式结构

在之前的博客中，已经讲到了关于链式二叉树相关定义的内容。

这里我们可以来看一看关于二叉树结点的定义：

typedef char BTDataType;//定义存储数据类型
 
typedef struct BinaryTreeNode
{
	BTDataType _data; //存储数据
	struct BinaryTreeNode* _left; //指向左孩子（左子树）
	struct BinaryTreeNode* _right; //指向右孩子（右子树）
}BTNode;

二叉树：

1. 空树

2. 非空树：由根结点，根节点的左子树，根节点的右子树组成。

从概念上可以看出，二叉树是递归定义的，后面对二叉树的构建和遍历操作都是围绕递归的思路展开。

二叉树的遍历方式及实现

学习二叉树，首先就需要学会其遍历方式，所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照不同的遍历规则，二叉树的遍历方式有四种：前序遍历，中序遍历，后序遍历和层序遍历

1. 前序遍历(Preorder Traversal 亦称先序遍历)访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)访问根结点的操作发生在遍历其左右子树之后。

这三种遍历方式大同小异，层序遍历放到后面单独再讲。

下面仔细讲下前序遍历，弄懂前序遍历，中序和后序也就没什么难度了。

1.前序遍历

前序遍历：访问根结点的操作发生在遍历其左右子树之前。

前序遍历图解：

对于上面这棵二叉树：

前序遍历结果：1 2 3 N N N 4 5 N N 6 N N

中序遍历结果：N 3 N 2 N 1 N 5 N 4 N 6 N

后序遍历结果：N N 3 N 2 N N 5 N N 6 4 1

层序遍历结果：1 2 4 3 N 5 6 N N N N N N

代码实现：

打印结点操作在遍历左右子树之前。

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)return; //遇到NULL结点返回
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left); //递归到左子树
	BinaryTreePrevOrder(root->_right); //递归到右子树
}

2.中序遍历

中序遍历：访问根结点的操作发生在遍历其左右子树之中（间）。

代码实现：
与前序很相似，不过打印结点操作在遍历完左子树之后。

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)return; //遇到NULL结点返回
	BinaryTreeInOrder(root->_left); //遍历左子树
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right); //遍历右子树
}

3.后续遍历

后序遍历：访问根结点的操作发生在遍历其左右子树之后。

代码实现：

与前序遍历相似，不过打印结点操作在遍历完左右子树之后。

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)return; //遇到NULL结点返回
	BinaryTreePostOrder(root->_left); //遍历左子树
	BinaryTreePostOrder(root->_right); //遍历右子树
	printf("%c ", root->_data);
}

4.层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

二叉树层序遍历的实现，需要借助之前讲过的一个数据结构——队列。

在使用队列之前，需要知道队列中存放的是什么内容，对于二叉树的结点来说，存放的应该是指向二叉树结点的指针：

// 链式结构：表示队列 
typedef BTNode* QDataType;
//队列的一个结点
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;
// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
	int size;//队列元素个数
}Queue;

看一下实现代码，这里直接复用队列的内容：

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->_front = NULL;
	q->_rear = NULL;
	q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL) {
		perror("malloc fail:");
		exit(1);
	}
	newnode->_data = data;
	newnode->_next = NULL;
	if (q->_front == NULL) {
		q->_front = newnode;
		q->_rear = newnode;
	}
	else {
		q->_rear->_next = newnode;
		q->_rear = newnode;
	}
	q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->_front);
	if (q->size == 1) {
		free(q->_front);
		q->_front = q->_rear = NULL;
	}
	else {
		QNode* pnext = q->_front->_next;
		free(q->_front);
		q->_front = pnext;
	}
	q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->_front);
	return q->_front->_data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->_rear);
	return q->_rear->_data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	if (q->_front == NULL)return;
	if (q->size == 1) {
		free(q->_front);
	}
	else {
		while (q->_front) {
			QNode* pnext = q->_front->_next;
			free(q->_front);
			q->_front = pnext;
		}
	}
	q->_front = q->_rear = NULL;
	q->size = 0;
}
 
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue qu; //创建一个队列
	QueueInit(&qu); //初始化队列
	if (root)QueuePush(&qu, root); //判断树是否为空树
	while (!QueueEmpty(&qu)) { //结束条件：队列为空
		BTNode* front = QueueFront(&qu); //取出队列中首元素
		QueuePop(&qu); //删除队首元素
		printf("%c ", front->_data); //打印遍历到的结点数据
        //将下一层结点放入队列中
		if (front->_left)QueuePush(&qu, front->_left);
		if (front->_right)QueuePush(&qu, front->_right);
	}
	printf("\n");
	QueueDestroy(&qu);//销毁队列
}

层序遍历规则：

1. 根节点的指针入队列。
2. 队列非空，队列中首元素出队，将队列下一层元素带入队尾（如果元素为NULL则不入队）。
3. 如果队列为空，循环停止，遍历结束。

关于结点数和查找

计算二叉树结点个数

把二叉树递归遍历一遍就可以得到结点个数，每层结点递归时都加一。

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)return 0;
    //return中遍历了整个二叉树，很像递归方式求斐波那契数
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

计算叶子结点个数

也是需要遍历一遍二叉树，但是需要满足叶子结点条件（左右孩子都为NULL）的时候才会return 1计数。

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

计算二叉树第k层结点个数

底层逻辑依然是遍历二叉树，这里计算第k层结点个数的关键点是通过控制每层递归传入的k值判断当前结点所在层数。

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)return 0;
	else if (k == 1)return 1;//当k==1时说明此处遍历的结点已经是第k层
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}

二叉树查找值为x的结点

查找的逻辑依然是遍历二叉树。

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)return NULL;
	else if (root->_data == x)return root;
	BTNode* ret1 = BinaryTreeFind(root->_left, x);
	if (ret1)return ret1; //如果左子树找到（不为NULL），直接返回，否则返回右子树
	return BinaryTreeFind(root->_right, x);
}

二叉树的创建和销毁

二叉树的创建（前序遍历）

此处讲的二叉树创建，是以一个所给的前序遍历数组为基础（如："ABD##E#H##CF##G##"）创建的。其实创建过程的本质还是递归结构。

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	assert(*pi <= n);
	if (a[*pi] == '#') {
		(*pi)++;
		return NULL;
	}
    //开辟结点空间
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL) { //判断空间是否开辟成功
		perror("malloc fail:");
		exit(1);
	}
	root->_data = a[(*pi)++];
    //递归构建左右子树
	root->_left = BinaryTreeCreate(a, n, pi);
	root->_right = BinaryTreeCreate(a, n, pi);
	return root;
}

二叉树的销毁

二叉树的销毁更适合基于后序遍历，从下往上依次销毁。这里并不是说前序和中序遍历无法实现销毁这一过程，只是用这两种结构实现会将问题复杂化——前中序遍历在销毁根节点后很难在找到左右孩子结点继续进行递归销毁，而后续遍历却可以规避这个问题：因为在删除根节点之前左右子树及其结点已被释放无需递归删除。

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)return;
	BinaryTreeDestory(&((*root)->_left));
	BinaryTreeDestory(&((*root)->_right));
	free(*root);
	*root = NULL;
}

上述代码传递二级指针是为了方便根节点指针置空，传一级指针在函数外部置空也是一种可行的解决方式。

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

判断一个二叉树是否为完全二叉树，可以使用之前讲到的层序遍历的思想。

完全二叉树：除了最后一层，其他每一层结点都是完全填满的，且最后一层所有结点都集中在左侧。层序遍历的过程中，如果遇到了一个结点，其无左子树而有右子树，那么这棵树肯定不是完全二叉树；另外，如果遇到了一个结点并非左右子结点都有，那么所有接下来遍历到的结点都必须是叶子节点。

我们可以在原有的层序遍历代码上修改：
这里就不再粘贴一遍队列的代码了

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	Queue qu;
	QueueInit(&qu);
	if (root)QueuePush(&qu, root);
	while (!QueueEmpty(&qu)) {
		BTNode* front = QueueFront(&qu);
		QueuePop(&qu);
		if (front == NULL)break;//如果队列中出现空结点跳出循环，进行下一步判断
        //通过push将下一层结点带入队列
		QueuePush(&qu, front->_left);
		QueuePush(&qu, front->_right);
	}
	while (!QueueEmpty(&qu)) {
		BTNode* front = QueueFront(&qu);
		QueuePop(&qu);
        //如果出现非空结点则证明不是完全二叉树
		if (front) {
			QueueDestroy(&qu);
			return false;
		}
	}
	QueueDestroy(&qu);
    //如果正常跳出循环则证明为完全二叉树
	return true;
}

上述代码的主要判断逻辑是，当队列中出现一个空结点时，判断此时队列中剩余结点是否都为空：如果队列中剩余结点都为空则证明是完全二叉树；如果存在非空结点则证明不是完全二叉树。

具体代码演示

这里来测试一下之前所写的二叉树的接口函数：

int main()
{
	char arr[] = "ABD##E#H##CF##G##";
	int i = 0;
	BTNode* treeroot = BinaryTreeCreate(arr, sizeof(arr) / sizeof(arr[0]), &i);
	printf("结点个数：%d\n", BinaryTreeSize(treeroot));
	printf("叶子结点个数：%d\n", BinaryTreeLeafSize(treeroot));
	int k;
    printf("输入计算第几层的结点个数：");
	scanf("%d", &k);
	printf("第k层结点个数： % d\n", BinaryTreeLevelKSize(treeroot, k));
	BTNode* node = BinaryTreeFind(treeroot, 'C');
	printf("%c\n", node->_data);
	printf("二叉树前序遍历：");
	BinaryTreePrevOrder(treeroot);
	printf("\n");
	printf("二叉树中序遍历：");
	BinaryTreeInOrder(treeroot);
	printf("\n");
	printf("二叉树后序遍历：");
	BinaryTreePostOrder(treeroot);
	printf("\n");
	printf("二叉树层序遍历：");
	BinaryTreeLevelOrder(treeroot);
	printf("是否为完全二叉树：%d",BinaryTreeComplete(treeroot));
	BinaryTreeDestory(&treeroot);
	return 0;
}

下面是所创建树的结构： 

 

下面是运行结果： 

结语

关于二叉树链式结构的内容到这里就结束了。本篇博客围绕二叉树的遍历，结点个数计算以及数值查找等内容展开。关于二叉树更多有趣的内容还远远不止这些，不过再次深入时就会以C++的方式来给大家呈现，如果对后续内容感兴趣的话，还请大家多多关注博主，感谢大家的支持。