共计 3966 个字符，预计需要花费 10 分钟才能阅读完成。
关注公众号: 高性能架构摸索。后盾回复【材料】，能够收费支付
俗话说：学如逆水行舟, 逆水行舟; 心似平原走马, 易放难收。这句话对程序员而言，领会更深。这行曾经越来越卷了，时刻筹备着，😃。
二叉树，在面试中，已是必备的开胃菜。而在二叉树相干的面试题目中，遍历更是常考题目。本文将从二叉树的遍历角度动手，从递归和非递归角度来剖析和解说二叉树的遍历。
遍历
二叉树的遍历是指从根节点登程，依照某种秩序顺次拜访二叉树中的所有节点，使每个节点被且仅被拜访一次。
二叉树的遍历，有 先序遍历 、 中序遍历 以及 后续遍历 三种。
下面三种遍历形式中的先序、中序以及后序三种形式，是父节点绝对于子节点来说的。如果父节点先于子节点，那么就是先序遍历。如果子节点先于父节点，那么就是后序遍历。而对于子节点来说，如果先左节点，而后是父节点，而后再是右节点，那么就是中序遍历。
如【图一】所示二叉树。其三种遍历后果如下：
先序遍历: A->B->D->E->C->F->G
中序遍历: D->B->E->A->F->C->G
后续遍历: D->E->B->F->G->C->A
为了便于了解代码，咱们先定义下树的节点定义：
struct TreeNode {
TreeNode *left;
TreeNode *right;
int val;
};先序遍历
定义：先拜访父节点，而后遍历左子树，最初遍历右子树。
递归
置信递归遍历大家都会很容易写进去，且 bugfree。因为实现代码很简略。
在上图【图二】中，应用递归遍历，就是将其左子树和右子树也当做一棵树来进行解决。代码如下：
void PreOrder(TreeNode *root) {if (!root) {return;}
// 遍历根节点(此处仅为输入，读者也能够依据理论须要进行解决，比方存储等)
std::cout << root->val << std::endl;
// 遍历左子树
PreOrder(root->left);
// 遍历右子树
PreOrder(root->right);
}非递归
在非递归操作中，咱们依然是依照先拜访根节点，而后遍历左子树，接着遍历右子树的形式。
- 达到节点 A, 拜访节点 A, 开始遍历 A 的左子树
- 达到节点 B，拜访节点 B，开始遍历 B 的左子树
-
达到节点 D, 拜访节点 D, 因为节点 D 无子树，因而节点 D 遍历实现
- 节点 D 遍历实现，意味着节点 B 的左子树遍历实现，因而接着遍历节点 B 的右子树
-
达到节点 E，拜访节点 E。因为节点 E 无子树，因而节点 E 遍历实现
- 节点 E 遍历实现，意味着节点 B 的右子树遍历实现，也预示着节点 B 的子树遍历实现
- 开始遍历节点 A 的右子树
- 达到节点 C，拜访节点 C。开始遍历 C 的左子树
-
达到节点 F，拜访节点 F。因为节点 F 无子树，因而节点 F 遍历实现
- 节点 F 遍历实现，意味着节点 C 的左子树遍历实现，因而开始遍历节点 C 的右子树
-
到的节点 G，拜访节点 G。因为节点 G 无子树，因而节点 G 遍历实现
- 节点 G 遍历实现，意味着节点 C 的右子树遍历实现，进而预示着节点 C 遍历实现
- 节点 C 遍历实现，意味着节点 A 的右子树遍历实现，进而意味着节点 A 遍历实现，因而以 A 为根节点的树遍历实现。
用非递归形式遍历二叉树，须要引入额定的数据结构栈(stack), 其根本流程如下：
1、申请一个栈 stack，而后将头节点压入 stack 中。
2、从 stack 中弹出栈顶节点，打印
3、将其右孩子节点（不为空的话）先压入 stack 中
4、将其左孩子节点（不为空的话）压入 stack 中。
5、一直反复步骤 2、3、4，直到 stack 为空，全副过程完结。
代码如下：
void PreOrder(TreeNode *root) {if (!root) {return;}
std::stack<TreeNode*> s;
s.push(root); // 步骤 1
while (!s.empty()) {auto t = s.top();
s.pop();// 出栈
std::cout << t->val << std::endl; // 拜访节点
if (t->right) {s.push(t->right); // 对应步骤 3
}
if (t->left) {s.push(t->left); // 对应步骤 4
}
}
}中序遍历
定义：先遍历左子树，拜访根节点，遍历右子树
递归
在上图【图四】中，应用递归遍历，就是将其左子树和右子树也当做一棵树来进行解决。代码如下：
void InOrder(TreeNode *root) {if (!root) {return;}
// 遍历左子树
InOrder(root->left);
// 遍历根节点(此处仅为输入，读者也能够依据理论须要进行解决，比方存储等)
std::cout << root->val << std::endl;
// 遍历右子树
InOrder(root->right);
}上述中序遍历的递归代码，相比于先序遍历，只是将拜访根节点的行为放在了遍历左右子树之间。
非递归
在非递归操作中，咱们依然是依照先遍历左子树，而后拜访根节点，最初遍历右子树的形式。
- 达到节点 A，节点 A 有左子树，遍历节点 A 的左子树
- 达到节点 B，节点 B 有左子树，遍历节点 B 的左子树
-
达到节点 D，节点 D 无子树，拜访 D 节点
- 因为 D 无子树，意味着 B 的左子树遍历实现，那么就回到 B 节点
- 拜访 B 节点，遍历 B 节点的右子树
-
达到节点 E，节点 E 无子树，拜访节点 E
- E 节点遍历实现，意味着以 B 为根的子树遍历实现，回到 A 节点
- 达到 A 节点，拜访 A 节点，遍历 A 节点的右子树
- 达到 C 节点，遍历 C 节点的左子树
-
达到 F 节点，因为 F 节点无子树，因而拜访 F 节点。
- 因为 F 节点无子树，意味着 C 节点的左子树遍历实现，回到 C 节点
- 达到 C 节点，拜访 C 节点，遍历 C 的右子树
-
达到节点 G，因为 G 无子树，因为拜访节点 G
- G 节点遍历实现，意味着 C 节点的右子树遍历实现，进而意味着 A 节点的右子树遍历实现，从意味着以 A 节点为根的二叉树遍历实现。
中序遍历，同样须要额定的辅助数据结构栈。
- 将根节点放入栈
2、如果根节点有左子树，则将左子树的根节点放入栈
3、反复步骤 1 和 2. 持续遍历左子树
4、从栈中弹出节点，进行拜访，而后遍历右子树(反复步骤 1 和 2)
5、如果栈为空，则遍历实现
代码如下：
void InOrder(TreeNode *root) {if (!root) {return;}
std::stack<TreeNode*> s;
auto p = root;
while (!s.empty() || p) {if (p) { // 步骤 1 和 2
s.push(p);
p = p->left;
} else { // 步骤 4
auto t = s.top();
std::cout << t->val << std::endl;
p = t->right;
}
}
}后续遍历
定义：先遍历左子树，再遍历右子树，最初拜访根节点
递归
void PostOrder(TreeNode *root) {if (!root) {return;}
// 遍历左子树
PostOrder(root->left);
// 遍历右子树
PostOrder(root->right);
// 遍历根节点(此处仅为输入，读者也能够依据理论须要进行解决，比方存储等)
std::cout << root->val << std::endl;
}下面就是后续遍历的递归写法，比拟写先序遍历、中序遍历以及后续遍历三者的递归遍历写法，大部分代码是一样的，惟一的区别就是 拜访根节点的代码地位 不一样：
先序遍历：先拜访根节点，而后遍历左子树，最初遍历右子树
中序遍历：先遍历左子树，而后拜访根节点，最初遍历右子树
后序遍历：先遍历左子树，而后遍历右子树，最初拜访根节点
非递归
在非递归操作中，咱们依然是依照先遍历左子树，而后拜访根节点，最初遍历右子树的形式。
- 达到节点 A，遍历 A 的左子树
- 达到节点 B，遍历 B 的左子树
-
达到节点 D，因为 D 无子树，则拜访节点 D
- 节点 D 无子树，意味着节点 B 的左子树遍历实现，接着遍历 B 的右子树
-
达到节点 E，因为 E 无子树，则拜访节点 E
- 节点 E 无子树，意味着节点 B 的右子树遍历实现，接回到节点 B
- 拜访节点 B，回到节点 B 的根节点 A
- 达到节点 A，拜访节点 A 的右子树
- 达到节点 C，遍历节点 C 的左子树
-
达到节点 F，因为节点 F 无子树，因而拜访节点 F
- 节点 F 拜访实现，意味着 C 节点的左子树遍历实现，因而回到节点 C
- 达到节点 C，遍历节点 C 的右子树
-
达到节点 G，因为节点 G 无子树，因为拜访节点 G
- 节点 G 拜访实现，意味着 C 节点的右子树遍历实现，回到节点 C
-
达到节点 C，拜访节点 C
- 节点 C 遍历实现，意味着节点 A 的右子树遍历实现，回到节点 A
- 节点 A 的右子树遍历实现，拜访节点 A
用非递归形式遍历二叉树，须要引入额定的数据结构栈(stack), 其根本流程如下：
1、申请两个栈 stack，而后将头节点压入指定 stack 中。
2、从 stack 中弹出栈顶节点，放入另外一个栈中
3、将其左孩子节点（不为空的话）先压入 stack 中
4、将其右孩子节点（不为空的话）压入 stack 中。
5、一直反复步骤 2、3、4，直到 stack 为空。
6、反复拜访另外一个栈，直至栈空
void PostOrder(TreeNode *root) {if (!root) {return;}
std::stack<TreeNode*> s1;
std::stack<TreeNode*> s2;
s1.push(root);
while (!s1.empty()) {auto t = s1.top();
s1.pop();
s2.push(t);
if (t->left) {s1.push(t->left);
}
if (t->right) {s1.push(t->right);
}
}
while (!s2.empty()) {auto t = s2.top();
s2.pop();
std::cout << t->val << std::endl;
}
}结语
对于二叉树来说，所谓的遍历，是指沿着某条路线顺次拜访每个节点，且均只做一次拜访。二叉树的遍历，是面试中常面算法之一，肯定要把其弄懂，必要的时候，须要背诵，乃至做到肌肉记忆。