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

前言

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

基础设置

下面的函数均为类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;
}