数据结构之链式结构二叉树的实现（进阶版）

本篇文章主要讲解链式二叉树的层序遍历以及判断是否为一棵完全二叉树

二者将会用到之前学过的队列知识，是将队列和二叉树的整合

一、如何将之前已经写好的文件加入当前的编译界面

如图所示，打开我们需要加入文件所在的文件夹，找到我们要加入的文件，按ctrl+c将其复制下来，在本文中，我们需要将queue.h和queue.c复制下来.

然后在找到我们当前文件所在的文件夹，将其粘贴进去，如图所示

 

之后在vs的解决方案栏中找到 头文件，右键，添加，现有项，进入这个界面

长按ctrl并且鼠标左键选择queue.h和queue.c,之后点添加，之后这个栏是这样的

此时在鼠标左键按住queue.c文件，拖到源文件处即可

好了，前提条件已经具备了，下面准备写代码了

二、层序遍历及判断完全二叉树

这里由于我们是要将二叉树的各个结点入队列，所以前面的typedef应该改一下

queue文件基本上不需要改动！

接下来我们将实现 层序遍历及判断完全二叉树，这里仅展示与其相关的代码，其余的代码前往上一篇文章查看！

这是tree.h文件

// 层序遍历
void LevelOrder(btnode* root);
// 判断⼆叉树是否是完全⼆叉树
bool BinaryTreeComplete(btnode* root);

这是tree.c文件

#include"queue.h"
//层序遍历
void LevelOrder(btnode* root)
{queue q;queueinit(&q);queuepush(&q, root);while (!queueempty(&q)){//取队头,出队头btnode* top = queuefront(&q);queuepop(&q);printf("%c", top->data);        //注意不要写成%d!!!!!//将队头的左右孩子入队列（不为空）if (top->left){queuepush(&q, top->left);}if (top->right){queuepush(&q, top->right);}}queuedestroy(&q);
}
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(btnode* root)
{queue q;queueinit(&q);queuepush(&q,root);while (!queueempty(&q)){//取队头，出队头btnode* top = queuefront(&q);queuepop(&q);if (top == NULL){ //只要取到空结点就跳出while循环break;}//把不为空的头结点的左右孩子入队列queuepush(&q, top->left);queuepush(&q, top->right);}//此时队列可能为空，也可能不为空，故继续取，若取到不为空的结点，则证明不是完全二叉树while (!queueempty(&q)){btnode* top = queuefront(&q);queuepop(&q);if (top != NULL){queuedestroy(&q);return false;}}queuedestroy(&q);return true;
}

这是test.c文件

	//层序遍历LevelOrder(root);printf("\n");//判断是否为完全二叉树if (BinaryTreeComplete(root)){printf("It is a complete binary tree!");}else{printf("It is not a complete binary tree!");}BinaryTreeDestory(&root);

运行结果附上：