目录
1. 深度优先遍历（DFS）
1.1 理论
深度优先遍历包括前序遍历、中序遍历与后序遍历；
前序遍历：访问根结点的操作发生在遍历其左右子树之前；（根->左子树->右子树）
中序遍历：访问根结点的操作发生在遍历其左右子树之中；（左子树->根->右子树）
后序遍历：访问根结点的操作发生在遍历其左右子树之后；（左子树->右子树->根）
以#表示空：
前序遍历：1 2 3 # # # 4 5 # # 6 # #
中序遍历：# 3 # 2 # 1 # 5 # 4 # 6 #
后序遍历：# # 3 # 2 # # 5 # # 6 4 1
1.2 程序实现
前序遍历函数PreOrder，中序遍历函数InOrder，后序遍历函数PostOrder实现如下：
// 前序遍历
void PreOrder(BTNode* root) {
if (root == NULL) {
printf("# ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
// 中序遍历
void InOrder(BTNode* root) {
if (root == NULL) {
printf("# ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
// 后序遍历
void PostOrder(BTNode* root) {
if (root == NULL) {
printf("# ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}为了验证递归调用实现深度优先遍历的正确性，现手搓一个二叉树（同理论部分）：
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int BTDataType;
typedef struct BinaryTreeNode {
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode* CreateBTNode(BTDataType x) {
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL) {
perror("malloc fail");
return NULL;
}
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
// 手搓一个二叉树
BTNode* CreateBinaryTree() {
BTNode* node1 = CreateBTNode(1);
BTNode* node2 = CreateBTNode(2);
BTNode* node3 = CreateBTNode(3);
BTNode* node4 = CreateBTNode(4);
BTNode* node5 = CreateBTNode(5);
BTNode* node6 = CreateBTNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}在main函数中调用以上三个函数，输出遍历结果：
int main() {
BTNode* root = CreateBinaryTree();
printf("PreOrder: \n");
PreOrder(root);
printf("\nInOrder: \n");
InOrder(root);
printf("\nPostOrder: \n");
PostOrder(root);
return 0;
}运行结果如下图，与理论的遍历序列一致：
2. 广度优先遍历（BFS）
在二叉树的遍历中，广度优先遍历即层序遍历；
BFS的实现需要借助队列，具体思路为上一层一个元素出队列则带下一层的元素入队列，由于队列先进先出的特性，即可实现二叉树的层序遍历。
2.1 理论
1. 此处队列代码实现直接衔接Queue.h与Queue.c文件，具体操作为：复制已实现的Queue.h与Queue.c文件，在当前二叉树的项目文件添加现有项，将以上两个文件拷贝到当前项目目录中后，在当前二叉树的.c文件中引用Queue.h即可。
本专栏前文已实现基本的Queue.h和Queue.c文件，理论与程序详情见下文，下文程序也不再展示关于队列的声明与实现：
【数据结构】_队列的结构与实现-CSDN博客文章浏览阅读753次，点赞15次，收藏11次。队列：只允许在一端进行数据的插入操作，在另一端进行数据的删除操作的特殊线性表，队列具有先进先出FIFO（First In First Out）的特点。（2）若队列仅剩一个元素，按当前无特殊情况处理的方法实现，则pq->ptail未置空，使得其成为野指针，故需对其进行单独处理。注：若采取设有头结点的单链表，可传一级指针，但仍然需传队尾结点指针，仍需要传递两个参数，总体而言依然较为麻烦。若将数组头视为队头，数组尾视为队尾，则插入对应尾插实现方便，但删除对应头删实现麻烦；出队列：进行删除操作的一端称为队头；https://blog.csdn.net/m0_63299495/article/details/1454438952. 再考虑队列元素类型问题，存储结点的数值域显然无法定位其子结点，不可行；存储结点的结构体的空间占用较大，不采取；存储结点的指针是较好的选择。
Queue.h中原本的队列结点与队列链式结构的结构体如下：
typedef int QDataType;
typedef struct QueueNode {
QDataType val;
struct QueueNode* next;
}QNode;
typedef struct Queue {
QNode* phead;
QNode* ptail;
int size;
}Queue;现QDataType的类型进行修改：
typedef BTNode* QDataType;但这种typedef的定义可能会导致无法识别，建议写为原生类型，即：
typedef struct BinaryTreeNode* QDataType;2.2 程序实现
#include "Queue.h"
void TreeLevelOrder(BTNode* root) {
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q)) {
BTNode* front = QueueFront(&q);
printf("%d ", front->data);
QueuePop(&q);
if (front->left)
QueuePush(&q,front->left);
if (front->right)
QueuePush(&q,front->right);
}
QueueDestory(&q);
}
int main() {
BTNode* root = CreateBinaryTree();
printf("\nBinaryLevelOrder: ");
TreeLevelOrder(root);
return 0;
}测试结果如下：
3. 二叉树的销毁
按照后序对二叉树进行递归销毁：
void TreeDestory(BTNode* root) {
if (root == NULL)
return;
TreeDestory(root->left);
TreeDestory(root->right);
free(root);
}注：不可采用前序或中序遍历对二叉树进行销毁，根结点的释放会导致该子树的子孙结点无法释放。