C++遍历树，前中后序，递归非递归实现

文章目录

- - 前序遍历
  - 中序遍历
  - 后序遍历
  - 代码解释

前序遍历

递归思路：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。
非递归思路：使用栈来模拟递归过程。先将根节点入栈，之后循环执行以下操作：弹出栈顶元素并访问，若其右子节点存在则将右子节点入栈，若其左子节点存在则将左子节点入栈。

中序遍历

递归思路：先递归遍历左子树，接着访问根节点，最后递归遍历右子树。
非递归思路：利用栈。从根节点开始，持续将左子节点入栈，直至左子节点为空；接着弹出栈顶元素并访问，再将当前节点设为其右子节点，重复上述操作。

后序遍历

递归思路：先递归遍历左子树，再递归遍历右子树，最后访问根节点。
非递归思路：借助两个栈。第一个栈用于模拟递归调用，第二个栈用于存储最终的遍历结果。先将根节点压入第一个栈，之后循环：从第一个栈弹出节点并压入第二个栈，若该节点有左子节点则将左子节点压入第一个栈，若有右子节点则将右子节点压入第一个栈。最后从第二个栈依次弹出元素。

以下是完整的 C++ 代码实现：

#include <iostream>
#include <stack>
#include <vector>// 定义二叉树节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 前序遍历 - 递归
void preorderTraversalRecursive(TreeNode* root, std::vector<int>& result) {if (root == nullptr) return;result.push_back(root->val);preorderTraversalRecursive(root->left, result);preorderTraversalRecursive(root->right, result);
}// 前序遍历 - 非递归
std::vector<int> preorderTraversalIterative(TreeNode* root) {std::vector<int> result;if (root == nullptr) return result;std::stack<TreeNode*> stack;stack.push(root);while (!stack.empty()) {TreeNode* node = stack.top();stack.pop();result.push_back(node->val);if (node->right) stack.push(node->right);if (node->left) stack.push(node->left);}return result;
}// 中序遍历 - 递归
void inorderTraversalRecursive(TreeNode* root, std::vector<int>& result) {if (root == nullptr) return;inorderTraversalRecursive(root->left, result);result.push_back(root->val);inorderTraversalRecursive(root->right, result);
}// 中序遍历 - 非递归
std::vector<int> inorderTraversalIterative(TreeNode* root) {std::vector<int> result;std::stack<TreeNode*> stack;TreeNode* current = root;while (current != nullptr || !stack.empty()) {while (current != nullptr) {stack.push(current);current = current->left;}current = stack.top();stack.pop();result.push_back(current->val);current = current->right;}return result;
}// 后序遍历 - 递归
void postorderTraversalRecursive(TreeNode* root, std::vector<int>& result) {if (root == nullptr) return;postorderTraversalRecursive(root->left, result);postorderTraversalRecursive(root->right, result);result.push_back(root->val);
}// 后序遍历 - 非递归
std::vector<int> postorderTraversalIterative(TreeNode* root) {std::vector<int> result;if (root == nullptr) return result;std::stack<TreeNode*> stack1, stack2;stack1.push(root);while (!stack1.empty()) {TreeNode* node = stack1.top();stack1.pop();stack2.push(node);if (node->left) stack1.push(node->left);if (node->right) stack1.push(node->right);}while (!stack2.empty()) {result.push_back(stack2.top()->val);stack2.pop();}return result;
}// 辅助函数：打印结果
void printResult(const std::vector<int>& result) {for (int val : result) {std::cout << val << " ";}std::cout << std::endl;
}int main() {// 构建一个简单的二叉树TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);std::vector<int> result;// 前序遍历std::cout << "Preorder Traversal (Recursive): ";preorderTraversalRecursive(root, result);printResult(result);result.clear();std::cout << "Preorder Traversal (Iterative): ";result = preorderTraversalIterative(root);printResult(result);result.clear();// 中序遍历std::cout << "Inorder Traversal (Recursive): ";inorderTraversalRecursive(root, result);printResult(result);result.clear();std::cout << "Inorder Traversal (Iterative): ";result = inorderTraversalIterative(root);printResult(result);result.clear();// 后序遍历std::cout << "Postorder Traversal (Recursive): ";postorderTraversalRecursive(root, result);printResult(result);result.clear();std::cout << "Postorder Traversal (Iterative): ";result = postorderTraversalIterative(root);printResult(result);// 释放内存delete root->left->left;delete root->left->right;delete root->left;delete root->right;delete root;return 0;
}

代码解释

TreeNode 结构体：用于定义二叉树的节点，包含节点的值、左子节点指针和右子节点指针。
递归遍历函数：preorderTraversalRecursive、inorderTraversalRecursive 和 postorderTraversalRecursive 分别实现了前序、中序和后序遍历的递归版本。
非递归遍历函数：preorderTraversalIterative、inorderTraversalIterative 和 postorderTraversalIterative 分别实现了前序、中序和后序遍历的非递归版本。
printResult 函数：用于打印遍历结果。
main 函数：构建一个简单的二叉树，调用各个遍历函数并打印结果，最后释放二叉树占用的内存。