二叉树是许多算法题的常用结构，其遍历算法的各种变种就是各种题目。具体的顺序如下：
- 先序遍历：先根、后左、再右
- 中序遍历：先左、后根、再右
- 后序遍历：先左、后右、再根
递归版先序、中序、后序遍历
最简单、最直接的版本
#include <iostream>
using namespace std;// 二叉树节点
struct Node
{int value;struct Node* left;struct Node* right;Node(int data) : value(data), left(nullptr), right(nullptr) {};
};// 先序遍历
void PreOrder(Node* head)
{if (head == nullptr)return;cout << head->value << " ";PreOrder(head->left);PreOrder(head->right);
}// 中序遍历
void InOrder(Node* head)
{if (head == nullptr)return;InOrder(head->left);cout << head->value << " ";InOrder(head->right);
}// 后序遍历
void PosOrder(Node* head)
{if (head == nullptr)return;PosOrder(head->left);PosOrder(head->right);cout << head->value << " ";
}int main()
{Node* n1 = new Node(1);Node* n2 = new Node(2);Node* n3 = new Node(3);Node* n4 = new Node(4);Node* n5 = new Node(5);n1->left = n2;n1->right = n3;n2->left = n4;n2->right = n5;PreOrder(n1);cout << endl;InOrder(n1);cout << endl;PosOrder(n1);cout << endl;delete n1;delete n2;delete n3;delete n4;delete n5;system("pause");return 0;
}
非递归版本
用递归方法解决的问题都能用非递归的方法来做，因为递归无非是使用了系统的函数栈来保存信息。我们自己申请一个栈来代替函数栈即可实现非递归方法。
先序遍历
先序遍历比较容易理解，首先将根节点入栈。从栈中取出栈顶节点，打印该点，接着先将右孩子入栈，再将左孩子入栈（因为栈的特点是先进后出，要先遍历左孩子就得后入栈）。不断重复该步骤直至栈为空。
void PreOrderUnRecur(Node* head)
{if (head){stack<Node*> stack;stack.push(head);Node* cur;while (!stack.empty()){cur = stack.top();stack.pop();cout << cur->value << " ";// 右孩子先进栈，后出if (cur->right)stack.push(cur->right);if (cur->left)stack.push(cur->left);}}
}
中序遍历
令cur等于head
步骤1：先把cur入栈，然后不停让cur=cur->left，重复此步骤。即把cur下的所有左孩子节点入栈。直到cur为空。
步骤2：从栈中弹出栈顶给cur，打印该节点，然后令cur=cur->right，回到步骤2。
步骤3：当栈为空时且cur为空时，过程结束。
入栈的顺序可参考下图：
void InOrderUnRecur(Node* head)
{if (head){stack<Node*> stack;Node* cur = head;while (!stack.empty() || cur != nullptr){while (cur != nullptr){stack.push(cur);cur = cur->left;}cur = stack.top();stack.pop();cout << cur->value << " ";cur = cur->right;}}
}
后序遍历
方法一：
申请两个栈s1、s2，先将头节点入栈s1。从s1中弹出栈顶节点记为cur，然后依次将cur的左孩子和右孩子压入s1。在这过程中每一个从s1中弹出的节点均压入s2。当s1为空后，从s2中依次弹出的节点便是后序遍历的次序。
主要就是利用两个栈来进行“倒腾“，压入s2的顺序为中、右、左，弹出的顺序就变成了左、右、中。
void PosOrderUnRecur(Node* head)
{if (head){stack<Node*> s1, s2;s1.push(head);Node* cur;while (!s1.empty()){cur = s1.top();s1.pop();s2.push(cur);if (cur->left)s1.push(cur->left);if (cur->right)s1.push(cur->right);}while (!s2.empty()){cout << s2.top()->value << " ";s2.pop();}}
}
方法二：
申请一个栈，将头节点压入栈。
现在我们思考一下：当遍历到一个节点时，如何判断这次遍历是打印该点，还是先处理它的孩子呢？
有以下几种情况：
- 该节点的左右孩子皆为空，即该节点为叶子节点，那么这次遍历就是打印该点。
- 如果上一次打印的节点为该节点的右孩子，说明该节点的子树处理完毕，这次遍历就是打印该点。
- 如果上一次打印的节点为该节点的左孩子，且该节点的右孩子为空，说明该节点的子树处理完毕，这次遍历就是打印该点。
- 否则说明子树没有被访问过，按照右孩子、左孩子的顺序入栈。
void PosOrderUnRecur(Node* head)
{if (head){stack<Node*> stack;stack.push(head);Node* last = nullptr;Node* top;while (!stack.empty()){top = stack.top();if ((top->left == nullptr && top->right == nullptr) || // 叶子节点(top->right == nullptr && last == top->left) || // 上个访问为左孩子，且右孩子为空last == top->right) // 上个访问为右孩子{cout << top->value << " ";last = top;stack.pop();}else{if (top->right)stack.push(top->right);if (top->left)stack.push(top->left);}}}
}
层次遍历
利用队列来做。
void LevelOrder(Node* head)
{if (head){queue<Node*> queue;queue.push(head);Node* cur;while (!queue.empty()){cur = queue.front();queue.pop();cout << cur->value << " ";if (cur->left)queue.push(cur->left);if (cur->right)queue.push(cur->right);}}
}
