【数据结构】基于栈的二叉树先/中/后序非递归遍历（C语言）_试利用栈的基本操作写出先序遍历和后序遍历的非递归形式的算法

二叉树的递归遍历：https://blog.csdn.net/weixin_51450101/article/details/122742243?spm=1001.2014.3001.5501

1. 直接实现栈操作方法

1.1 先序遍历

/*先序遍历二叉树的非递归算法（直接实现栈操作）*/
void PreOrder(BiTree bt) {
   
//s[m]表示栈，top表示栈顶指针
	BiTNode* s[Stack_Size];
	int top = 0;
	BiTNode* p = bt;
	do {
   
		while (p != NULL) {
   
			if (top > Stack_Size)
				return;
			printf("%c ", p->data);
			top = top + 1;
			s[top] = p;
			p = p->LChild;
		}
		if (top != 0) {
   
			p = s[top];
			top = top - 1;
			p = p->RChild;
		}
	} while (p != NULL || top != 0);
}
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

1.2 中序遍历

/*中序遍历二叉树的非递归算法（直接实现栈操作）*/
void InOrder(BiTree bt) {
   
//s[m]表示栈，top表示栈顶指针
	BiTNode* s[Stack_Size];
	int top = 0;
	BiTNode* p = bt;
	do {
   
		while (p != NULL) {
   
			if (top > Stack_Size)
				return;
			top = top + 1;
			s[top] = p;
			p = p->LChild;
		}
		if (top != 0) {
   
			p = s[top];
			top = top - 1;
			printf("%c ", p->data);
			p = p->RChild;
		}
	} while (p != NULL || top != 0);
}
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

1.3 后序遍历

/*后序遍历二叉树的非递归算法（直接实现栈操作）*/
void PostOrder(BiTree bt) {
   
//s[m]表示栈，top表示栈顶指针
	BiTNode* s[Stack_Size];
	int top = 0;
	BiTNode* p = bt, * q = NULL;
	while (p != NULL || top != 0) {
   
		if (p != NULL) {
   
			if (top > Stack_Size)
				return;
			top = top + 1;
			s[top] = p;
			p = p->LChild;
		}
		else {
   
			p = s[top];
			if (p->RChild == NULL || p->RChild == q) {
   //无右孩子结点或右孩子结点已遍历过
				printf("%c ", p->data);
				q = p;
				top = top - 1;
				p = NULL;
			}
			else
				p = p->RChild;
		}
	}
}
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

1.4 完整实现代码

# include<stdio.h>
# include<malloc.h>
# define Stack_Size 50

1
2
3
4