详细讲解C++中二叉树的遍历：前序、中序、后序遍历
在二叉树中，节点的遍历有三种方式：前序遍历、中序遍历、后序遍历。其中，前序遍历、中序遍历、后序遍历分别对应节点的遍历顺序：先遍历根节点，再遍历左子树和右子树；先遍历左子树，再遍历根节点和右子树；先遍历左子树和右子树，再遍历根节点。
在 C++ 中，我们可以使用递归和迭代两种方式来实现二叉树的遍历。下面我们分别介绍这两种方式实现前序、中序、后序遍历的具体方法。
递归实现
递归是二叉树遍历的一种常用方法，其实现代码相对简单。具体实现方法如下：
（1）前序遍历
void preorderTraversal(TreeNode* root) {
if (root == nullptr) return;
cout << root->val << " "; // 访问根节点
preorderTraversal(root->left); // 遍历左子树
preorderTraversal(root->right); // 遍历右子树
}中序遍历
void inorderTraversal(TreeNode* root) {
if (root == nullptr) return;
inorderTraversal(root->left); // 遍历左子树
cout << root->val << " "; // 访问根节点
inorderTraversal(root->right); // 遍历右子树
}后序遍历
void postorderTraversal(TreeNode* root) {
if (root == nullptr) return;
postorderTraversal(root->left); // 遍历左子树
postorderTraversal(root->right); // 遍历右子树
cout << root->val << " "; // 访问根节点
}迭代实现
在迭代实现中，我们需要使用栈来存储节点，以便在遍历完左子树后能够回到其父节点，进而遍历右子树。具体实现方法如下：
（1）前序遍历
void preorderTraversal(TreeNode* root) {
if (root == nullptr) return;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
cout << node->val << " ";
if (node->right != nullptr) s.push(node->right); // 右子树先入栈
if (node->left != nullptr) s.push(node->left); // 左子树后入栈，保证遍历顺序
}
}中序遍历
void inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* node = root;
while (node != nullptr || !s.empty()) {
while (node != nullptr) {
s.push(node);
node = node->left;
}
node = s.top();
s.pop();
cout << node->val << " ";
node = node->right;
}
}
（3）后序遍历
在迭代实现中，后序遍历比前序遍历和中序遍历要复杂一些，因为在访问节点之前需要先访问其左右子树。具体实现方法如下：
```c++
void postorderTraversal(TreeNode* root) {
if (root == nullptr) return;
stack<TreeNode*> s1, s2;
s1.push(root);
while (!s1.empty()) {
TreeNode* node = s1.top();
s1.pop();
s2.push(node); // 将访问过的节点压入 s2 栈
if (node->left != nullptr) s1.push(node->left); // 左子树先入栈
if (node->right != nullptr) s1.push(node->right); // 右子树后入栈，保证遍历顺序
}
while (!s2.empty()) {
cout << s2.top()->val << " "; // 访问 s2 栈中的节点，即后序遍历结果
s2.pop();
}
}以上就是 C++ 中二叉树的前序、中序、后序遍历的递归和迭代实现方法。需要注意的是，迭代实现中需要借助栈来存储节点，而递归实现则不需要额外的数据结构。
另外，还有一种 Morris 遍历方法，可以实现二叉树的前序、中序、后序遍历，并且不需要使用额外的数据结构（如栈）。其基本思想是利用线索二叉树的概念，将节点的右孩子指向后继节点，这样可以在遍历完左子树之后回到当前节点，从而避免使用栈。
（1）Morris 前序遍历
Morris 前序遍历的基本思路是：对于当前节点，如果其左子节点为空，直接输出该节点的值，并将当前节点指向右子节点；如果其左子节点不为空，找到其左子树的最右节点，并将该节点的右子节点指向当前节点，然后输出当前节点的值，并将当前节点指向其左子节点。这样可以保证在回溯时可以回到当前节点，并继续遍历右子树。
void morrisPreorderTraversal(TreeNode* root) {
if (root == nullptr) return;
TreeNode* cur = root;
while (cur != nullptr) {
if (cur->left == nullptr) { // 左子树为空，直接输出节点值并向右子树遍历
cout << cur->val << " ";
cur = cur->right;
} else {
// 找到左子树的最右节点
TreeNode* pre = cur->left;
while (pre->right != nullptr && pre->right != cur) pre = pre->right;
if (pre->right == nullptr) { // 为了能在回溯时回到当前节点，需要在最右节点处建立一个临时指针
cout << cur->val << " ";
pre->right = cur;
cur = cur->left;
} else { // 说明已经遍历过该节点的左子树，需要断开临时指针，并向右子树遍历
pre->right = nullptr;
cur = cur->right;
}
}
}
}（2）Morris 中序遍历
Morris 中序遍历的基本思路是：对于当前节点，如果其左子节点为空，直接输出该节点的值，并将当前节点指向右子节点；如果其左子节点不为空，找到其左子树的最右节点，并将该节点的右子节点指向当前节点，然后将当前节点指向其左子节点。这样可以保证可以在回溯时回到当前节点，并输出节点值。
Morris 中序遍历是一种不使用递归和栈的方式实现二叉树中序遍历的方法。该方法利用了 Morris 遍历的思想，即对于当前节点，如果其左子树不为空，就找到其左子树的最右节点，并将该节点的右子节点指向当前节点，这样就可以在遍历完左子树后回到当前节点，而不需要使用栈保存遍历的路径。
具体来说，Morris 中序遍历的实现步骤如下：
初始化当前节点为根节点 root。
如果当前节点的左子节点为空，输出当前节点的值，并将当前节点更新为其右子节点。
如果当前节点的左子节点不为空，则找到其左子树的最右节点，即左子树中最后一个节点，记为predecessor。
如果predecessor的右子节点为空，将其右子节点指向当前节点，然后将当前节点更新为其左子节点。
如果predecessor的右子节点为当前节点，说明左子树已经遍历完毕，输出当前节点的值，然后将predecessor的右子节点重置为空，并将当前节点更新为其右子节点。
重复2-5步，直到当前节点为空。
实现过程中需要注意的是，由于 Morris 中序遍历会修改二叉树的结构，因此需要在遍历完当前节点的左子树之后，将修改过的节点恢复为原始状态。这可以通过在遍历完左子树之后，再次访问当前节点时，将predecessor的右子节点重置为空实现。
下面是 Morris 中序遍历的具体实现代码：
void morrisInorderTraversal(TreeNode* root) {
TreeNode* cur = root;
while (cur != nullptr) {
if (cur->left == nullptr) {
cout << cur->val << " ";
cur = cur->right;
} else {
TreeNode* predecessor = cur->left;
while (predecessor->right != nullptr && predecessor->right != cur) {
predecessor = predecessor->right;
}
if (predecessor->right == nullptr) {
predecessor->right = cur;
cur = cur->left;
} else {
predecessor->right = nullptr;
cout << cur->val << " ";
cur = cur->right;
}
}
}
}Morris 中序遍历的时间复杂度为 O(n)，空间复杂度为 O(1)，因此在某些情况下，它比使用栈实现的中序遍历更加高效。但需要注意的是，Morris 中序遍历的代码较为复杂，可读性较差，因此在实际应用中需要根据实际情况选择合适的遍历方式。
（3）Morris 后序遍历
Morris 后序遍历的基本思路是：对于当前节点，如果其左子节点为空，直接将当前节点指向右子节点；如果其左子节点不为空，找到其左子树的最右节点，并将该节点的右子节点指向当前节点，然后将当前节点指向其左子节点。这样可以保证可以在回溯时回到当前节点，并按照右、左、根的顺序输出节点值。
与 Morris 前序遍历和 Morris 中序遍历不同，Morris 后序遍历需要在遍历完左子树时反转路径，然后输出路径上的节点值，最后再将路径反转回来。
void reversePath(TreeNode* from, TreeNode* to) {
if (from == to) return;
TreeNode* x = from;
TreeNode* y = from->right;
while (x != to) {
TreeNode* z = y->right;
y->right = x;
x = y;
y = z;
}
}
void printReversePath(TreeNode* from, TreeNode* to) {
reversePath(from, to);
TreeNode* p = to;
while (true) {
cout << p->val << " ";
if (p == from) break;
p = p->right;
}
reversePath(to, from);
}
void morrisPostorderTraversal(TreeNode* root) {
if (root == nullptr) return;
TreeNode dummy(0);
dummy.left = root;
TreeNode* cur = &dummy;
while (cur != nullptr) {
if (cur->left == nullptr) {
cur = cur->right;
} else {
TreeNode* pre = cur->left;
while (pre->right != nullptr && pre->right != cur) pre = pre->right;
if (pre->right == nullptr) {
pre->right = cur;
cur = cur->left;
} else {
printReversePath(cur->left, pre);
pre->right = nullptr;
cur = cur->right;
}
}
}
}以上就是二叉树的三种基本遍历方式，以及 Morris 遍历的介绍和实现。需要注意的是，递归方法和迭代方法在空间复杂度上的差别比较大，如果二叉树比较大的话，递归方法可能会导致栈溢出。此外，Morris 遍历虽然可以不使用额外的数据结构，但其代码可读性较差，且实际运行效率也不一定比使用栈更高。因此，在实际应用中需要根据实际情况选择合适的遍历方式。
