树的遍历（非递归）

发表于 | 分类于 | 阅读数

前言

太菜了，树的遍历忘的一干二净。上机时脑子空荡荡，知识在垃圾堆。特别写一篇博客理一下。

前序遍历

三种遍历方式中算法最为简单的一个，一直向左遍历，将遍历到的点输出，如果有右节点，就进入右节点，开始新一轮循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void preoder(BT* T)
{
	if (!T) return;
	ST stack1;
	stack1.top = 0;
	BT* p = T;
	while (stack1.top || p)
	{
		while (p)
		{
			printf("%c ",p->data);
			stack1.t[stack1.top++] = p;
			p = p->left;
		}
		if (stack1.top)
		{
			p = stack1.t[--stack1.top];
			p = p->right;
		}
	}
	printf("\n");
}

中序遍历

和前序遍历类似，只是输出的位置要做更改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void inoder(BT* T)
{
	if (!T) return;
	ST stack1;
	stack1.top = 0;
	BT* p = T;
	while (p || stack1.top)
	{
		while (p)
		{
			stack1.t[stack1.top++] = p;
			p = p->left;
		}
		if (stack1.top)
		{
			p = stack1.t[--stack1.top];
			printf("%c ", p->data);
			p = p->right;
		}
	}
	printf("\n");
}

后序遍历

后序稍稍麻烦，需要判断上次访问的节点是位于左子树，还是右子树。若是位于左子树，则需跳过根节点，先进入右子树，再回头访问根节点；若是位于右子树，则直接访问根节点。

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
void postorder(BT* T)
{
	ST stack1;
	stack1.top = 0;
	BT* p, * p1;
	p = T;
	do
	{
		while (p)
		{
			stack1.t[stack1.top++] = p;
			p = p->left;
		}
		p1 = NULL;
		while (stack1.top)
		{
			p = stack1.t[stack1.top - 1];
			if (p->right == p1)	//无右节点或者已经被访问出栈
			{
				printf("%c ", p->data);
				stack1.top--;
				p1 = p;
			}
			else
			{
				p = p->right;
				break;
			}

		}
	} while (stack1.top);
}