二叉树遍历：C++ 实现指南

二叉树是计算机科学中一个基础且重要的数据结构，广泛应用于算法和各种应用中。掌握二叉树的遍历是学习数据结构的关键一步。本文将详细介绍二叉树的前序、中序和后序遍历，使用C++语言编写，适合新手入门。

什么是二叉树？

二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。它具有以下特点：
- 每个节点至多有两个子节点。
- 节点的子节点分为左子节点和右子节点。
- 左子节点的值总是小于或等于它的父节点的值。
- 右子节点的值总是大于或等于它的父节点的值。

二叉树的遍历

二叉树的遍历指的是按照某种顺序访问树中的每个节点，使得每个节点都被访问一次。常见的遍历方式有三种：前序遍历、中序遍历和后序遍历。

1. 前序遍历（Pre-order Traversal）

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

步骤：
1. 访问根节点。
2. 遍历左子树。
3. 遍历右子树。

2. 中序遍历（In-order Traversal）

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

步骤：
1. 遍历左子树。
2. 访问根节点。
3. 遍历右子树。

3. 后序遍历（Post-order Traversal）

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

步骤：
1. 遍历左子树。
2. 遍历右子树。
3. 访问根节点。

二叉树节点定义

首先，我们需要定义一个二叉树节点的结构体：

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

前序遍历（Pre-order Traversal）

void preOrderTraversal(TreeNode* root) {if (root == nullptr) return;std::cout << root->val << " ";preOrderTraversal(root->left);preOrderTraversal(root->right);
}

中序遍历（In-order Traversal）

void inOrderTraversal(TreeNode* root) {if (root == nullptr) return;inOrderTraversal(root->left);std::cout << root->val << " ";inOrderTraversal(root->right);
}

后序遍历（Post-order Traversal）

void postOrderTraversal(TreeNode* root) {if (root == nullptr) return;postOrderTraversal(root->left);postOrderTraversal(root->right);std::cout << root->val << " ";
}

迭代前序遍历

#include <stack>
void iterativePreOrderTraversal(TreeNode* root) {if (!root) return;std::stack<TreeNode*> stack;stack.push(root);while (!stack.empty()) {TreeNode* node = stack.top();stack.pop();std::cout << node->val << " ";if (node->right) stack.push(node->right);if (node->left) stack.push(node->left);}
}

迭代中序遍历

void iterativeInOrderTraversal(TreeNode* root) {if (!root) return;std::stack<TreeNode*> stack;TreeNode* current = root;while (current || !stack.empty()) {while (current) {stack.push(current);current = current->left;}current = stack.top();stack.pop();std::cout << current->val << " ";current = current->right;}
}

迭代后序遍历

void iterativePostOrderTraversal(TreeNode* root) {if (!root) return;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()) {std::cout << stack2.top()->val << " ";stack2.pop();}
}

主函数示例

int main() {// 创建一个简单的二叉树//       1//      / \//     2   3//    / \//   4   5TreeNode* 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::cout << "Pre-order Traversal: ";preOrderTraversal(root);std::cout << std::endl;std::cout << "In-order Traversal: ";inOrderTraversal(root);std::cout << std::endl;std::cout << "Post-order Traversal: ";postOrderTraversal(root);std::cout << std::endl;// 迭代遍历std::cout << "Iterative Pre-order Traversal: ";iterativePreOrderTraversal(root);std::cout << std::endl;std::cout << "Iterative In-order Traversal: ";iterativeInOrderTraversal(root);std::cout << std::endl;std::cout << "Iterative Post-order Traversal: ";iterativePostOrderTraversal(root);std::cout << std::endl;return 0;
}

结语

通过本文的介绍，你应该对二叉树的遍历有了基本的了解。无论是前序、中序还是后序遍历，理解其访问顺序是关键。希望这篇文章能够帮助你入门二叉树遍历，并在实际编程中灵活运用。记住，实践是最好的老师，多写代码，多思考，你将更深入地掌握这一技能。