二叉树后序遍历(非递归)-蒲公英云

二叉树后序遍历(非递归)

二叉树的递归遍历算法就不用说了；在非递归算法中，后序遍历难度大，很多书上只给出思想或者几段无法直接调试的代码，甚至有些书上是错的，当时我在研究的过程中，就是按着书上错误的代码绕了好半天，几预抓狂。好在最终摸索出来了，不禁感叹很多出书人的水平真是…… 这里将直接可以在编译器里调试的代码贴出来(在DEV-C++编译器中编译通过)

这里我们约定：空的节点用空格表示，按照前序遍历来创建树！

1 // main.cpp

复制代码

2 #include < iostream >
3 using namespace std;
4 typedef struct node {
5 char data;
6 struct node * lchild;
7 struct node * rchild;
8 }BiNode, * BiTree;
9 typedef struct node1{
10 BiTree data[ 30 ]; // 默认30个元素，这里需要一个辅助堆栈！！！
11 int top;
12 }Stack;
13
14 void createTree(BiTree & T) // 先序递归创建树，这里注意参数的类型，T的类型是 “*&” ,如果是 “**“ 代码稍加改动就OK…
15 {
16 char ch;
17 cin. get (ch). get (); //过滤输入流中每次回车产生的回车符
18 if (ch == ‘ ‘ ) T = NULL; //这里首先判断是不是空格，如果是，则为该节点赋NULL
19 else {
20 T = (BiTree)malloc( sizeof (BiNode));
21 T -> data = ch;
22 createTree(T -> lchild);
23 createTree(T -> rchild);
24 }
25 }
26 void initstack(Stack *& st)
27 {
28 st = (Stack * )malloc( sizeof (Stack));
29 st -> top =- 1 ;
30 }
31 bool isempty(Stack * st)
32 {
33 return st -> top ==- 1 ;
34 }
35 bool isfull(Stack * st)
36 {
37 return st -> top == 19 ;
38 }
39 void push(Stack * st,BiTree T)
40 {
41 if ( ! isfull(st))
42 st -> data[ ++ st -> top] = T; //栈顶指针始终指向堆栈最上面可用的一个元素，因此入栈时候，先要将指针加1,然后再执行入栈操作！
43 else cout << “ 已满 “ << endl;
44 }
45 BiTree pop(Stack * st)
46 {
47 if ( ! isempty(st)) return st -> data[st -> top -- ];
48 }
49 BiTree gettop(Stack * st)
50 {
51 if ( ! isempty(st)) return st -> data[st -> top]; //出栈时，先取出栈顶指针指向的元素，然后再将指针减1，使其指向栈中下一个可用元素！
52 }
53 void preOrderNoRe(BiTree T) // 前序遍历
54 {
55 Stack * st;
56 initstack(st);
57 BiTree p;
58 p = T;
59 while (p != NULL ||! isempty(st))
60 {
61 while (p != NULL)
62 {
63 cout << p -> data << “ “ ;
64 push(st,p);
65 p = p -> lchild;
66 }
67 if ( ! isempty(st))
68 {
69 p = pop(st);
70 p = p -> rchild;
71 }
72
73 }
74 }
75 void inOrderNoRe(BiTree T) //中序遍历
76 {
77 Stack * st;
78 initstack(st);
79 BiTree p;
80 p = T;
81 while (p != NULL ||! isempty(st))
82 {
83 while (p != NULL)
84 {
85 push(st,p);
86 p = p -> lchild;
87 }
88 if ( ! isempty(st))
89 {
90 p = pop(st);
91 cout << p -> data << “ “ ;
92 p = p -> rchild;
93 }
94
95 }
96 }
97 void postOrderNoRe(BiTree T) //后序遍历
98 {
99 BiTree p;
100 Stack * st;
101 initstack(st);
102 p = T;
103 int Tag[ 20 ]; // 栈，用于标识从左（0）或右（1）返回
104 while (p != NULL || ! isempty(st))
105 {
106 while (p != NULL)
107 {
108 push(st,p);
109 Tag[st -> top] = 0 ;
110 p = p -> lchild;
111 }
112 while ( ! isempty(st) && Tag[st -> top] == 1 )
113 {
114 p = pop(st);
115 cout << p -> data << “ “ ;
116 }
117 if ( ! isempty(st))
118 {
119 Tag[st -> top] = 1 ; // 设置标记右子树已经访问
120 p = gettop(st);
121 p = p -> rchild;
122 }
123 else break ;
124 }
125 }
126 int main()
127 {
128 cout << “ Enter char one by one hicjiajia “ << endl;
129 BiNode * T;
130 createTree(T);
131 cout << endl;
132
133 cout << “ preOrderNoRe: “ ;preOrderNoRe(T);cout << endl;
134 cout << “ inOrderNoRe: “ ;inOrderNoRe(T);cout << endl;
135 cout << “ postOrderNoRe: “ ;postOrderNoRe(T);cout << endl;
136 system( “ pause “ );
137 return 0 ;
138 }