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 /*先序方式插入結(jié)點(diǎn)*/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 /*右孩子不存在或者已經(jīng)訪問過，root出棧并訪問*/156 if( (root->right == NULL) || (root->right ==
tmp) )
157 {
158 printf(
"%c ", root->
tag);
159 tmp = root;
//保存root指針160 root=NULL;
//當(dāng)前指針置空，防止再次入棧161 }
162 163 /*不出棧，繼續(xù)訪問右孩子*/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)的表示非遞歸遍歷。
測(cè)試數(shù)據(jù)：
124#8##5##369###7##
表示的二叉樹：
用windows自帶的畫圖畫的，的確是粗糙了點(diǎn)。。。
測(cè)試結(jié)果：
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
一、關(guān)于二叉樹的建立
首先要注意二叉樹的創(chuàng)建過程，這里用的是先序方式遞歸插入結(jié)點(diǎn)，所以輸入數(shù)據(jù)的時(shí)候，必須按照先序方式輸入，
左結(jié)點(diǎn)或右結(jié)點(diǎn)為空的，用#表示。否則，輸入不會(huì)有響應(yīng)，因?yàn)檫f歸過程還未結(jié)束，按CTRL+Z也沒用。當(dāng)然可以用其
他方式插入(如中序遞歸插入，后序遞歸插入等)。
二、三種非遞歸遍歷的區(qū)別
前序、中序和后序的遞歸遍歷方式比較簡單，這里就不講了。而非遞歸的遍歷方式，只需要用數(shù)組存儲(chǔ)結(jié)點(diǎn)指針，模擬系統(tǒng)棧的工作機(jī)制就可以了。
先說先序非遞歸遍歷，按照根-左-右的方式訪問的話，需要將當(dāng)前結(jié)點(diǎn)壓棧(同時(shí)打印當(dāng)前結(jié)點(diǎn)信息)，直到左子樹為空(內(nèi)層while)；然后出棧，訪問
右結(jié)點(diǎn)；后面的操作就跟前面的一樣了(外層while)。
對(duì)于中序非遞歸遍歷，可以看到代碼結(jié)構(gòu)幾乎一模一樣，只是打印結(jié)點(diǎn)信息的位置不同而已。這是因?yàn)橹行虮闅v是左-根-右，這樣前序和中序非
遞歸遍歷（根-左和左-根都是壓棧動(dòng)作，且出棧動(dòng)作的對(duì)象都是父節(jié)點(diǎn))是一致的。
對(duì)于后序非遞歸遍歷，因?yàn)楹笮虮闅v是左-右-根，根的訪問是在右孩子之后，而這意味著兩種情況：
1、右孩子不為空（繼續(xù)訪問右孩子）；
2、右孩子為空，從左孩子返回，則需要訪問根結(jié)點(diǎn)。
為了區(qū)分這兩種情況(物理形式上從左孩子返回，還是從右孩子返回來訪問根節(jié)點(diǎn))，對(duì)于右孩子的訪問又需要判斷根結(jié)點(diǎn)的右孩子是否為空或者已
訪問過（右子樹已遍歷過）。除這兩種情況外，都不應(yīng)該訪問根節(jié)點(diǎn)，而是要繼續(xù)進(jìn)入右子樹。
三、補(bǔ)充說明
在后序非遞歸遍歷的else語句中top++純粹是為了使棧保持平衡，因?yàn)閷?duì)于2)繼續(xù)訪問右孩子這種情況，不需要出棧，而前面的root[--top]包含
了出棧操作，以此保證棧的正確性（當(dāng)然可以有其他的處理，這里也是考慮到三種非遞歸遍歷方式的統(tǒng)一性）。
兩個(gè)while不會(huì)提高程序的時(shí)間復(fù)雜度，因?yàn)槎鏄涞慕Y(jié)點(diǎn)個(gè)數(shù)是固定的，內(nèi)層while是為了提高算法的邏輯性。
四、遞歸->非遞歸
另外，今天實(shí)習(xí)看到一個(gè)老師寫的非遞歸代碼，非常棒，贊一個(gè)！他僅僅是將程序的返回地址和函數(shù)的形參、局部變量都保存起來，然后在退出時(shí)
還原現(xiàn)場(chǎng)；同樣是非遞歸，但是這種方式更接近編譯器的處理方式，同操作系統(tǒng)的任務(wù)切換也比較一致；所以這種處理方法為遞歸自動(dòng)轉(zhuǎn)換為非遞歸奠
定了基礎(chǔ)。
分享一下他當(dāng)場(chǎng)編寫的非遞歸的漢諾塔：
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 }