描述

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

在几个月之前写王道的选择题的时候便碰到了它，当时先入为主的考虑了递归实现的遍历方法，在看了讲解视频的评论后才知道原来是通过后续遍历来实现，这样可以很方便的的实现路径的查找。（其实我觉得直接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 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef char ElemType;
 5 const int N = 1e4+100;
 6 
 7 typedef struct BiTNode
 8 {
 9     ElemType data;            // 数据域
10     struct BiTNode *lchild;    // 左孩子指针
11     struct BiTNode *rchild;    // 右孩子指针
12 }BTNode,*BiTree;
13 // 树的节点 为了方便测试与建树写成全局变量
14 BiTNode A,B,C,D,E,F,G,H;
15 
16 // 非递归后序遍历二叉树
17 // 传入的参数为根节点
18 int PostOrder_Traversal(BTNode *b)
19 {
20     // 首先建栈
21     // 数组模拟
22     BTNode *st[N];
23     // 辅助节点,判断是否扫描完右子树
24     BTNode *p;
25     // 用于标记是否进入了右子树
26     bool flag;
27     // 栈顶
28     int top = -1;
29     do 
30     {
31         // 首先走到叶子节点
32         while(b != NULL)
33         {
34             st[++top] = b;
35             b = b->lchild;
36         }
37         p = NULL;
38         flag = true;
39         // 如果还未进入右子树
40         // 且栈不为空
41         while(top != -1 && flag)
42         {
43             b = st[top];
44             // 如果右子树为空
45             // 表示现在已经走到右下角了
46             if(b->rchild == p)
47             {
48                 printf("%c ",b->data);
49                 top--;
50                 p = b;
51             }
52             // 右子树不为空就往右子树走
53             // 然后跳出while 
54             // 一直往左下走到叶子节点再进入while
55             else 
56             {
57                 b = b->rchild;
58                 flag = 0;
59             }
60         }
61     }
62     while(top != -1);    // 如果栈非空
63     return 0;
64 }
65 
66 void BuildTree();
67 int main()
68 {
69     BuildTree();
70     PostOrder_Traversal(&A);
71     return 0;
72 }
73 
74 void BuildTree()
75 {
76     A.data = 'A';    B.data = 'B';    C.data = 'C';    
77     D.data = 'D';    E.data = 'E';    F.data = 'F';    
78     G.data = 'G';    H.data = 'H';
79     A.lchild = &B;    A.rchild = &D;    B.lchild = NULL;
80     B.rchild = &C;    C.lchild = NULL;C.rchild = NULL;
81     D.lchild = &E;    D.rchild = &H;     E.lchild = &F;
82     E.rchild = &G;    H.lchild = H.rchild = NULL;
83     F.lchild = F.rchild = G.lchild = G.rchild = NULL;
84 }