C++ 二叉树遍历递归与非递归_C++树形结构操作详解-C++-PHP中文网

C++ 二叉树遍历递归与非递归_C++树形结构操作详解

尼克

发布： 2025-12-04 10:45:43

原创

856人浏览过

二叉树遍历的核心在于理解递归与非递归实现。前序、中序、后序遍历分别按根-左-右、左-根-右、左-右-根顺序访问节点。递归写法简洁，非递归借助栈模拟调用过程，避免深度过大导致的栈溢出。前序非递归先压右后压左；中序需沿左链入栈再转向右子树；后序可用双栈法或逆序输出辅助栈。掌握这些方法有助于灵活应对树形结构操作问题。

c++ 二叉树遍历递归与非递归_c++树形结构操作详解

二叉树的遍历是C++数据结构中的核心内容，掌握其递归与非递归实现方式对理解树形结构操作至关重要。常见的遍历方式包括前序、中序和后序三种，每种都有对应的递归和非递归写法。递归写法简洁直观，非递归则依赖栈模拟调用过程，更贴近底层运行机制。

前序遍历（根-左-右）

递归实现：先访问根节点，再递归遍历左子树和右子树。

void preorder(TreeNode* root) {
   if (!root) return;
   cout val    preorder(root->left);
   preorder(root->right);
}

非递归实现：使用栈保存待访问节点。每次弹出栈顶并访问，然后先压入右子树，再压入左子树，确保左子树优先处理。

void preorder_iterative(TreeNode* root) {
   if (!root) return;
   stack<TreeNode*> s;
   s.push(root);
   while (!s.empty()) {
      TreeNode* node = s.top(); s.pop();
      cout val       if (node->right) s.push(node->right);
      if (node->left) s.push(node->left);
   }
}

中序遍历（左-根-右）

递归实现：先递归访问左子树，再处理根节点，最后递归右子树。

立即学习“C++免费学习笔记（深入）”；

void inorder(TreeNode* root) {
   if (!root) return;
   inorder(root->left);
   cout val    inorder(root->right);
}

非递归实现：从根节点开始，不断将左子节点压栈直到为空。然后弹出栈顶访问，并转向其右子树重复该过程。

DubbingX智声云配

多情绪免费克隆AI音频工具

975

查看详情

void inorder_iterative(TreeNode* root) {
   stack<TreeNode*> s;
   TreeNode* curr = root;
   while (curr || !s.empty()) {
      while (curr) {
         s.push(curr);
         curr = curr->left;
      }
      curr = s.top(); s.pop();
      cout val       curr = curr->right;
   }
}

后序遍历（左-右-根）

递归实现：先处理左右子树，最后访问根节点。

void postorder(TreeNode* root) {
   if (!root) return;
   postorder(root->left);
   postorder(root->right);
   cout val }

非递归实现：较为复杂，可通过两个栈或标记法实现。使用双栈时，第一个栈按“根-左-右”入栈顺序弹出并压入第二个栈，最终从第二个栈弹出即为后序结果。

void postorder_iterative(TreeNode* root) {
   if (!root) return;
   stack<TreeNode*> s1, s2;
   s1.push(root);
   while (!s1.empty()) {
      TreeNode* node = s1.top(); s1.pop();
      s2.push(node);
      if (node->left) s1.push(node->left);
      if (node->right) s1.push(node->right);
   }
   while (!s2.empty()) {
      cout val       s2.pop();
   }
}

另一种方法是使用单栈配合前驱节点判断，逻辑更紧凑但理解难度稍高。

层序遍历（广度优先）

虽然不属于深度优先范畴，但作为树的重要遍历方式也常被提及。使用队列实现，逐层访问节点。

void levelorder(TreeNode* root) {
   if (!root) return;
   queue<TreeNode*> q;
   q.push(root);
   while (!q.empty()) {
      TreeNode* node = q.front(); q.pop();
      cout val       if (node->left) q.push(node->left);
      if (node->right) q.push(node->right);
   }
}

基本上就这些。理解各种遍历的本质差异和栈的作用机制，能帮助你在实际编程中灵活选择合适的方法。递归适合思维清晰表达，非递归更适合控制执行流程和避免栈溢出问题。

以上就是C++ 二叉树遍历递归与非递归_C++树形结构操作详解的详细内容，更多请关注php中文网其它相关文章！