二叉树后序遍历非递归实现

二叉树的遍历有递归实现的方式，前中后序遍历都非常直观易懂，缺点是递归始终是个开销可观的操作。非递归实现二叉树遍历不太易懂，尤其是后序遍历，这里把它记录下来以后回顾用。

二叉树后序遍历概念：对任一节点，它的左孩子总是先于它的右孩子被遍历到，它的右孩子总是先于该节点被遍历到。即是：左右中的顺序进行遍历。

算法和原理

感觉上看代码注释就能很好理解，树这种结构文字很难表述清楚。待我找到一个好的工具来画图，再看看能不能表达清楚～-～。建议读者自己在纸上模拟一次过程就能理解精髓了。主要是对二叉查找树的性质要够熟悉，其次对栈有基本的理解（先入后出）。

上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<stack>
#include"Header.h"
using namespace std;
// 二叉树插入的操作
void insert(Node<int>* root, int value) {
	if (root->val == value) {	// 拒绝重复的值
	}
	else if (root->val > value) {	// value在root左子树
		if (root->left == NULL) {	// root没有左子树，直接加一个节点
			root->left = new Node<int>();
			root->left->val = value;
			root->left->right = root->left->left = NULL;
			return;
		}
		insert(root->left, value);
	}
	else if (root->val < value) {   // value在root右子树
		if (root->right == NULL) {	// root没有右子树，直接加一个节点
			root->right = new Node<int>();
			root->right->val = value;
			root->right->right = root->right->left = NULL;
			return;
		}
		insert(root->right, value);
	}
}
int main() {
	Node<int>* root;			// 根节点
	Node<int>* tem;
	Node<int>* pre = NULL;      // pre 用来保存上一次弹出的节点的地址
	stack<Node<int>*> sta;		// 使用栈先入后出的特性来模拟遍历
	int n;
	int value;
	while (cin >> n) {
		cin >> value;
		root = new Node<int>();
		root->val = value;
		root->right = root->left = NULL;
		for (int i = 1; i < n; i++) {			// 输入一串数字，按逐个插入的原则，建二叉查找树，自己在纸上模拟下建个树更好理解
			cin >> value;
			insert(root, value);
		}
		while (!sta.empty()) sta.pop();		// 清空栈
		sta.push(root);
		pre = root;			// 这里将pre初始化为root，防止pre被更新前，任一节点的左右孩子之一是空导致判断复杂化。自己体会下
		while (!sta.empty()) {
			tem = sta.top();
			if (tem->left == pre || tem->right == pre || (!tem->left && !tem->right)) {	// 如果一个节点没有左右子节点，那么它作为根直接输出
				sta.pop();																// 如果它的左或右节点已经出过栈，说明它的左右子树都遍历过了，那么它也可以出栈了
				cout << tem->val << " ";												//  |
				pre = tem;																//  ↓
			}																			// 否则将它的左右节点入栈，刚好压在它头上。
			else {																		// 这就保证了如果一个节点root的左/右节点弹出（说明左右子树都遍历过了），那么当栈顶是root时，pre存的必然是它们之一。
				if (tem->right) {			// 先压入右节点，当然根节点是在右节点之前被压入过了。
					sta.push(tem->right);
				}
				if (tem->left) {			// 再压入左节点
					sta.push(tem->left);
				}							// 那就保证在出栈时，是按照左右中的顺序
			}
		}
	}
	return 0;
}

复杂度分析

时间复杂度：
O(n) 每个节点入栈一次出栈一次2n，没有额外的循环，常数去掉

空间复杂度：平均O(logn) 最坏O(n) 取决于二叉树的高度，如果是平衡二叉树那么就是O(logn)