二叉树遍历包括前序、中序、后序和层序四种，可通过递归或迭代实现。前序遍历先访问根节点，再左子树、右子树；中序是左→根→右；后序为左→右→根；层序按层级从上到下、每层从左到右访问节点。递归实现简洁直观，迭代则借助栈或队列模拟过程，其中前序迭代使用栈并优先压入右子树，中序持续向左入栈后回退访问，后序较复杂需标记已访问节点或双栈辅助，层序遍历利用队列实现，可记录每层节点数以分行输出。
二叉树的遍历是数据结构中的基础操作，C++中可以通过递归或迭代的方式实现。常见的遍历方式有三种：前序、中序和后序，再加上层序遍历，共四种。下面详细介绍每种遍历的实现方法。
前序、中序、后序遍历（递归实现）
定义二叉树节点结构后，递归遍历非常直观。顺序区别在于“根”的处理时机：
前序遍历：先访问根节点，再遍历左子树，最后右子树（根→左→右）中序遍历：先遍历左子树，再访问根节点，最后右子树（左→根→右）后序遍历：先遍历左子树，再右子树，最后访问根节点（左→右→根）
代码示例：
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};// 前序遍历void preorder(TreeNode* root) {if (!root) return;cout <val <left);preorder(root->right);}
// 中序遍历void inorder(TreeNode* root) {if (!root) return;inorder(root->left);cout <val <right);}
// 后序遍历void postorder(TreeNode* root) {if (!root) return;postorder(root->left);postorder(root->right);cout <val << " ";}
前中后序遍历（迭代实现）
使用栈模拟递归过程，可以避免函数调用开销，也便于理解执行流程。
立即学习“C++免费学习笔记（深入）”；
前序迭代：
利用栈，先压入右子树再压左子树，保证左子树先出栈。
void preorderIterative(TreeNode* root) { if (!root) return; stack stk; stk.push(root); while (!stk.empty()) { TreeNode* node = stk.top(); stk.pop(); cout <val <right) stk.push(node->right); if (node->left) stk.push(node->left); }}
中序迭代：
一直向左走到底，路径上节点入栈，到空时回退并访问，再转向右子树。
void inorderIterative(TreeNode* root) { stack stk; TreeNode* curr = root; while (curr || !stk.empty()) { while (curr) { stk.push(curr); curr = curr->left; } curr = stk.top(); stk.pop(); cout <val <right; }}
后序迭代：
较复杂，可借助两个栈，或使用一个栈配合“上次访问节点”标记。
void postorderIterative(TreeNode* root) { if (!root) return; stack stk; TreeNode* lastVisited = nullptr; TreeNode* curr = root; while (curr || !stk.empty()) { if (curr) { stk.push(curr); curr = curr->left; } else { TreeNode* peekNode = stk.top(); if (peekNode->right && lastVisited != peekNode->right) { curr = peekNode->right; } else { cout <val << " "; lastVisited = stk.top(); stk.pop(); } } }}
层序遍历（广度优先）
使用队列实现，按层级从上到下、从左到右访问节点。
void levelOrder(TreeNode* root) { if (!root) return; queue q; q.push(root); while (!q.empty()) { TreeNode* node = q.front(); q.pop(); cout <val <left) q.push(node->left); if (node->right) q.push(node->right); }}
若需按层输出（每层一行），可在循环内记录当前层节点数：
void levelOrderPerLevel(TreeNode* root) { if (!root) return; queue q; q.push(root); while (!q.empty()) { int levelSize = q.size(); for (int i = 0; i < levelSize; ++i) { TreeNode* node = q.front(); q.pop(); cout <val <left) q.push(node->left); if (node->right) q.push(node->right); } cout << endl; // 每层换行 }}
基本上就这些。掌握递归与迭代的写法，能应对大多数面试和工程场景。迭代写法虽然稍复杂，但有助于深入理解遍历逻辑。实际开发中可根据需求选择合适方式。
以上就是C++怎么实现二叉树的遍历_C++数据结构与二叉树遍历算法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1484633.html
微信扫一扫 
支付宝扫一扫 
