【数据结构】_二叉树的遍历与销毁

目录

1. 深度优先遍历（DFS）

1.1 理论

1.2 程序实现

2. 广度优先遍历（BFS）

2.1 理论

2.2 程序实现 

3. 二叉树的销毁

---

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);
}

注：不可采用前序或中序遍历对二叉树进行销毁，根结点的释放会导致该子树的子孙结点无法释放。