二叉树的创建及遍历是很多二叉树问题的基础,递归遍历逻辑清晰,代码简约漂亮,然则效率低下(所有递归方案的通病,非不得已不用递归);
非递归遍历高效,却不是能信手写出来的,特别是后续非递归遍历,相信很多资深码工也有这样的经历:
5年前学习了二叉树的非递归遍历,一个月前复习了并达到能熟练写出的程度,在不参考任何资料的情况下,今天却怎样也写不出来,
二叉树基础 创建,遍历方法(前序/中序/后序/层序、递归/非递归)
。如果你也有过这种经历,恭喜你,这说明你是一个正常人……
另一方面市面上有些国人写的教材,各种语法、逻辑错误层出不起,不知祸害了多少未来的码工,深感痛心。
印象比较深刻的有清华大学出版社出版的《数据结果(C++版)》 王红梅、胡明、王涛编著。
如书中第163页后序非递归遍历方法,短短不到30行代码各种语法、逻辑错误如下:
1 template
2 void BiTree::PostOrder(BiNode
3 {
4 top = -1;
5 //错误二:应该在这里定义下文用到的栈s(书中说这是具体的代码,不是伪代码)。
6 wihle(root != NULL || top != -1)
7 {
8 while(root != NULL)
9 {
10 top++;
11 s[top].ptr = root;
12 s[top].flag = 1;
13 root = root -> lchild;
14 }
15 while(top != -1 && s[top].flag ==2)
16 {
17 root = s[top--].ptr;
18 cout << root->data;
19 }
20 if(top != -1)
21 {
22 s[top].flag = 2;
23 root = s[top].ptr->rchild;
24 }
25 //错误三:致命逻辑错误,栈空时,应该退出外层循环,否则将进入死循环,应该加上如下一行代码。
26 //else break;
27 }
28 }
下面咱们来实现一个二叉树的Class,在Class中实现以下方法:
1.创建一颗二叉树;
2.销毁一颗二叉树;
3.递归前序遍历方法;
4.非递归前序遍历方法;
5.递归中序遍历方法;
6.非递归中序遍历方法;
7.递归后序遍历方法;
8.非递归后序遍历方法;
9.层序遍历方法(这个应该就没有递归的方法)。
要点:非递归遍历用栈辅助(深度优先),层序遍历用队列辅助(广度优先)。
二叉树节点定义:
1 template
2 struct BiNode
3 {
4 T data;
5 BiNode
6 BiNode
7 };
二叉树Class定义:
要点:1.数据成员申明为私有(原因见Effective C++ 条款21:将成员变量申明为private);
2. 公有成员方法如PreOrder1()为对外接口,调用私用方法PreOrderRecursive(BiNode
1 template
2 class BiTree
3 {
4 public:
5 BiTree();
6 ~BiTree();
7 void PreOrder1();//递归
8 void PreOrder2();//非递归
9 void InOrder1();//递归
10 void InOrder2();//非递归
11 void PostOrder1();//递归
12 void PostOrder2();//非递归
13 void LevelOrder();
14 private:
15 BiNode
16 void CreateBiTree(BiNode
17 void ReleaseBiTree(BiNode
18
19 void PreOrderRecursive(BiNode
20 void PreOrderNonRecursive(BiNode
21
22 void InOrderRecursive(BiNode
23 void InOrderNonRecursive(BiNode
24
25 void PostOrderRecursive(BiNode
26 void PostOrderNonRecursive(BiNode
27
28 void LevelOrder(BiNode
29 };
创建二叉树:
1 template
2 void BiTree
3 {
4 T data;
5 cin>>data;
6 if(data == INVALID)
7 {
8 root = NULL;
9 }
10 else
11 {
12 root = new BiNode
13 root->data = data;
14 CreateBiTree(root->pLeft);
15 CreateBiTree(root->pRight);
16 }
17 }
18
19
20 template
21 BiTree
22 {
23 CreateBiTree(root);
24 }
销毁二叉树:
1 template
2 void BiTree
3 {
4 if(root != NULL)
5 {
6 ReleaseBiTree(root->pLeft);
7 ReleaseBiTree(root->pRight);
8 delete root;
9 }
10 }
11
12
13 template
14 BiTree
15 {
16 ReleaseBiTree(root);
17 }
前序递归遍历:
1 template
2 void BiTree
3 {
4 if(root != NULL)
5 {
6 cout<
7 PreOrderRecursive(root->pLeft);
8 PreOrderRecursive(root->pRight);
9 }
10 }
11
12
13
14 template
15 void BiTree
16 {
17 PreOrderRecursive(root);
18 cout< 19 } 中序递归遍历: 1 template 2 void BiTree 3 { 4 if(root != NULL) 5 { 6 InOrderRecursive(root->pLeft); 7 cout< 8 InOrderRecursive(root->pRight); 9 } 10 } 11 12 13 template 14 void BiTree 15 { 16 InOrderRecursive(root); 17 cout< 18 } 后序递归遍历: 1 template 2 void BiTree 3 { 4 if(root != NULL) 5 { 6 PostOrderRecursive(root->pLeft); 7 PostOrderRecursive(root->pRight); 8 cout< 9 } 10 } 11 12 13 template 14 void BiTree 15 { 16 PostOrderRecursive(root); 17 cout< 18 } 层序遍历: 1 template 2 void BiTree 3 { 4 BiNode 5 queue 6 if(root == NULL) 7 return; 8 q.push(root); 9 while(!q.empty()) 10 { 11 p = q.front(); 12 cout << p->data<<" "; 13 q.pop(); 14 if(p->pLeft != NULL) q.push(p->pLeft); 15 if(p->pRight != NULL) q.push(p->pRight); 16 } 17 } 18 19 template 20 void BiTree 21 { 22 LevelOrder(root); 23 cout< 24 } 前序非递归遍历: 1 template 2 void BiTree 3 { 4 stack 5 while(root != NULL || !s.empty()) 6 { 7 while(root != NULL) 8 { 9 cout< 10 s.push(root); 11 root = root->pLeft; 12 } 13 if(!s.empty()) 14 { 15 root = s.top(); 16 s.pop(); 17 root = root->pRight; 18 } 19 } 20 21 } 22 23 24 25 26 template 27 void BiTree 28 { 29 PreOrderNonRecursive(root); 30 cout< 31 } 中序非递归遍历: 1 template 2 void BiTree 3 { 4 stack 5 while(root != NULL || !s.empty()) 6 { 7 while(root != NULL) 8 { 9 s.push(root); 10 root = root->pLeft; 11 } 12 if(!s.empty()) 13 { 14 root = s.top(); 15 s.pop(); 16 cout< 17 root = root->pRight; 18 } 19 } 20 21 } 22 23 24 25 template 26 void BiTree 27 { 28 InOrderNonRecursive(root); 29 cout< 30 } 后序非递归遍历: 1 template 2 void BiTree 3 { 4 5 stack 6 stack 7 8 while(root != NULL || !s1.empty()) 9 { 10 while(root != NULL) 11 { 12 s1.push(root); 13 s2.push(1); 14 root = root->pLeft; 15 } 16 if(!s1.empty()) 17 { 18 if(s2.top()==1) 19 { 20 s2.pop(); 21 s2.push(2); 22 root = s1.top()->pRight; 23 } 24 else 25 { 26 root = s1.top(); 27 s1.pop(); 28 s2.pop(); 29 cout< 30 root = NULL; 31 } 32 } 33 34 } 35 36 } 37 38 template 39 void BiTree 40 { 41 PostOrderRecursive(root); 42 cout< 43 } 44 45 template 46 void BiTree 47 { 48 PostOrderNonRecursive(root); 49 cout< 50 } 假定我们创建的二叉树形状如下: 1 /* 2 假定所创建的二叉树如下图所示 3 A 4 / \ 5 B C 6 / \ / 7 D E F 8 \ 9 G 10 11 12 创建二叉树的文件:《BiTree.txt》内容如下: 13 A B D # # E # G # # C F # # # 14 15 */ 16 const char *preorder = "A B D E G C G"; 17 const char *inorder = "D B E G A F C"; 18 const char *postorder = "D G E B F C A"; 19 const char *levelorder= "A B C D E F G"; main函数: 1 int main() 2 { 3 ifstream fin("BiTree.txt");// 输入文件 4 ofstream fout("out.txt"); //输出文件 5 6 streambuf *cinbackup; 7 streambuf *coutbackup; 8 9 cinbackup= cin.rdbuf(fin.rdbuf()); //用 rdbuf() 重新定向 10 coutbackup= cout.rdbuf(fout.rdbuf()); //用 rdbuf() 重新定向 11 12 BiTree 13 14 cout << "*preorder = " << preorder << endl; 15 cout << " PreOrder1(): "; 16 pbitree->PreOrder1(); 17 cout << " PreOrder2(): "; 18 pbitree->PreOrder2(); 19 cout< 20 21 cout << "*inorder = " << inorder << endl; 22 cout << " inorder1(): "; 23 pbitree->InOrder1(); 24 cout << " InOrder2(): "; 25 pbitree->InOrder2(); 26 cout< 27 28 cout << "*postorder = " << postorder << endl; 29 cout << " PostOrder1(): "; 30 pbitree->PostOrder1(); 31 cout << " PostOrder2(): "; 32 pbitree->PostOrder2(); 33 cout< 34 35 cout << "*levelorder = " << levelorder << endl; 36 cout << " LevelOrder(): "; 37 pbitree->LevelOrder(); 38 39 delete pbitree; 40 cin.rdbuf(cinbackup); // 取消,恢复键盘输入 41 cout.rdbuf(coutbackup); //取消,恢复屏幕输出 42 return 0; 43 } 完整的代码: 1 #include 2 #include 3 #include 4 #include 5 6 using namespace std; 7 8 9 /* 10 假定所创建的二叉树如下图所示 11 A 12 / \ 13 B C 14 / \ / 15 D E F 16 \ 17 G 18 19 20 创建二叉树的文件:《BiTree.txt》内容如下: 21 A B D # # E # G # # C F # # # 22 23 */ 24 const char *preorder = "A B D E G C G"; 25 const char *inorder = "D B E G A F C"; 26 const char *postorder = "D G E B F C A"; 27 const char *levelorder= "A B C D E F G"; 28 29 const char INVALID = '#';//INVALID在CreateBiTree()函数中表示空节点,类型适配 template 30 31 template 32 struct BiNode 33 { 34 T data; 35 BiNode 36 BiNode 37 }; 38 39 template 40 class BiTree 41 { 42 public: 43 BiTree(); 44 ~BiTree(); 45 void PreOrder1();//递归 46 void PreOrder2();//非递归 47 void InOrder1();//递归 48 void InOrder2();//非递归 49 void PostOrder1();//递归 50 void PostOrder2();//非递归 51 void LevelOrder(); 52 private: 53 BiNode 54 void CreateBiTree(BiNode 55 void ReleaseBiTree(BiNode 56 57 void PreOrderRecursive(BiNode 58 void PreOrderNonRecursive(BiNode 59 60 void InOrderRecursive(BiNode 61 void InOrderNonRecursive(BiNode 62 63 void PostOrderRecursive(BiNode 64 void PostOrderNonRecursive(BiNode 65 66 void LevelOrder(BiNode 67 }; 68 69 70 template 71 void BiTree 72 { 73 T data; 74 cin>>data; 75 if(data == INVALID) 76 { 77 root = NULL; 78 } 79 else 80 { 81 root = new BiNode 82 root->data = data; 83 CreateBiTree(root->pLeft); 84 CreateBiTree(root->pRight); 85 } 86 } 87 88 89 template 90 void BiTree 91 { 92 if(root != NULL) 93 { 94 ReleaseBiTree(root->pLeft); 95 ReleaseBiTree(root->pRight); 96 delete root; 97 } 98 } 99 template 100 BiTree 101 { 102 CreateBiTree(root); 103 } 104 105 106 template 107 BiTree 108 { 109 ReleaseBiTree(root); 110 } 111 112 113 template 114 void BiTree 115 { 116 if(root != NULL) 117 { 118 cout< 119 PreOrderRecursive(root->pLeft); 120 PreOrderRecursive(root->pRight); 121 } 122 } 123 124 template 125 void BiTree 126 { 127 stack 128 while(root != NULL || !s.empty()) 129 { 130 while(root != NULL) 131 { 132 cout< 133 s.push(root); 134 root = root->pLeft; 135 } 136 if(!s.empty()) 137 { 138 root = s.top(); 139 s.pop(); 140 root = root->pRight; 141 } 142 } 143 144 } 145 146 147 template 148 void BiTree 149 { 150 PreOrderRecursive(root); 151 cout< 152 } 153 154 template 155 void BiTree 156 { 157 PreOrderNonRecursive(root); 158 cout< 159 } 160 161 template 162 void BiTree 163 { 164 if(root != NULL) 165 { 166 InOrderRecursive(root->pLeft); 167 cout< 168 InOrderRecursive(root->pRight); 169 } 170 } 171 172 template 173 void BiTree 174 { 175 stack 176 while(root != NULL || !s.empty()) 177 { 178 while(root != NULL) 179 { 180 s.push(root); 181 root = root->pLeft; 182 } 183 if(!s.empty()) 184 { 185 root = s.top(); 186 s.pop(); 187 cout< 188 root = root->pRight; 189 } 190 } 191 192 } 193 194 template 195 void BiTree 196 { 197 InOrderRecursive(root); 198 cout< 199 } 200 201 202 template 203 void BiTree 204 { 205 InOrderNonRecursive(root); 206 cout< 207 } 208 209 template 210 void BiTree 211 { 212 if(root != NULL) 213 { 214 PostOrderRecursive(root->pLeft); 215 PostOrderRecursive(root->pRight); 216 cout< 217 } 218 } 219 220 template 221 void BiTree 222 { 223 224 stack 225 stack 226 227 while(root != NULL || !s1.empty()) 228 { 229 while(root != NULL) 230 { 231 s1.push(root); 232 s2.push(1); 233 root = root->pLeft; 234 } 235 if(!s1.empty()) 236 { 237 if(s2.top()==1) 238 { 239 s2.pop(); 240 s2.push(2); 241 root = s1.top()->pRight; 242 } 243 else 244 { 245 root = s1.top(); 246 s1.pop(); 247 s2.pop(); 248 cout< 249 root = NULL; 250 } 251 } 252 253 } 254 255 } 256 257 template 258 void BiTree 259 { 260 PostOrderRecursive(root); 261 cout< 262 } 263 264 template 265 void BiTree 266 { 267 PostOrderNonRecursive(root); 268 cout< 269 } 270 271 template 272 void BiTree 273 { 274 BiNode 275 queue 276 if(root == NULL) 277 return; 278 q.push(root); 279 while(!q.empty()) 280 { 281 p = q.front(); 282 cout << p->data<<" "; 283 q.pop(); 284 if(p->pLeft != NULL) q.push(p->pLeft); 285 if(p->pRight != NULL) q.push(p->pRight); 286 } 287 } 288 289 template 290 void BiTree 291 { 292 LevelOrder(root); 293 cout< 294 } 295 296 int main() 297 { 298 299 300 ifstream fin("BiTree.txt");// 输入文件 301 ofstream fout("out.txt"); //输出文件 302 303 streambuf *cinbackup; 304 streambuf *coutbackup; 305 306 cinbackup= cin.rdbuf(fin.rdbuf()); //用 rdbuf() 重新定向 307 coutbackup= cout.rdbuf(fout.rdbuf()); //用 rdbuf() 重新定向 308 309 BiTree 310 311 cout << "*preorder = " << preorder << endl; 312 cout << " PreOrder1(): "; 313 pbitree->PreOrder1(); 314 cout << " PreOrder2(): "; 315 pbitree->PreOrder2(); 316 cout< 317 318 cout << "*inorder = " << inorder << endl; 319 cout << " inorder1(): "; 320 pbitree->InOrder1(); 321 cout << " InOrder2(): "; 322 pbitree->InOrder2(); 323 cout< 324 325 cout << "*postorder = " << postorder << endl; 326 cout << " PostOrder1(): "; 327 pbitree->PostOrder1(); 328 cout << " PostOrder2(): "; 329 pbitree->PostOrder2(); 330 cout< 331 332 cout << "*levelorder = " << levelorder << endl; 333 cout << " LevelOrder(): "; 334 pbitree->LevelOrder(); 335 336 delete pbitree; 337 cin.rdbuf(cinbackup); // 取消,恢复键盘输入 338 cout.rdbuf(coutbackup); //取消,恢复屏幕输出 339 return 0; 340 }电脑资料
《二叉树基础 创建,遍历方法(前序/中序/后序/层序、递归/非递归)》(http://meiwen.anslib.com)。