二叉树的非递归遍历 | 秋招面试必备

前言

本文将详细介绍二叉树的非递归遍历的实现方法，利用迭代循环实现二叉树的不同遍历方式。
如果在开始前，已掌握递归遍历二叉树的方法，理解栈帧的建立和销毁过程，能够更容易上手迭代写法。

基础设置

下面的函数均为类BinaryTree的成员函数，_root为类的成员变量，在构造函数中初始化为二叉树的根节点。

二叉树节点声明如下：

struct TreeNode {TreeNode(int d = 1) : left(nullptr), right(nullptr), data(d){}TreeNode* left;TreeNode* right;int data;
};

前序遍历

前序遍历，即按照“根左右”顺序遍历二叉树。迭代法的核心是使用栈记录将要遍历到的树的节点，而栈具有“后进先出”的特性，所以为满足先访问左子树，在访问右子树的要求，则节点的入栈顺序为==“右左”==。
初学时，节点入栈的顺序，容易与递归遍历“根左右”顺序混淆。因为在循环体中，没有完全按照“右左根”顺序进行处理，依然是先处理了根节点。这就需要辩证的看待“根”这一概念，当前处理的根节点也可以是某一节点的左子树（右子树）。学习迭代遍历法时，选择性地规避“根”节点的概念，可能更好理解。

每次循环的栈顶，都为将要处理的根节点，然后再处理右子树（若不为空）、左子树（若不为空）。

void PreorderIt() {if (_root == nullptr) {return;}std::stack<TreeNode*> s;s.push(_root);while (!s.empty()) {TreeNode* cur = s.top();s.pop();std::cout << cur->data << ' ';if (cur->right != nullptr) {s.push(cur->right);}if (cur->left != nullptr) {s.push(cur->left);}}return;
}

也可以显示使用一个指针cur，以表示当前要处理的根节点。

void PreorderItV2() {if (_root == nullptr) {return;}std::stack<TreeNode*> s;TreeNode* cur = _root;while (!s.empty() || cur != nullptr) {if (cur == nullptr) {cur = s.top();s.pop();}std::cout << cur->data << ' ';if (cur->right != nullptr) {s.push(cur->right);}cur = cur->left;}return;
}

中序遍历

迭代法中序遍历处理节点的顺序与“左根右”顺序一致，处理所有的左子树，然后访问根节点，最后处理右子树。

void InorderIt() {if (_root == nullptr) {return;}TreeNode* cur = _root;std::stack<TreeNode*> s;while (!s.empty() || cur != nullptr) {// 入栈所有的左子树while (cur != nullptr) {s.push(cur);cur = cur->left;}// 访问根节点cur = s.top();s.pop();std::cout << cur->data << ' ';// 处理右子树cur = cur->right;}return;
}

后序遍历

法一

遵循“左右根”顺序，迭代法也需要先处理左子树、右子树，最后是根节点。但是左右子树需要经过根节点中转（会访问两次），为避免反复访问一侧子树的节点，我们可以加入一个哨兵节点dummy，记录已经处理过的子树，从而解决死循环的问题。

void PostorderIt() {if (_root == nullptr) {return;}TreeNode* cur = _root;TreeNode* dummy = nullptr;std::stack<TreeNode*> s;while (!s.empty() || cur != nullptr) {// 处理左子树while (cur != nullptr) {s.push(cur);cur = cur->left;}cur = s.top();// 右子树存在 且 没有访问过if (cur->right && cur->right != dummy) { // 处理右子树cur = cur->right;}else {std::cout << cur->data << ' ';dummy = cur;s.pop();cur = nullptr; // 一定需要置空，避免反复处理左子树}}
}

法二

后序遍历原为“左右根”，那么如果按照“根右左”的顺序访问节点并逆序输出，那么也能得到相同的效果。【两次逆序，负负得正】

void PostorderItV2() {if (_root == nullptr) {return;}std::vector<int> res;std::stack<TreeNode*> s;s.push(_root);while (!s.empty()) {TreeNode* cur = s.top();s.pop();res.push_back(cur->data);if (cur->left != nullptr) {s.push(cur->left);}if (cur->right != nullptr) {s.push(cur->right);}}std::reverse(res.begin(), res.end());for (auto num : res) {std::cout << num << ' ';}return;
}