上一篇讲解了二叉树的链式存储和深度等问题有需要的可以去观看【数据结构】C语言实现二叉树(二叉树链式结构结点个数深度等)-CSDN博客目录一.前序遍历1.前序遍历的概念​编辑2.前序遍历的代码实现二.中序遍历1.中序遍历的概念2.中序遍历的代码实现三.后序遍历1.后序遍历的概念2.后序遍历的代码实现四.层序遍历1.层序遍历的概念思想2.层序遍历的代码实现Queue.hQueue.cTest.c总结二叉树的遍历是指按某条搜索路径访问树中每个结点使得每个结点均被访问一次而且仅被访问一次。按照先遍历左子树再遍历右子树的原则常见的遍历次序有前序、中序、后序和层序四种遍历算法。一.前序遍历1.前序遍历的概念若二叉树为空则不用遍历若不为空则按照根结点 左子树 右子树的顺序来遍历二叉树通过前序遍历得到的顺序为空用N来表示接下来我们来画出递归展开图来帮助大家更好理解程序运行的过程2.前序遍历的代码实现说明在实现前序遍历的时候我们要手搓一个二叉树但这不是真正的二叉树创建而是帮助我们更好理解遍历的逻辑即用来测试的后序我会真正讲解二叉树是如何实现的这里我们使用下面这个图来实现原理和上面的一样#includestdio.h #includestdlib.h #includestdbool.h typedef char data1; typedef struct BinaryTreeNode { data1 n; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyNode(char x) { BTNode* newnode (BTNode*)malloc(sizeof(BTNode*)); if (newnode NULL) { perror(malloc fail); exit(1); } newnode-n x; newnode-left NULL; newnode-right NULL; return newnode; } //返回二叉树的根节点,这不是真正意义上创建的二叉树而是测试用例 BTNode* CreatBinaryTree() { BTNode* nodeA BuyNode(A); BTNode* nodeB BuyNode(B); BTNode* nodeC BuyNode(C); BTNode* nodeD BuyNode(D); BTNode* nodeE BuyNode(E); BTNode* nodeF BuyNode(F); BTNode* nodeG BuyNode(G); BTNode* nodeH BuyNode(H); nodeA-left nodeB; nodeB-left nodeD; nodeB-right nodeE; nodeE-right nodeH; nodeA-right nodeC; nodeC-left nodeF; nodeC-right nodeG; return nodeA; } //用递归来实遍历前序根 左子树 右子树 void PreOrder(BTNode* root) { //判断根结点是否为空 if (root NULL) // A { // B C printf(0 ); // D E F G return; // H } printf(%c , root-n); PreOrder(root-left); PreOrder(root-right); } int main() { BTNode* root CreatBinaryTree(); PreOrder(root); printf(\n); return 0; }二.中序遍历1.中序遍历的概念若二叉树为空则不用遍历若不为空则按照左子树 根结点 右子树的顺序来遍历二叉树通过前序遍历得到的顺序为空用N来表示2.中序遍历的代码实现中序遍历的思想跟前序遍历的思想基本一样后序遍历也同样如此//中序左子树 根 右子树 void InOrder(BTNode* root) { if (root NULL) { printf(0 ); return; } InOrder(root-left); printf(%c , root-n); InOrder(root-right); }三.后序遍历1.后序遍历的概念若二叉树为空则不用遍历若不为空则按照左子树 右子树 根结点的顺序来遍历二叉树通过前序遍历得到的顺序为空用N来表示2.后序遍历的代码实现//后序左子树 右子树 根 void PostOrder(BTNode* root) { if (root NULL) { printf(0 ); return; } PostOrder(root-left); PostOrder(root-right); printf(%c , root-n); }四.层序遍历1.层序遍历的概念层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根结点所在 层数为1层序遍历就是从所在二叉树的根结点出发首先访问第一层的树根结点然后从左到右访问第2层 上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。思想进行层次遍历时需要借助一个队列层次遍历的思想为① 将二叉树的根结点入队② 若队列非空则队头结点出队并访问该结点若它有左孩子则将其左孩子入队若它有右孩子则将其右孩子入队③ 重复步骤 ② 直至队列为空。2.层序遍历的代码实现由于这里要用到队列的代码所以我把队列的相关代码也贴在这里确保代码能够正常实现。若是对这些代码理解有问题可以看我写的队列的详细内容吃透各个函数的相关知识Queue.h#pragma once #includestdio.h #includestdlib.h #includeassert.h #includestdbool.h //链式结构表示队列 //相当于前置声明队列中存放的是二叉树中结点指针的地址 typedef struct BinaryTreeNode* data; typedef struct QListNode { data a; struct QListNode* next; }QNode;//队列中的结点 //由于队列是先进先出所以插入的时候都需要找尾结点不如直接定义两个指针一个指向头结点一个指向尾结点 //但是传递参数需要传递两个指针不如将两个指针定义在一个结构体中只用传递结构体即可 //队列的结构 typedef struct Queue { QNode* head; QNode* ptial; int size;//累计队列中有几个结点 }Queue; //初始化队列 void QueueInit(Queue* q);//两个指针都指向头结点 //void QueueInit(QNode* head, QNode* pital);//创建头结点可以传递一级指针没有头结点要传递二级指针 //队尾入队列 void QueuePush(Queue* q, data x); //对头出队列 void QueuePop(Queue* q); //获取队列头部元素 data QueueFront(Queue* q); //获取队列尾部元素 data QueueBack(Queue* q); //判断队列是否为空 bool QueueEmpty(Queue* q); //销毁队列 void QueueDestory(Queue* q); //队列中的元素个数 int QueueSize(Queue* q);Queue.c#includeQueue.h //初始化队列 void QueueInit(Queue* q) { q-head NULL; q-ptial NULL; q-size 0; } //队尾入队列 void QueuePush(Queue* q, data x) { assert(q); //创建新结点 QNode* newnode (QNode*)malloc(sizeof(QNode)); if (newnode NULL) { perror(newnode fail); exit(1); } newnode-next NULL; newnode-a x; if (q-ptial NULL) { q-ptial newnode; q-head newnode; } else q-ptial-next newnode; q-ptial newnode; q-size; } //对头出队列 void QueuePop(Queue* q) { //判断队列是否为空 assert(q); assert(q-head ! NULL); ////存放第二个结点 //QNode* next q-head-next-next; //free(q-head-next); //q-head-next next; //q-size--; //没有将指针ptial置为空成为野指针了 //一个结点 if (q-head-next NULL) { free(q-head); q-head q-ptial NULL; } else { QNode* next q-head-next; free(q-head); q-head next; } q-size--; } //获取队列头部元素 data QueueFront(Queue* q) { assert(q); assert(q-head ! NULL); return q-head-a; } //获取队列尾部元素 data QueueBack(Queue* q) { assert(q); assert(q-head ! NULL); return q-ptial-a; } //判断队列是否为空 bool QueueEmpty(Queue* q) { assert(q); return q-size 0; } //销毁队列 void QueueDestory(Queue* q) { assert(q); QNode* cur q-head; while (cur) { QNode* next cur-next; free(cur); cur next; } q-head q-ptial NULL; q-size 0; //QNode* cur q-head; //while (cur) //{ // QNode* next cur-next; // free(cur); // cur next; //} //q-head q-ptial NULL; //q-size 0; } //队列中的元素个数 int QueueSize(Queue* q) { assert(q); return q-size; }Test.c#includestdio.h #includestdlib.h #includestdbool.h #includeQueue.h typedef char data1; typedef struct BinaryTreeNode { data1 n; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyNode(char x) { BTNode* newnode (BTNode*)malloc(sizeof(BTNode*)); if (newnode NULL) { perror(malloc fail); exit(1); } newnode-n x; newnode-left NULL; newnode-right NULL; return newnode; } //返回二叉树的根节点,这不是真正意义上创建的二叉树而是测试用例 BTNode* CreatBinaryTree() { BTNode* nodeA BuyNode(A); BTNode* nodeB BuyNode(B); BTNode* nodeC BuyNode(C); BTNode* nodeD BuyNode(D); BTNode* nodeE BuyNode(E); BTNode* nodeF BuyNode(F); BTNode* nodeG BuyNode(G); BTNode* nodeH BuyNode(H); nodeA-left nodeB; nodeB-left nodeD; nodeB-right nodeE; nodeE-right nodeH; nodeA-right nodeC; nodeC-left nodeF; nodeC-right nodeG; return nodeA; } //层序遍历 void TreeLevelOrder(BTNode* root) { Queue q; QueueInit(q); //先入根节点的地址 if(root) QueuePush(q, root); while (!QueueEmpty(q)) { //出队列存储下来结点的地址 BTNode* Front QueueFront(q); printf(%c , Front-n); QueuePop(q); if(Front-left) QueuePush(q, Front-left); if(Front-right) QueuePush(q, Front-right); } QueueDestory(q); } int main() { BTNode* root CreatBinaryTree(); //层序遍历 TreeLevelOrder(root); printf(\n); return 0; }总结二叉树四种遍历方式前序遍历根节点 → 左子树 → 右子树先访问根再依次遍历左右子树中序遍历左子树 → 根节点 → 右子树根在中间常用于二叉搜索树排序后序遍历左子树 → 右子树 → 根节点最后访问根适合删除节点等操作层序遍历按树的层级从上到下、从左到右访问节点需借助队列实现。四种遍历核心是访问节点的顺序不同前 / 中 / 后序属深度优先依赖递归 / 栈实现侧重纵向遍历层序属广度优先依赖队列实现侧重横向分层。不同遍历适配不同场景比如中序适合排序层序适合层级相关操作掌握顺序逻辑是关键。通过本节课的学习相信你一定有所收获如果对你有帮助欢迎 点赞、收藏、关注后续持续更新数据结构与算法