一、结构体声明和函数声明
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<stdbool.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 n, 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);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
//队列
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);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);二、二叉树各个函数的实现
1.二叉树构建函数: BinaryTreeCreate
利用前序遍历数组构建二叉树
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)//n为字符串长度，要使用下标i的指针，
//这样才可以改变其的值
{
if (*pi == n - 1)//如果字符数组的下标到达字符串长度-1 的位置，说明已经构建完成
return NULL;
//如果是空节点，就不要申请空间
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
//如果不是空节点，要申请一个空间存储结点的数据
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
//存储当前的字符串中的数据信息
newnode->data = a[*pi];
(*pi)++;
//构建左右子树
newnode->left = BinaryTreeCreate(a,n,pi);
newnode->right = BinaryTreeCreate(a, n, pi);
return newnode;
}2.二叉树销毁函数: BinaryTreeDestory
确保能够将所有结点都删除，所有要采用后序遍历的方法来进行对每一个结点的删除
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)//后序遍历销毁
{
if (root == NULL)
return ;
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
free(root);//释放结点
}
3.求二叉树节点个数函数: BinaryTreeSize
结点为空，说明没有结点，否则其等于：左子树结点+右子树结点+1（自己本身）
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)//结点为空，返回0，否则返回，左子树+右子树+1
{
if (root == NULL) //如果该结点为空，返回0
return 0;
//每个结点，都是由左子树的结点个数+右子树的结点个数+1（自己本身）
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;//左子树+右子树+1
}
4.求二叉树叶子节点个数函数: BinaryTreeLeafSize
如果左右子树都为空，说明是叶子结点，如果不是，继续判断它的左右孩子结点的情况
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)//如果该结点为空，返回0
return 0;
if (root->left == NULL && root->right == NULL)//如果左右子树都为空，说明是叶子结点，返回1
return 1;
//不是叶子结点，遍历其左，右子树
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
5. 求二叉树第k层节点个数函数:BinaryTreeLevelKSize
空结点返回0，第一层返回1，其他层 返回 左子树的k-1层+右子树的k-1层的 结点总和
// 二叉树第k层节点个数
//空结点返回0，第一层返回1，其他层 返回 左子树的k-1层+右子树的k-1层的 结点总和
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)//如果该结点为空，返回0
return 0;
if (k == 1) //第一层只有一个结点，返回1
return 1;
//其他层 返回 左子树的k-1层+右子树的k-1层的 结点总和
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
6.二叉树查找值为x的节点函数:BinaryTreeFind
每次查找都要创建一个二叉树节点类型的临时变量，来记录每次的查找结果，并将其返回
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)//如果结点为空，返回NULL,说明没找到
return NULL;
if (root->data == x) //如果该结点的值等于要寻找的值，就将该结点返回
return root;
BTNode* ret1 = BinaryTreeFind(root->left, x); //保证每次都先找该结点的左孩子，后找右孩子
if (ret1) //如果找到的不是NULL,就将其结点返回
return ret1;
BTNode* ret2 = BinaryTreeFind(root->right, x);
if (ret2) //如果找到的不是NULL,就将其结点返回
return ret2;
return NULL; //没找到返回NULL
}
7.二叉树前序遍历函数: BinaryTreePrevOrder
先访问根结点，再访问左子树和右子树
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
printf("%c", root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}
8.二叉树中序遍历函数:BinaryTreeInOrder
先访问左子树，再是根节点，最后是右子树
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreeInOrder(root->left);
printf("%c", root->data);
BinaryTreeInOrder(root->right);
}
9.二叉树后序遍历函数:BinaryTreePostOrder
先访问左子树和右子树，最后访问根结点
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c", root->data);
}
10.层序遍历函数:BinaryTreeLevelOrder
（1）思路方法
使用队列的性质，先进先出，出元素在队头，入元素在队尾。
首先将树的根节点入队列，然后将队头元素出队列，这时还要将这个刚出队列的队头结点的左右孩子结点入队列，（如果非空入队列，空结点不要入队列）。
使用循环，直至队列为空，循环停止。按层次依次输出所有值
因为队头元素每出队一次，都在更新，所以所有的结点都是按照层次顺序依次进入队列，然后依次出队列
（2）队列的实现代码：
// 初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->front = NULL; //初始化为NULL
q->rear = NULL;//初始化为NULL
q->size = 0; //初始化个数为0
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));//申请新的结点
if (newnode == NULL)
{
perror("malloc fail");
return;
}
else
{
newnode->data = data;
newnode->next = NULL;
if (q->front == NULL) //如果front指针指向的是NULL，说明插入前队列是空队列
{
q->front = newnode;
q->rear = newnode;
}
else //front指向的不是NULL,说明不是空队列
{
q->rear->next = newnode;
q->rear = newnode;
}
q->size++; //插入完，个数加1
}
}
// 队头出队列
void QueuePop(Queue* q)//出队就是头删
{
assert(q);
assert(q->size != 0);//队列不为空
QNode* head = q->front; //找到头结点
if (head->next == NULL)//如果出队之前，前队列只有一个结点
{
free(head); //释放头结点，后front 和rear都要指向NULL,表示现在是空队列
head = NULL;
q->front = q->rear = NULL;
q->size = 0; //个数置为0
return;
}
else //出队前，队列有两个及其以上的结点数
{
QNode* del = head;
head = head->next; //更新头结点
free(del);
del = NULL;
q->front = head; //将front 指向更新后的头结点
q->size--;//个数减1
}
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
return q->front->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
return q->rear->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
if (q->front == NULL)//队列为空，返回1
return 1;
else
return 0;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* del = q->front; //如果是空队列，就直接返回NULL，不要释放结点
if (del == NULL)
{
;
}
else
{
QNode* cur = del->next;
while (del != NULL) //逐个释放结点
{
free(del);
del = cur;
if (cur != NULL)
cur = cur->next;
}
}
//队头指针和队尾指针都是要置NULL的，size都是要置为0
q->front = q->rear = NULL;
q->size = 0;
}
（3）层次遍历算法代码
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)//利用队列实现
{
Queue Q;
QueueInit(&Q);//初始化队列
if(root!=NULL)
QueuePush(&Q, root);//根结点入队列
while (!QueueEmpty(&Q))
{
BTNode* temp = QueueFront(&Q);//取队头元素
printf("%c", temp->data);//打印队头结点 所对应的数据元素
QueuePop(&Q);//队头元素出队
//队头元素出队后，将其左右两个孩子结点入队 (孩子结点为空，没有进入队列)
if(temp->left!=NULL) //左孩子不为空，入队列
QueuePush(&Q, temp->left);
if (temp->right != NULL) //右孩子不为空，入队列
QueuePush(&Q, temp->right);
}
QueueDestroy(&Q);//最后销毁队列
}
11. 判断二叉树是否是完全二叉树函数: BinaryTreeComplete
（1）思路方法
使用队列的性质，先进先出，出元素在队头，入元素在队尾。
首先将树的根节点入队列，然后将队头元素出队列，这时还要将这个刚出队列的队头结点的左右孩子结点入队列，（空与非空结点都入队列）。
先使用一个循环，队列为非空为循环条件，元素依次人队和出队
如果队头元素出队时，遇到空结点，就跳出循环。说明找到了一个空节点
现在要再次使用循环，判断在空节点之后是否有出现非空结点，有说明不是完全二叉树，没有说明是完全二叉树
(2)算法代码
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
Queue Q;
QueueInit(&Q);//初始化队列
if (root != NULL)
QueuePush(&Q, root);//根结点入队列
while (!QueueEmpty(&Q))
{
BTNode* temp = QueueFront(&Q);//取队头结点元素
QueuePop(&Q);//队头元素出队
if (temp == NULL) //如果出队的队头元素为NULL,就跳出循环，
//寻找接下来有没有非空结点
{
break;
}
//队头元素出队后，将其左右两个孩子结点入队 (孩子结点为空，也进入了队列)
QueuePush(&Q, temp->left);//左孩子入队列
QueuePush(&Q, temp->right); //右孩子入队列
}
//再次使用循环，判断在空节点之后是否有出现非空结点，有说明不是完全二叉树，没有说明是完全二叉树
while (!QueueEmpty(&Q))
{
QDataType temp = QueueFront(&Q);//取队头元素 (QDataType是QNode*的类型)
QueuePop(&Q);//队头元素出队
if (temp != NULL) //如果找到队头元素不是空，说明不是完全二叉树，返回false
{
QueueDestroy(&Q);//最后销毁队列
return false;
}
}
QueueDestroy(&Q);//最后销毁队列
return true; //是完全二叉树，返回true
}
三、测试
int main()
{
char arr[] = "ABD##E#H##CF##G##";
int len = strlen(arr);
int i = 0;
//构建二叉树
BTNode* root = BinaryTreeCreate(arr, len, &i);
//水平遍历
BinaryTreeLevelOrder(root);
printf("\n");
int cur = BinaryTreeComplete(root);
if (cur == 1)
printf("是完全二叉树\n");
else
printf("不是完全二叉树\n");
//前序遍历
printf("前序遍历结点:");
BinaryTreePrevOrder(root);
printf("\n");
//中序遍历
printf("中序遍历结点:");
BinaryTreeInOrder(root);
printf("\n");
//后序遍历
printf("后序遍历结点:");
BinaryTreePostOrder(root);
printf("\n");
int a=BinaryTreeLevelKSize(root, 4);
printf("该层有%d个\n", a);
int b=BinaryTreeLeafSize(root);
printf("叶子结点有%d个\n", b);
int c= BinaryTreeSize(root);
printf("总结点有%d个\n", c);
int d=BinaryTreeDepth(root);
printf("树深为%d\n", d);
BinaryTreeDestory(root);//销毁二叉树
return 0;
}
结果：
