二叉树遍历递归/非递归模板（？？）

110 阅读 0 评论 73 点赞

我是靠谱客的博主幽默路人，这篇文章主要介绍二叉树遍历递归/非递归模板（？？），现在分享给大家，希望可以做个参考。

递归版

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void First_order_traversal(int i) //先序
{
	printf("%dn", key[i]);
	First_order_traversal(lc[i]);
	First_order_traversal(rc[i]);
}
void Sequential_traversal(int i) //中序
{
	Sequential_traversal(lc[i]);
	printf("%dn", key[i]);
	Sequential_traversal(rc[i]);
}
void Post_order_traversal(int i) //后序
{
	Post_order_traversal(lc[i]);
	Post_order_traversal(rc[i]);
	printf("%dn", key[i]);
}

非递归版

复制代码

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
int vis[MAXN], lc[MAXN], rc[MAXN], key[MAXN];
void First_order_traversal(int i)
{
	stack<int> st;
	st.push(i);
	while(!st.empty())
	{
		i = st.top(); st.pop();
		printf("%dn", key[i]);
		if(rc[i]) st.push(rc[i]);
		if(lc[i]) st.push(lc[i]);
	}
}
void Sequential_traversal(int i)
{
	stack<int> st;
	st.push(i);
	while(!st.empty())
	{
		if(!(i=st.top())) { st.pop(); continue; }
		i = st.top(); vis[i]++;
		if(vis[i] == 1) st.push(lc[i]);
		else if(vis[i] == 2) printf("%dn", key[i]), st.push(rc[i]);
		else st.pop();
	}
}
void Post_order_traversal(int i)
{
	stack<int> st;
	st.push(i);
	while(!st.empty())
	{
		if(!(i=st.top())) { st.pop(); continue; }
		vis[i]++;
		if(vis[i] == 1) st.push(lc[i]);
		else if(vis[i] == 2) st.push(rc[i]);
		else printf("%dn", key[i]), st.pop();
	}
}