PostOrder_Traversal

描述

二叉树的非递归后序遍历,改编自王道习题答案的一种方法

在几个月之前写王道的选择题的时候便碰到了它,当时先入为主的考虑了递归实现的遍历方法,在看了讲解视频的评论后才知道原来是通过后续遍历来实现,这样可以很方便的的实现路径的查找。(其实我觉得直接dfs瞎搞也挺好写的,但是毕竟这个知识点在考研的时候要考,所以还是整理一下,考试前应该会再打开看一下)

主要是方便自己复习用,故只有部分注释,无思路分析

代码中二叉树树形如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
graph TB 
A-->B(B)
A-->D(D)
B-->N1(NULL)
B-->C
C-->N2(NULL)
C-->N3(NULL)
D-->E
D-->H
E-->F
E-->G
H-->N4(NULL)
H-->N5(NULL)
F-->N6(NULL)
F-->N7(NULL)
G-->N8(NULL)
G-->N9(NULL)

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef char ElemType;
const int N = 1e4+100;

typedef struct BiTNode
{
ElemType data; // 数据域
struct BiTNode *lchild; // 左孩子指针
struct BiTNode *rchild; // 右孩子指针
}BTNode,*BiTree;
// 树的节点 为了方便测试与建树写成全局变量
BiTNode A,B,C,D,E,F,G,H;

// 非递归后序遍历二叉树
// 传入的参数为根节点
int PostOrder_Traversal(BTNode *b)
{
// 首先建栈
// 数组模拟
BTNode *st[N];
// 辅助节点,判断是否扫描完右子树
BTNode *p;
// 用于标记是否进入了右子树
bool flag;
// 栈顶
int top = -1;
do
{
// 首先走到叶子节点
while(b != NULL)
{
st[++top] = b;
b = b->lchild;
}
p = NULL;
flag = true;
// 如果还未进入右子树
// 且栈不为空
while(top != -1 && flag)
{
b = st[top];
// 如果右子树为空
// 表示现在已经走到右下角了
if(b->rchild == p)
{
printf("%c ",b->data);
top--;
p = b;
}
// 右子树不为空就往右子树走
// 然后跳出while
// 一直往左下走到叶子节点再进入while
else
{
b = b->rchild;
flag = 0;
}
}
}
while(top != -1); // 如果栈非空
return 0;
}

void BuildTree();
int main()
{
BuildTree();
PostOrder_Traversal(&A);
return 0;
}

void BuildTree()
{
A.data = 'A'; B.data = 'B'; C.data = 'C';
D.data = 'D'; E.data = 'E'; F.data = 'F';
G.data = 'G'; H.data = 'H';
A.lchild = &B; A.rchild = &D; B.lchild = NULL;
B.rchild = &C; C.lchild = NULL;C.rchild = NULL;
D.lchild = &E; D.rchild = &H; E.lchild = &F;
E.rchild = &G; H.lchild = H.rchild = NULL;
F.lchild = F.rchild = G.lchild = G.rchild = NULL;
}