二叉树的前序, 中序, 后序非递归算法

什么是前序, 中序, 后序首先先介绍一下三种遍历二叉树的方法:

  1. 前序:先根结点后左孩子最后右孩子
  2. 中序:先左孩子后根结点最后右孩子
  3. 后序:先左孩子后右孩子最后根结点

例如上图中的二叉树我们的遍历输出分别为:
前序: GDAFEMHZ
中序: ADEFGHMZ
后序: AEFDHZMG代码部分#include

#include

什么是前序, 中序, 后序

首先先介绍一下三种遍历二叉树的方法:

  1. 前序:先根结点后左孩子最后右孩子
  2. 中序:先左孩子后根结点最后右孩子
  3. 后序:先左孩子后右孩子最后根结点
    二叉树例子
    例如上图中的二叉树我们的遍历输出分别为:
    前序: GDAFEMHZ
    中序: ADEFGHMZ
    后序: AEFDHZMG

代码部分

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
#include<cstdio>
#include<iostream>
#include<stack>//这是关于C++队列以及栈的库模板调用
#include<queue>//我的博客中有一篇关于这些库函数的使用
#include<iomanip>
#include<cstdlib>
#define MAXSIZE 100
using namespace std;
int flag[MAXSIZE];
typedef struct BiTNode
{
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;//定义二叉树的结构体
void CreateBiTree(BiTree &T)
{
char ch;
cin>>ch;
if(ch == '#') T = NULL;
else
{
T = new BiTNode;
T->data = ch;
CreateBiTree(T -> lchild);//输入左子树
CreateBiTree(T -> rchild);//输入右子树
}
}//采用先序递归的形式创建二叉树, 当用户输入"#"时,为空作用域
//例如我们上面的例子,输入上面的图片中二叉树时这个函数的输入格式为:
//GDA##FE###MH##Z###
void show_DLR(BiTree &T)//先序遍历
{
BiTree p, l, k;
p = T;
l = new BiTNode;
k = new BiTNode;
stack<BiTree>m;//这个遍历我采用栈压入元素, 队列弹出元素的
//格式
queue<BiTree>n;
while(p || !n.empty())
{
if(p)//遍历左子树
{
m.push(p);//分别将二叉树的结点压入栈和队列中
n.push(p);
p = p->lchild;
}
else
{
k = n.front();
n.pop();//注意此时弹出的为队列中的第一个元素
cout<<setw(4)<<k->data;
l = m.top();
m.pop();
p = l->rchild;
}
}
cout<<endl;
}
void show_LDR(BiTree &T)//中序遍历
{
BiTree p, q;
stack<BiTree>s;//和上面的先序遍历很像
//只不过在中序遍历中我们只用一个栈就可以完成
p = T;
q = new BiTNode;
while(p || !s.empty() )
{
if(p)
{
s.push(p);
p = p->lchild;
}
else
{
q = s.top();
s.pop();
cout<<setw(4)<<q->data;
p = q->rchild;
}
}
cout<<endl;
}
void show_LRD(BiTree &T)//后序遍历是最为头疼的
{//这里我设置了一个全局数组为flag
BiTree p, m, n;
stack<BiTree>s;
int i = 0;
p = T;
while(p)
{//将当前左子树全部压入堆栈中
s.push(p);
flag[s.size()] = 0;//栈中的库函数s.size()返回当前栈中
//元素的个数
//其目的主要是设置一个标志位看看
//当前节点是否被访问过
p = p->lchild;
}
while(!s.empty())
{
p = s.top();
if(!p->rchild || flag[s.size()])
{//没有右子树或者当前的结点的右子树被访问过就输出
m = s.top();
s.pop();
cout<<setw(4)<<m->data;
}
else
{
flag[s.size()] = 1;//已访问
m = p->rchild;
while(m)
{//因为为后序遍历,将当前结点的左子树分别再压入堆栈
s.push(m);
flag[s.size()] = 0;
m = m->lchild;
}
}
}
}
int main()
{
BiTree L;
CreateBiTree(L);
show_DLR(L);
show_LDR(L);
show_LRD(L);
return 0;
}
越来越多的平台(微信公众平台,新浪微博,简书,百度打赏等)支持打赏功能,付费阅读时代越来越近,特此增加了打赏功能,支持微信打赏和支付宝打赏。坚持原创技术分享,您的支持将鼓励我继续创作!