C++数据结构X篇_17_C++实现二叉树的非递归遍历（企业链表实现栈，利用栈的先进后出特点实现二叉树的非递归遍历）

本篇参考C++实现二叉树的非递归遍历进行整合介绍。
在C++数据结构X篇_14_二叉树的递归遍历（先序遍历、中序遍历、后续遍历方法介绍；举例；代码实现）中我们实现二叉树通过递归遍历实现了先序、中序与后续遍历，那么如何通过非递归遍历实现先序、中序与后续遍历呢？

1. 二叉树的非递归遍历规则

我们先看看非递归遍历规则，还是同样的二叉树。

• 1、首先将二叉树根节点A放入栈中，并将节点是否打印标签设为false。

• 2、再将节点A从栈中弹出，将其左右子树节点BF入栈，打印标签设为false，将A再次入栈，此时是否打印的标签设为true（注意这里三个节点入栈顺序与先序、中序与后续遍历方式有关,入栈顺序与遍历顺序正好相反，如果为先序遍历DLR，入栈顺序就应该为RLD）

• 3、再从栈中取出栈顶元素并进行打印，重复2的步骤，本身与左右子树分别入栈，本身打印标签改为true，左右子树打印标签设为false。

• 4、如果从栈中取出的栈顶元素标签为true,则直接打印，并取下一个栈中元素

参考下图对整个流程进行理解更为直观一些：

2. 实现代码

2.1 代码解析

此处采用企业链表实现栈，并利用栈的先进后出特点实现上述二叉树的非递归遍历，主要分为以下几部分：

• 栈的定义与操作
• 二叉树相关定义与操作
• 二叉树创建与遍历

2.2 实现代码

#include 
using namespace std;

//栈的定义与操作
//节点
class linknode
{
public:
	linknode* next;
};
//自定义数据
class my_data
{
public:
	linknode* node;
	char data;
};
//链式栈
class linkstack
{
public:
	linknode head;
	int size;
};
//初始化栈
linkstack* init_linkstack()
{
	linkstack* stack = new linkstack;
	stack->head.next = NULL;
	stack->size = 0;
	return stack;
}
//入栈
void push_linkstack(linkstack* stack, linknode* data)
{
	data->next = stack->head.next;
	stack->head.next = data;
	stack->size++;
}
//出栈
void pop_linkstack(linkstack* stack)
{
	stack->head.next = stack->head.next->next;
	stack->size--;
}
//返回栈顶元素
linknode* top_linkstack(linkstack* stack)
{
	return stack->head.next;
}

//二叉树相关定义与操作
const int my_true = 1;
const int my_false = 0;
//定义二叉树节点
class binarynode
{
public:
	char ch;			 //节点数据域
	binarynode* lchild;  //左孩子
	binarynode* rchild;  //右孩子
};
//栈中的二叉树节点
class linktree
{
public:
	linknode node;
	binarynode* root;
	int flag;
};
//创建栈中二叉树节点
linktree* creat_linktree_node(binarynode* node, int flag)
{
	linktree* newnode = new linktree;
	newnode->root = node;
	newnode->flag = flag;
	return newnode;
}
//非递归遍历
void nonrecurision(binarynode* root)
{
	//创建栈
	linkstack* stack = init_linkstack();
	//把根节点放入
	push_linkstack(stack, (linknode*)creat_linktree_node(root, my_false));
	while (stack->size > 0)
	{
		//弹出栈顶元素
		linktree* node = (linktree*)top_linkstack(stack);
		pop_linkstack(stack);

		//弹出节点判断是否为空
		if (node->root == NULL)
		{
			continue;
		}

		if (node->flag == my_true)
		{
			cout << node->root->ch << "\t";
		}
		else  //改变压栈顺序即可改变遍历顺序
		{
			//当前节点左右子树入栈
			push_linkstack(stack, (linknode*)creat_linktree_node(node->root->rchild, my_false));
			push_linkstack(stack, (linknode*)creat_linktree_node(node->root->lchild, my_false));
			//当前节点入栈
			node->flag = my_true;
			push_linkstack(stack, (linknode*)node);
		}
	}
	cout << endl;
}

int main()
{
	//创建节点
	binarynode node1 = { 'A',NULL,NULL };
	binarynode node2 = { 'B',NULL,NULL };
	binarynode node3 = { 'C',NULL,NULL };
	binarynode node4 = { 'D',NULL,NULL };
	binarynode node5 = { 'E',NULL,NULL };
	binarynode node6 = { 'F',NULL,NULL };
	binarynode node7 = { 'G',NULL,NULL };
	binarynode node8 = { 'H',NULL,NULL };
	//建立节点关系
	node1.lchild = &node2;
	node1.rchild = &node6;
	node2.rchild = &node3;
	node3.lchild = &node4;
	node3.rchild = &node5;
	node6.rchild = &node7;
	node7.lchild = &node8;
	//非递归先序遍历
	cout << "非递归先序遍历：" << endl;
	nonrecurision(&node1);
	system("pause");
	return 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
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

运行结果：

3. 二叉树的非递归遍历思路、二叉树的非递归遍历代码实现