1 #include <iostream>
2 3 #define MAXN 100
4 using namespace stbd;
5 6 7 struct BTNode
8 {
9 char tag;
10 BTNode *
left;
11 BTNode *
right;
12 };
13 14 class BTree
15 {
16 private:
17 BTNode **
root;
18 void BuildBTree(BTNode **
root);
19 20 public:
21 /*递归版本*/22 void PreVisit(BTNode *
root);
23 void InVisit(BTNode *
root);
24 void PostVisit(BTNode *
root);
25 26 /*非递归版本*/27 void NR_PreVisit(BTNode *
root);
28 void NR_InVisit(BTNode *
root);
29 void NR_PostVisit(BTNode *
root);
30 31 BTree(BTNode **
r);
32 BTree();
33 };
34 35 BTree::BTree()
36 {
37 38 }
39 40 BTree::BTree(BTNode **
r)
41 {
42 root =
r;
43 /*44 *root = new BTNode; 45 (*root)->left = NULL;
46 (*root)->right = NULL; 47 */48 BuildBTree(root);
49 }
50 51 /*先序方式插入结点*/52 void BTree::BuildBTree(BTNode **
root)
53 {
54 char c;
55 56 c =
getchar();
57 if(c ==
'#')
58 *root=
NULL;
59 else{
60 *root =
new BTNode;
61 (*root)->tag =
c;
62 BuildBTree(&(*root)->
left);
63 BuildBTree(&(*root)->
right);
64 }
65 }
66 67 void BTree::PreVisit(BTNode *
root)
68 {
69 if(root!=
NULL)
70 {
71 printf(
"%c ", root->
tag );
72 PreVisit(root->
left);
73 PreVisit(root->
right);
74 }
75 }
76 77 void BTree::InVisit(BTNode *
root)
78 {
79 if(root!=
NULL)
80 {
81 InVisit(root->
left);
82 printf(
"%c ", root->
tag );
83 InVisit(root->
right);
84 }
85 }
86 87 void BTree::PostVisit(BTNode *
root)
88 {
89 if(root!=
NULL)
90 {
91 PostVisit(root->
left);
92 PostVisit(root->
right);
93 printf(
"%c ", root->
tag );
94 }
95 }
96 97 void BTree::NR_PreVisit(BTNode *
root)
98 {
99 BTNode *
s[MAXN];
100 int top=
0;
101 102 while(top!=
0 || root!=
NULL)
103 {
104 while(root!=
NULL)
105 {
106 s[top] =
root;
107 printf(
"%c ", s[top++]->
tag);
108 root = root->
left;
109 }
110 if(top>
0)
111 {
112 root = s[--
top];
113 root = root->
right;
114 }
115 }
116 }
117 118 void BTree::NR_InVisit(BTNode *
root)
119 {
120 BTNode *
s[MAXN];
121 int top=
0;
122 123 while(top!=
0 || root!=
NULL)
124 {
125 while(root!=
NULL)
126 {
127 s[top++]=
root;
128 root = root->
left;
129 }
130 if(top>
0)
131 {
132 root = s[--
top];
133 printf(
"%c ", root->
tag);
134 root = root->
right;
135 }
136 }
137 }
138 139 void BTree::NR_PostVisit(BTNode *
root)
140 {
141 BTNode *s[MAXN], *tmp=
NULL;
142 int top=
0;
143 144 while(top!=
0 || root!=
NULL)
145 {
146 while(root!=
NULL)
147 {
148 s[top++]=
root;
149 root=root->
left;
150 }
151 if(top>
0)
152 {
153 root = s[--
top];
154 155 /*右孩子不存在或者已经访问过，root出栈并访问*/156 if( (root->right == NULL) || (root->right ==
tmp) )
157 {
158 printf(
"%c ", root->
tag);
159 tmp = root;
//保存root指针160 root=NULL;
//当前指针置空，防止再次入栈161 }
162 163 /*不出栈，继续访问右孩子*/164 else165 {
166 top++;
//与root=s[--top]保持平衡167 root = root->
right;
168 }
169 }
170 }
171 }
172 173 int main()
174 {
175 BTNode *root=
NULL;
176 BTree bt(&root);
//头指针的地址177 178 bt.NR_PreVisit(root);
179 printf(
"\n");
180 bt.NR_InVisit(root);
181 printf(
"\n");
182 bt.NR_PostVisit(root);
183 printf(
"\n");
184 return 0;
185 }
先上代码，tb带NR(Non-recursive)的表示非递归遍历。
测试数据：
124#8##5##369###7##
表示的二叉树：
用windows自带的画图画的，的确是粗糙了点。。。
测试结果：
1 2 4 8 5 3 6 9 7
4 8 2 5 1 9 6 3 7
8 4 5 2 9 6 7 3 1
一、关于二叉树的建立
首先要注意二叉树的创建过程，这里用的是先序方式递归插入结点，所以输入数据的时候，必须按照先序方式输入，
左结点或右结点为空的，用#表示。否则，输入不会有响应，因为递归过程还未结束，按CTRL+Z也没用。当然可以用其
他方式插入(如中序递归插入，后序递归插入等)。
二、三种非递归遍历的区别
前序、中序和后序的递归遍历方式比较简单，这里就不讲了。而非递归的遍历方式，只需要用数组存储结点指针，模拟系统栈的工作机制就可以了。
先说先序非递归遍历，按照根-左-右的方式访问的话，需要将当前结点压栈(同时打印当前结点信息)，直到左子树为空(内层while)；然后出栈，访问
右结点；后面的操作就跟前面的一样了(外层while)。
对于中序非递归遍历，可以看到代码结构几乎一模一样，只是打印结点信息的位置不同而已。这是因为中序遍历是左-根-右，这样前序和中序非
递归遍历（根-左和左-根都是压栈动作，且出栈动作的对象都是父节点)是一致的。
对于后序非递归遍历，因为后序遍历是左-右-根，根的访问是在右孩子之后，而这意味着两种情况：
1、右孩子不为空（继续访问右孩子）；
2、右孩子为空，从左孩子返回，则需要访问根结点。
为了区分这两种情况(物理形式上从左孩子返回，还是从右孩子返回来访问根节点)，对于右孩子的访问又需要判断根结点的右孩子是否为空或者已
访问过（右子树已遍历过）。除这两种情况外，都不应该访问根节点，而是要继续进入右子树。
三、补充说明
在后序非递归遍历的else语句中top++纯粹是为了使栈保持平衡，因为对于2)继续访问右孩子这种情况，不需要出栈，而前面的root[--top]包含
了出栈操作，以此保证栈的正确性（当然可以有其他的处理，这里也是考虑到三种非递归遍历方式的统一性）。
两个while不会提高程序的时间复杂度，因为二叉树的结点个数是固定的，内层while是为了提高算法的逻辑性。
四、递归->非递归
另外，今天实习看到一个老师写的非递归代码，非常棒，赞一个！他仅仅是将程序的返回地址和函数的形参、局部变量都保存起来，然后在退出时
还原现场；同样是非递归，但是这种方式更接近编译器的处理方式，同操作系统的任务切换也比较一致；所以这种处理方法为递归自动转换为非递归奠
定了基础。
分享一下他当场编写的非递归的汉诺塔：
1 #include <stdio.h>
2 #include <iostream>
3
4 using namespace std ;
5
6 #define MAXSIZE 1000
7
8 struct SNode
9 {
10 int n;
11 char from ;
12 char to;
13 char aux ;
14 int label ;
15 } ;
16
17 struct STK
18 {
19
20 SNode stack[MAXSIZE] ;
21 int sp ;
22 STK()
23 {
24 sp = 0 ;
25 };
26 void push (int n,char from,char to,char aux, int label )
27 {
28 if ( sp>= MAXSIZE )
29 {
30 printf ( "STK is full!\n" ) ;
31 }
32 stack[sp].n = n ;
33 stack[sp].from = from ;
34 stack[sp].to = to ;
35 stack[sp].aux = aux ;
36 stack[sp++].label = label ;
37 };
38 SNode POP()
39 {
40 if ( sp <=0 )
41 {
42 printf ( "STK is empty!\n" ) ;
43 }
44 return stack[--sp] ;
45 };
46 } ;
47
48 void move(int n,char from,char to,char aux)
49 {
50 if(n==1)
51 {
52 cout<<"将#1盘从"<<from<<"移到"<<to<<endl;
53 }
54 else
55 {
56 move(n-1,from,aux,to);
57 cout<<"将#"<<n<<"盘从"<<from<<"移到"<<to<<endl;
58 move(n-1,aux,to,from);
59 }
60 }
61
62
63 void move_stk(int n,char from,char to,char aux)
64 {
65 STK stk ;
66 char tmp;
67 S1:
68 if(n==1)
69 {
70 cout<<"将#1盘从"<<from<<"移到"<<to<<endl;
71 }
72 else
73 {
74 stk.push (n,from,to,aux,2 ) ;
75 n = n-1 ;
76 tmp = to ;
77 to = aux ;
78 aux = tmp ;
79 goto S1;
80 // move(n-1,from,aux,to);
81 S2:
82 cout<<"将#"<<n<<"盘从"<<from<<"移到"<<to<<endl;
83
84 stk.push (n,from,to,aux,3 ) ;
85 n = n-1 ;
86 tmp = from ;
87 from = aux ;
88 aux = tmp ;
89 goto S1;
90 // move(n-1,aux,to,from);
91 }
92 S3:
93 if ( stk.sp > 0 )
94 {
95 SNode sn = stk.POP() ;
96 n = sn.n ;
97 from = sn.from;
98 to = sn.to ;
99 aux = sn.aux ;
100 if ( 1 == sn.label )
101 goto S1;
102 else if ( 2 == sn.label )
103 goto S2;
104 else
105 goto S3;
106 }
107 }
108
109
110
111 int main(int argc, char * argv[])
112 {
113 move ( 3,'A','B', 'C' );
114 printf ( "================================\n" ) ;
115 move_stk ( 3,'A','B', 'C' );
116
117 return 0;
118 }