二叉树基础创建，遍历方法(前序/中序/后序/层序、递归/非递归） -电脑资料

电脑资料时间：2019-01-01 我要投稿

【www.unjs.com - 电脑资料】

二叉树的创建及遍历是很多二叉树问题的基础，递归遍历逻辑清晰，代码简约漂亮，然则效率低下（所有递归方案的通病，非不得已不用递归）；

非递归遍历高效，却不是能信手写出来的，特别是后续非递归遍历，相信很多资深码工也有这样的经历：

5年前学习了二叉树的非递归遍历，一个月前复习了并达到能熟练写出的程度，在不参考任何资料的情况下，今天却怎样也写不出来，

二叉树基础创建，遍历方法(前序/中序/后序/层序、递归/非递归）

。

如果你也有过这种经历，恭喜你，这说明你是一个正常人……

另一方面市面上有些国人写的教材，各种语法、逻辑错误层出不起，不知祸害了多少未来的码工，深感痛心。

印象比较深刻的有清华大学出版社出版的《数据结果（C++版）》王红梅、胡明、王涛编著。

如书中第163页后序非递归遍历方法，短短不到30行代码各种语法、逻辑错误如下：

1 template

2 void BiTree::PostOrder(BiNode * root)//错误一：正确的写法为void BiTree::PostOrder(BiNode * root)

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 *pLeft;

6 BiNode *pRight;

7 };

二叉树Class定义：

要点：1.数据成员申明为私有（原因见Effective C++ 条款21：将成员变量申明为private）；

2. 公有成员方法如PreOrder1()为对外接口，调用私用方法PreOrderRecursive(BiNode * root)实现具体其功能。

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 * root;

16 void CreateBiTree(BiNode * &root);

17 void ReleaseBiTree(BiNode * root);

19 void PreOrderRecursive(BiNode * root);

20 void PreOrderNonRecursive(BiNode * root);

22 void InOrderRecursive(BiNode * root);

23 void InOrderNonRecursive(BiNode * root);

25 void PostOrderRecursive(BiNode * root);

26 void PostOrderNonRecursive(BiNode * root);

28 void LevelOrder(BiNode * root);

29 };

创建二叉树：

1 template

2 void BiTree::CreateBiTree( BiNode * &root)// 根据前序遍历次序创建二叉树

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 }

20 template

21 BiTree::BiTree():root(NULL)

22 {

23 CreateBiTree(root);

24 }

销毁二叉树：

1 template

2 void BiTree::ReleaseBiTree(BiNode * root)

3 {

4 if(root != NULL)

5 {

6 ReleaseBiTree(root->pLeft);

7 ReleaseBiTree(root->pRight);

8 delete root;

9 }

10 }

13 template

14 BiTree::~BiTree()

15 {

16 ReleaseBiTree(root);

17 }

前序递归遍历：

1 template

2 void BiTree::PreOrderRecursive(BiNode * root)

3 {

4 if(root != NULL)

5 {

6 cout<data<<" ";

7 PreOrderRecursive(root->pLeft);

8 PreOrderRecursive(root->pRight);

9 }

10 }

14 template

15 void BiTree::PreOrder1()

16 {

17 PreOrderRecursive(root);

18 cout<

19 }

中序递归遍历：

1 template

2 void BiTree::InOrderRecursive(BiNode * root)

3 {

4 if(root != NULL)

5 {

6 InOrderRecursive(root->pLeft);

7 cout<data<<" ";

8 InOrderRecursive(root->pRight);

9 }

10 }

13 template

14 void BiTree::InOrder1()

15 {

16 InOrderRecursive(root);

17 cout<

18 }

后序递归遍历：

1 template

2 void BiTree::PostOrderRecursive(BiNode * root)

3 {

4 if(root != NULL)

5 {

6 PostOrderRecursive(root->pLeft);

7 PostOrderRecursive(root->pRight);

8 cout<data<<" ";

9 }

10 }

13 template

14 void BiTree::PostOrder1()

15 {

16 PostOrderRecursive(root);

17 cout<

18 }

层序遍历：

1 template

2 void BiTree::LevelOrder(BiNode * root)

3 {

4 BiNode * p;

5 queue *> q;

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 }

19 template

20 void BiTree::LevelOrder()

21 {

22 LevelOrder(root);

23 cout<

24 }

前序非递归遍历：

1 template

2 void BiTree:: PreOrderNonRecursive(BiNode * root)

3 {

4 stack *> s;

5 while(root != NULL || !s.empty())

6 {

7 while(root != NULL)

8 {

9 cout<data<<" ";

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 }

21 }

26 template

27 void BiTree::PreOrder2()

28 {

29 PreOrderNonRecursive(root);

30 cout<

31 }

中序非递归遍历：

1 template

2 void BiTree::InOrderNonRecursive(BiNode * root)

3 {

4 stack *> s;

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<data<<" ";

17 root = root->pRight;

18 }

19 }

21 }

25 template

26 void BiTree::InOrder2()

27 {

28 InOrderNonRecursive(root);

29 cout<

30 }

后序非递归遍历：

1 template

2 void BiTree::PostOrderNonRecursive(BiNode * root)

3 {

5 stack *> s1;

6 stack s2;//s2辅助记录s1相应位置的元素的状态：s1、s2保持同步。

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<data<<" ";

30 root = NULL;

31 }

32 }

34 }

36 }

38 template

39 void BiTree::PostOrder1()

40 {

41 PostOrderRecursive(root);

42 cout<

43 }

45 template

46 void BiTree::PostOrder2()

47 {

48 PostOrderNonRecursive(root);

49 cout<

50 }

假定我们创建的二叉树形状如下：

1 /*

2 假定所创建的二叉树如下图所示

3 A

4 / \

5 B C

6 / \ /

7 D E F

8 \

9 G

12 创建二叉树的文件：《BiTree.txt》内容如下:

13 A B D # # E # G # # C F # # #

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"); //输出文件

6 streambuf *cinbackup;

7 streambuf *coutbackup;

9 cinbackup= cin.rdbuf(fin.rdbuf()); //用 rdbuf() 重新定向

10 coutbackup= cout.rdbuf(fout.rdbuf()); //用 rdbuf() 重新定向

12 BiTree *pbitree = new BiTree;//创建一颗二叉树

14 cout << "*preorder = " << preorder << endl;

15 cout << " PreOrder1(): ";

16 pbitree->PreOrder1();

17 cout << " PreOrder2(): ";

18 pbitree->PreOrder2();

19 cout<

21 cout << "*inorder = " << inorder << endl;

22 cout << " inorder1(): ";

23 pbitree->InOrder1();

24 cout << " InOrder2(): ";

25 pbitree->InOrder2();

26 cout<

28 cout << "*postorder = " << postorder << endl;

29 cout << " PostOrder1(): ";

30 pbitree->PostOrder1();

31 cout << " PostOrder2(): ";

32 pbitree->PostOrder2();

33 cout<

35 cout << "*levelorder = " << levelorder << endl;

36 cout << " LevelOrder(): ";

37 pbitree->LevelOrder();

39 delete pbitree;

40 cin.rdbuf(cinbackup); // 取消，恢复键盘输入

41 cout.rdbuf(coutbackup); //取消，恢复屏幕输出

42 return 0;

43 }

完整的代码：

1 #include

2 #include

3 #include

4 #include

6 using namespace std;

9 /*

10 假定所创建的二叉树如下图所示

11 A

12 / \

13 B C

14 / \ /

15 D E F

16 \

17 G

20 创建二叉树的文件：《BiTree.txt》内容如下:

21 A B D # # E # G # # C F # # #

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";

29 const char INVALID = '#';//INVALID在CreateBiTree()函数中表示空节点，类型适配 template

31 template

32 struct BiNode

33 {

34 T data;

35 BiNode *pLeft;

36 BiNode *pRight;

37 };

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 * root;

54 void CreateBiTree(BiNode * &root);

55 void ReleaseBiTree(BiNode * root);

57 void PreOrderRecursive(BiNode * root);

58 void PreOrderNonRecursive(BiNode * root);

60 void InOrderRecursive(BiNode * root);

61 void InOrderNonRecursive(BiNode * root);

63 void PostOrderRecursive(BiNode * root);

64 void PostOrderNonRecursive(BiNode * root);

66 void LevelOrder(BiNode * root);

67 };

70 template

71 void BiTree::CreateBiTree( BiNode * &root)// 根据前序遍历次序创建二叉树

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 }

89 template

90 void BiTree::ReleaseBiTree(BiNode * root)

91 {

92 if(root != NULL)

93 {

94 ReleaseBiTree(root->pLeft);

95 ReleaseBiTree(root->pRight);

96 delete root;

97 }

98 }

99 template

100 BiTree::BiTree():root(NULL)

101 {

102 CreateBiTree(root);

103 }

104

105

106 template

107 BiTree::~BiTree()

108 {

109 ReleaseBiTree(root);

110 }

111

112

113 template

114 void BiTree::PreOrderRecursive(BiNode * root)

115 {

116 if(root != NULL)

117 {

118 cout<data<<" ";

119 PreOrderRecursive(root->pLeft);

120 PreOrderRecursive(root->pRight);

121 }

122 }

123

124 template

125 void BiTree:: PreOrderNonRecursive(BiNode * root)

126 {

127 stack *> s;

128 while(root != NULL || !s.empty())

129 {

130 while(root != NULL)

131 {

132 cout<data<<" ";

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::PreOrder1()

149 {

150 PreOrderRecursive(root);

151 cout<

152 }

153

154 template

155 void BiTree::PreOrder2()

156 {

157 PreOrderNonRecursive(root);

158 cout<

159 }

160

161 template

162 void BiTree::InOrderRecursive(BiNode * root)

163 {

164 if(root != NULL)

165 {

166 InOrderRecursive(root->pLeft);

167 cout<data<<" ";

168 InOrderRecursive(root->pRight);

169 }

170 }

171

172 template

173 void BiTree::InOrderNonRecursive(BiNode * root)

174 {

175 stack *> s;

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<data<<" ";

188 root = root->pRight;

189 }

190 }

191

192 }

193

194 template

195 void BiTree::InOrder1()

196 {

197 InOrderRecursive(root);

198 cout<

199 }

200

201

202 template

203 void BiTree::InOrder2()

204 {

205 InOrderNonRecursive(root);

206 cout<

207 }

208

209 template

210 void BiTree::PostOrderRecursive(BiNode * root)

211 {

212 if(root != NULL)

213 {

214 PostOrderRecursive(root->pLeft);

215 PostOrderRecursive(root->pRight);

216 cout<data<<" ";

217 }

218 }

219

220 template

221 void BiTree::PostOrderNonRecursive(BiNode * root)

222 {

223

224 stack *> s1;

225 stack s2;//s2辅助记录s1相应位置的元素的状态：s1、s2保持同步，

电脑资料

《二叉树基础创建，遍历方法(前序/中序/后序/层序、递归/非递归）》(https://www.unjs.com)。

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<data<<" ";

249 root = NULL;

250 }

251 }

252

253 }

254

255 }

256

257 template

258 void BiTree::PostOrder1()

259 {

260 PostOrderRecursive(root);

261 cout<

262 }

263

264 template

265 void BiTree::PostOrder2()

266 {

267 PostOrderNonRecursive(root);

268 cout<

269 }

270

271 template

272 void BiTree::LevelOrder(BiNode * root)

273 {

274 BiNode * p;

275 queue *> q;

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::LevelOrder()

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 *pbitree = new 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 }

相关文章

二叉树基础 创建，遍历方法(前序/中序/后序/层序、递归/非递归） -电脑资料

二叉树基础 创建，遍历方法(前序/中序/后序/层序、递归/非递归）

电脑资料

二叉树基础创建，遍历方法(前序/中序/后序/层序、递归/非递归） -电脑资料

二叉树基础创建，遍历方法(前序/中序/后序/层序、递归/非递归）