本文针对数据结构初学者和进阶开发者完整覆盖二叉树前序、中序、后序遍历的递归与非递归实现包含可直接运行代码、易错点剖析、核心逻辑拆解助力快速掌握二叉树遍历核心算法。目录一、二叉树的基础概念二、二叉树节点的结构定义三、创建二叉树节点四、二叉树的核心遍历算法4.1 递归遍历4.1.1 前序遍历根 - 左 - 右4.1.2 中序遍历左 - 根 - 右4.1.3 后序遍历左 - 右 - 根4.1.4 递归遍历模板4.1.5 递归序访问次序4.1.6 完整可运行示例构建二叉树 遍历4.1.7 运行结果4.2 非递归遍历借助栈实现4.2.1 前序遍历根 - 左 - 右4.2.2 中序遍历左 - 根 - 右4.2.3 后序遍历左 - 右 - 根- 双栈法- 单栈法4.2.4 单栈法后序遍历深度拆解4.2.5 补充C语言实现栈的基本操作函数五、总结与拓展一、二叉树的基础概念二叉树是一种每个节点最多拥有两个子节点的树形数据结构两个子节点分别称为左子节点左孩子和右子节点右孩子。二叉树的核心操作以遍历为基础遍历指按特定顺序访问所有节点且每个节点仅访问一次其中前序、中序、后序遍历属于深度优先遍历DFS依赖递归或栈实现层序遍历属于广度优先遍历BFS依赖队列实现本文重点讲解前/中/后序遍历。二、二叉树节点的结构定义首先需要定义二叉树的节点类型包含数据域和两个指针域分别指向左、右子节点具体代码如下#includestdio.h#includestdlib.h#includestdbool.h// 定义二叉树节点结构体typedefstructBinaryTreeNode{intdata;// 数据域存储节点值此处以int类型为例可按需修改structBinaryTreeNode*left;// 左子节点指针指向左子树structBinaryTreeNode*right;// 右子节点指针指向右子树}BTNode,*BTree;// 别名定义BTNode为节点类型BTree为节点指针类型说明data存储节点的具体数据这里使用int类型实际开发中可替换为字符、结构体等其他类型。left/right分别指向左、右子节点初始化为NULL时表示该方向无子节点叶子节点的两个指针均为NULL。typedef别名简化了后续代码书写BTree等价于struct BinaryTreeNode *。三、创建二叉树节点为了方便构建二叉树先实现一个创建单个节点的辅助函数用于分配内存并初始化节点数据和指针// 创建单个二叉树节点返回节点指针BTNode*createBTNode(intdata){// 分配内存BTNode*newNode(BTNode*)malloc(sizeof(BTNode));if(newNodeNULL){// 内存分配失败判断perror(malloc failed);exit(EXIT_FAILURE);}// 初始化节点newNode-datadata;newNode-leftNULL;newNode-rightNULL;returnnewNode;}四、二叉树的核心遍历算法二叉树的遍历是指按照一定顺序访问二叉树中的所有节点且每个节点仅被访问一次最常用的是前序、中序、后序遍历深度优先分为递归实现和非递归实现。4.1 递归遍历递归遍历的核心思想是利用函数自身调用遵循 “先处理当前节点 / 先处理子树” 的规则递归遍历左、右子树。4.1.1 前序遍历根 - 左 - 右第一次来到一个结点的时候就打印访问顺序先访问根节点再递归前序遍历左子树最后递归前序遍历右子树。// 前序遍历递归版voidpreOrderTraverse(BTree root){if(rootNULL){// 递归终止条件空树无需访问return;}printf(%d ,root-data);// 1. 访问根节点preOrderTraverse(root-left);// 2. 递归遍历左子树preOrderTraverse(root-right);// 3. 递归遍历右子树}4.1.2 中序遍历左 - 根 - 右第二次来到一个结点的时候打印访问顺序先递归中序遍历左子树再访问根节点最后递归中序遍历右子树。// 中序遍历递归版voidinOrderTraverse(BTree root){if(rootNULL){// 递归终止条件空树无需访问return;}inOrderTraverse(root-left);// 1. 递归遍历左子树printf(%d ,root-data);// 2. 访问根节点inOrderTraverse(root-right);// 3. 递归遍历右子树}4.1.3 后序遍历左 - 右 - 根第三次来到一个结点的时候打印访问顺序先递归后序遍历左子树再递归后序遍历右子树最后访问根节点。// 后序遍历递归版voidpostOrderTraverse(BTree root){if(rootNULL){// 递归终止条件空树无需访问return;}postOrderTraverse(root-left);// 1. 递归遍历左子树postOrderTraverse(root-right);// 2. 递归遍历右子树printf(%d ,root-data);// 3. 访问根节点}4.1.4 递归遍历模板voidf(BTree root){if(rootNULL)return;//1f(root.left);//2f(root.right);//3}//执行完第6行代码回到root才继续第8行代码//第八行执行完回到root后继续下面的代码下面没有代码了就结束这个f函数注意1、2、3位置都会回到根节点root4.1.5 递归序访问次序1、2、4、NULL、4、NULL、4、2、5、NULL、5、NULL、5、2、1、3、6、NULL、6、NULL、6、3、7、NULL、7、NULL、7、3、1最后一层的空结点只会来到一次而非空结点会来到3次4.1.6 完整可运行示例构建二叉树 遍历下面构建一个简单的二叉树如下所示并调用上述所有遍历函数验证运行结果1/\23/\45#includestdio.h#includestdlib.h#includestdbool.h/*————————————————————————————————————————————————————————————————————————————————————————*/// 定义二叉树节点结构体typedefstructBinaryTreeNode{intdata;structBinaryTreeNode*left;structBinaryTreeNode*right;}BTNode,*BTree;/*————————————————————————————————————————————————————————————————————————————————————————*/// 创建单个二叉树节点BTNode*createBTNode(intdata){BTNode*newNode(BTNode*)malloc(sizeof(BTNode));if(newNodeNULL){perror(malloc failed);exit(EXIT_FAILURE);}newNode-datadata;newNode-leftNULL;newNode-rightNULL;returnnewNode;}/*——————————————————————————————————————————————————————————————————————————————————————*/// 前序遍历递归版voidpreOrderTraverse(BTree root){if(rootNULL){return;}printf(%d ,root-data);preOrderTraverse(root-left);preOrderTraverse(root-right);}/*_______________________________________________________________________________________*/// 中序遍历递归版voidinOrderTraverse(BTree root){if(rootNULL){return;}inOrderTraverse(root-left);printf(%d ,root-data);inOrderTraverse(root-right);}/*______________________________________________________________________________________*/// 后序遍历递归版voidpostOrderTraverse(BTree root){if(rootNULL){return;}postOrderTraverse(root-left);postOrderTraverse(root-right);printf(%d ,root-data);}/*___________________________________________________________________________________*/// 释放二叉树内存后序遍历方式避免内存泄漏voidfreeBTree(BTree root){if(rootNULL){return;}freeBTree(root-left);freeBTree(root-right);free(root);}/*——————————————————————————————————————————————————————————————————————————————————*/intmain(){// 构建二叉树BTNode*rootcreateBTNode(1);root-leftcreateBTNode(2);root-rightcreateBTNode(3);root-left-leftcreateBTNode(4);root-left-rightcreateBTNode(5);// 遍历输出printf(前序遍历递归);preOrderTraverse(root);printf(\n);printf(中序遍历递归);inOrderTraverse(root);printf(\n);printf(后序遍历递归);postOrderTraverse(root);printf(\n);// 释放内存freeBTree(root);rootNULL;return0;}4.1.7 运行结果前序遍历递归12453中序遍历递归42513后序遍历递归452314.2 非递归遍历借助栈实现二叉树的非递归遍历核心是利用栈保存待访问的节点通过控制节点入栈、出栈的顺序以及访问节点数据的时机实现不同的遍历顺序这里使用了C中栈的一些函数文章最后补充了这些函数的C语言实现4.2.1 前序遍历根 - 左 - 右先访问根节点再将右孩子入栈最后左孩子入栈栈先进后出保证左孩子先被处理。classSolution{public:vectorintpreorderTraversal(TreeNode*root){stackTreeNode*st;vectorintresult;if(rootNULL)returnresult;st.push(root);while(!st.empty()){TreeNode*nodest.top();// 中st.pop();result.push_back(node-val);if(node-right)st.push(node-right);if(node-left)st.push(node-left);}returnresult;}};4.2.2 中序遍历左 - 根 - 右例如上图 递归序为1 2 4 空 4 5 6 空 6 空 6 空 6 5 空 5 4 2 7 空 7 空 2 1 3 空 3 8 9 10 空 10 空 10 9 空 9 8 空 8 3 1 中序遍历打印4 6 5 2 7 1 3 10 9 8 先将所有左孩子依次入栈直到左孩子为空再出栈访问节点最后处理右孩子核心将自己的左树处理完才到自己最后处理自己的右树将每棵子树的左边界压入栈中直到左边界为空栈顶结点弹出并打印以该节点为根节点的右树重复第一步循环退出条件没有子树且栈为空classSolution{public:vectorintinorderTraversal(TreeNode*root){vectorintresult;stackTreeNode*st;if(root!NULL){TreeNode*curroot;while(cur!NULL||!st.empty()){if(cur!NULL){st.push(cur);curcur-left;}else{curst.top();st.pop();result.push_back(cur-val);curcur-right;}}}returnresult;}};易错点cur入栈必须放在if(cur!NULL)内部否则会无条件重复入栈导致死循环和节点重复处理。4.2.3 后序遍历左 - 右 - 根有两种常用方式此处为双栈法核心思路用栈1按 根→左→右 顺序入栈前序变种出栈节点存入栈2最后栈2出栈即为 左→右→根 的后序结果。//这是 前序中 、右 、左入栈顺序classSolution{public:vectorintpreorderTraversal(TreeNode*root){stackTreeNode*st;vectorintresult;if(rootNULL)returnresult;st.push(root);while(!st.empty()){TreeNode*nodest.top();// 中st.pop();result.push_back(node-val);if(node-right)st.push(node-right);//右if(node-left)st.push(node-left);//左}returnresult;}};//这是 前序变种中、左 、右入栈顺序classSolution{public:vectorintpreorderTraversal(TreeNode*root){stackTreeNode*st;vectorintresult;if(rootNULL)returnresult;st.push(root);while(!st.empty()){TreeNode*nodest.top();// 中st.pop();result.push_back(node-val);if(node-left)st.push(node-left);//左if(node-right)st.push(node-right);//右//由上面变到下面交换了俩个if语句}returnresult;}};- 双栈法classSolution{public:vectorintpostorderTraversal(TreeNode*root){vectorintresult;stackTreeNode*st;stackTreeNode*collect;if(rootNULL)returnresult;//前 序按照中、左、右的顺序进栈st.push(root);while(!st.empty()){rootst.top();st.pop();//按照中、左、右进栈//按照中、右、左出栈//再按照中、右、左进入collect栈collect.push(root);if(root-left!NULL)st.push(root-left);if(root-right!NULL)st.push(root-right);}//从collect栈中一次弹出打印//此时打印顺序为左、右、中while(!collect.empty()){result.push_back(collect.top()-val);collect.pop();}returnresult;}};- 单栈法classSolution{public:vectorintpostorderTraversal(TreeNode*root){TreeNode*hroot;vectorintresult;stackTreeNode*st;if(h!NULL){st.push(h);//error:一定要记得将root先压入栈//st.push(h);将根节点入栈while(!st.empty()){TreeNode*curst.top();if(cur-left!NULLh!cur-lefth!cur-right){st.push(cur-left);}elseif(cur-right!NULLh!cur-right){st.push(cur-right);}else{result.push_back(cur-val);hcur;st.pop();}}}returnresult;}};4.2.4 单栈法后序遍历深度拆解1核心前提后序遍历要求先左、再右、最后根单栈法通过栈保存待处理节点标记节点h避免重复遍历子树。2关键变量解析TreeNode* h标记已完成左→右→根遍历的节点用于判断当前节点的子树是否已处理。TreeNode* cur获取栈顶节点判断其左右子树是否需要入栈。stackTreeNode* st存储待处理节点仅当节点左右子树均处理完毕后才出栈。3循环逻辑逐行拆解循环条件 while ( !st.empty( ) )栈为空时所有节点处理完毕。三个分支互斥严格遵循后序顺序1. 分支1压入左子节点条件cur有左子节点且左、右子节点均未被访问h≠左、h≠右。目的优先处理左子树符合先左要求。2. 分支2压入右子节点条件cur有右子节点且右子节点未被访问h≠右且分支1不满足左子树已处理。目的左子树处理完毕后处理右子树符合再右要求。3. 分支3访问当前节点条件左右子树均无或已处理。操作存入节点值更新h为当前节点标记已处理弹出节点。目的最后访问根节点符合最后根要求。4.2.5 补充C语言实现栈的基本操作函数//栈的基本操作函数//初始化栈栈顶指针置0空栈voidInitStackStack*s{s-top0;}//判断栈是否为空(t0p0表示无元素空栈)intIsStackEmpty(Stack*s){returns-top0;}//判断栈是否已满intIsStackFull(Stack*s){returns-topMax_stack_size;}//入栈操作:先存数据到当前top位置再topintPush(Stack*s,BTree node){if(IsStackFull(s)){printf(栈溢出入栈失败\n);return0;}s-data[s-top]node;s-top;return1;}//出栈操作先top--指向当前元素再取出数据//注意这里的node存储的的是返回的二叉树结点指针所以这里用了二级指针intPop(Stack*s,BTree*node){if(IsStackEmpty(s)){printf(栈为空出栈失败\n);return0;}s-top--;*nodes-data[s-top];//取出栈顶元素return1;}五、总结与拓展递归vs非递归递归简洁但有函数栈开销非递归手动控栈更高效适合大数据量场景。遍历应用前序遍历可用于二叉树复制中序遍历可用于二叉搜索树BST有序输出后序遍历可用于二叉树内存释放。拓展学习层序遍历BFS借助队列、二叉树的构建与销毁、节点查找与删除等操作均可基于遍历逻辑实现。本文代码均已实测可运行若有疑问或优化建议欢迎在评论区留言交流