Java学习教程-二叉树的前序中序后序遍历[非递归方式].docx

1. packagetree.binarytree;2. 3. importjava.util.LinkedList;4. importjava.util.Queue;5. importjava.util.Random;6. importjava.util.Stack;7. 8. /*9. *CreatedbyLanxiaowei10. *Craatedon2016/12/1217:1411. *采用二叉排序树的中序遍历实现对一个无序的数字序列进行排序12. */13. publicclassTestBinarySortTree214. 15. publicstaticvoidmain(Stringargs)16. /测试100次17. /test(100);18. 19. test2();20. 21. 22. publicstaticvoidtest2()23. BinarySortTreeNodeparentNode=newBinarySortTreeNode(5);24. 25. BinarySortTreeNodec3=newBinarySortTreeNode(3);26. BinarySortTreeNodec6=newBinarySortTreeNode(6);27. BinarySortTreeNodec1=newBinarySortTreeNode(1);28. BinarySortTreeNodec4=newBinarySortTreeNode(4);29. 30. BinarySortTreeNodec8=newBinarySortTreeNode(8);31. BinarySortTreeNodec9=newBinarySortTreeNode(9);32. 33. c8.left=c3;34. c8.right=c6;35. 36. c9.left=c1;37. c9.right=c4;38. 39. parentNode.left=c8;40. parentNode.right=c9;41. 42. /中序遍历二叉树(非递归方式)43. Queuequeue=parentNode.midOrderWithoutRecursive(parentNode);44. while(!queue.isEmpty()45. inti=queue.poll();46. System.out.print(i+);47. 48. 49. System.out.println();50. /前序遍历二叉树(非递归方式)51. queue=parentNode.preOrderWithoutRecursive(parentNode);52. while(!queue.isEmpty()53. inti=queue.poll();54. System.out.print(i+);55. 56. System.out.println();57. 58. /后序遍历二叉树(非递归方式)59. queue=parentNode.postOrderWithoutRecursive(parentNode);60. while(!queue.isEmpty()61. inti=queue.poll();62. System.out.print(i+);63. 64. System.out.println();65. 66. /后序遍历二叉树(非递归方式)-另一种实现67. queue=parentNode.postorderTraversal(parentNode);68. while(!queue.isEmpty()69. inti=queue.poll();70. System.out.print(i+);71. 72. System.out.println();73. System.out.println(/*华丽的分割线end*/n);74. 75. 76. /*77. *测试方法78. *paramtimes测试的总次数79. */80. publicstaticvoidtest(inttimes)81. if(times0)86. System.out.println(/*华丽的分割线begin*/);87. intmin=1;88. intmax=100;89. /先随机生成一个随机数作为二叉树的父节点90. intparentVal=random(min,max);91. /打印生成的parent节点数值92. System.out.println(Parent:+parentVal);93. /创建二叉树的父节点94. BinarySortTreeNodeparentNode=newBinarySortTreeNode(parentVal);95. /假设我们的无序数字序列的长度n=10,这里我们随机生成无序数字序列里的每个数字,然后插入二叉树结构中96. intn=10;97. /用于存储每个子节点的数值98. intnum=0;99. /这里之所以是n-2,是因为我们已经生成了父节点,剩下我们只需要生成n-1个子节点,100. /而i是从零开始的,因此这里是n-2101. for(inti=0;in-2;i+)102. /随机生成每个子节点的数值103. num=random(min,max);104. System.out.println(Child:+num);105. /创建每个子节点106. BinarySortTreeNodechild=newBinarySortTreeNode(num);107. /往二叉排序树里插入子节点108. parentNode.insert(parentNode,child);109. 110. 111. /中序遍历二叉树(非递归方式)112. Queuequeue=parentNode.midOrderWithoutRecursive(parentNode);113. while(!queue.isEmpty()114. inti=queue.poll();115. System.out.print(i+);116. 117. 118. System.out.println();119. /前序遍历二叉树(非递归方式)120. queue=parentNode.preOrderWithoutRecursive(parentNode);121. while(!queue.isEmpty()122. inti=queue.poll();123. System.out.print(i+);124. 125. System.out.println();126. 127. /后序遍历二叉树(非递归方式)128. queue=parentNode.postOrderWithoutRecursive(parentNode);129. while(!queue.isEmpty()130. inti=queue.poll();131. System.out.print(i+);132. 133. System.out.println();134. System.out.println(/*华丽的分割线end*/n);135. 136. 137. 138. /*139. *二叉排序树的每个节点140. */141. publicstaticclassBinarySortTreeNode142. /左子节点143. privateBinarySortTreeNodeleft;144. /右子节点145. privateBinarySortTreeNoderight;146. /*节点上的值*/147. privateintval;148. 149. publicBinarySortTreeNode()150. 151. publicBinarySortTreeNode(intval)152. this.val=val;153. 154. 155. /*156. *往指定的父节点上插入一个子节点157. *paramparentNode父节点158. *paramnewNode待插入的节点159. *return160. */161. publicbooleaninsert(BinarySortTreeNodeparentNode,BinarySortTreeNodenewNode)162. if(null=newNode)163. thrownewIllegalArgumentException(TheNodetobeinsertedMUSTNOTbenull.);164. 165. if(null=parentNode)166. parentNode=newNode;167. returntrue;168. 169. /若待插入的节点数值大于等于父节点,则待插入的newNode此时应该在右边170. if(parentNode.valnewNode.val)182. /如果父节点此刻的左树为空,那么就将待插入的newNode作为父节点左树的父节点183. if(parentNode.left=null)184. parentNode.left=newNode;185. returntrue;186. else187. /如果父节点的左树不为空,那么就插入到左树的父节点下188. returninsert(parentNode.left,newNode);189. 190. 191. returnfalse;192. 193. 194. /*195. *在指定的父节点为parentNode的二叉树下查找是否存在一个数字x196. *paramparentNode二叉树的父节点197. *paramx待查找的数字x198. *return199. */200. publicbooleansearch(BinarySortTreeNodeparentNode,intx)201. /如果二叉树为null,直接returnfalse202. if(null=parentNode)203. returnfalse;204. 205. /此时说明找到数字x了,直接returntrue206. if(parentNode.val=x)207. returntrue;208. 209. /此时应该在右子树中查找210. if(parentNode.valx)215. returnsearch(parentNode.left,x);216. 217. returnfalse;218. 219. 220. /*221. *中序遍历(递归方式实现)222. *paramparentNode223. */224. publicvoidmidorder(BinarySortTreeNodeparentNode)225. if(null=parentNode)226. return;227. 228. midorder(parentNode.left);229. System.out.print(parentNode.val+);230. midorder(parentNode.right);231. 232. 233. /*234. *二叉树前序遍历(非递归方式)235. *paramparentNode236. *return237. */238. publicQueuepreOrderWithoutRecursive(BinarySortTreeNodeparentNode)239. Stackstack=newStack();240. Queuequeue=newLinkedList();241. BinarySortTreeNodecurrentParent=parentNode;242. 243. /当前节点非空或者Stack非空时执行244. while(currentParent!=null|!stack.isEmpty()245. /先放父节点246. queue.add(currentParent.val);247. stack.push(currentParent);248. /然后遍历左子树249. currentParent=currentParent.left;250. while(currentParent=null&!stack.isEmpty()251. currentParent=stack.peek();252. stack.pop();253. /然后遍历右子树254. currentParent=currentParent.right;255. 256. 257. returnqueue;258. 259. 260. /*261. *二叉树后序遍历(非递归方式)262. *这种后序遍历实现方式相比postorderTraversal实现而言,性能更高效263. *左子树右子树中间父节点264. *paramparentNode265. *return266. */267. publicQueuepostOrderWithoutRecursive(BinarySortTreeNodeparentNode)268. longstart=System.nanoTime();269. Queuequeue=newLinkedList();270. BinarySortTreeNodedummy=newBinarySortTreeNode(0);271. dummy.left=parentNode;272. BinarySortTreeNodecur=dummy;273. BinarySortTreeNodepre=null;274. while(cur!=null)275. if(cur.left=null)276. cur=cur.right;277. else278. pre=cur.left;279. while(pre.right!=null&pre.right!=cur)280. pre=pre.right;281. 282. if(pre.right=null)283. pre.right=cur;284. cur=cur.left;285. else286. reverse(cur.left,pre);287. BinarySortTreeNodetemp=pre;288. while(temp!=cur.left)289. queue.add(temp.val);290. temp=temp.right;291. 292. queue.add(temp.val);293. reverse(pre,cur.left);294. pre.right=null;295. cur=cur.right;296. 297. 298. 299. longend=System.nanoTime();300. System.out.println(postOrderWithoutRecursivetake+(end-start)+ns);301. returnqueue;302. 303. 304. /*305. *二叉树后序遍历(非递归方式)306. *paramroot307. *return308. */309. publicQueuepostorderTraversal(BinarySortTreeNoderoot)310. longstart=System.nanoTime();311. Queueresult=newLinkedList();312. Stackstack=newStack();313. BinarySortTreeNodeprev=null;314. BinarySortTreeNodecurr=root;315. if(root=null)316. returnresult;317. 318. stack.push(root);319. while(!stack.empty()320. curr=stack.peek();321. if(prev=null|prev.left=curr|prev.right=curr)322. if(curr.left!=null)323. stack.push(curr.left);324. elseif(curr.right!=null)325. stack.push(curr.right);326. 327. 328. /从左子树往上遍历329. elseif(curr.left=prev)330. if(curr.right!=null)331. stack.push(curr.right);332. 333. 334. /从右子树往上遍历335. else336. result.add(curr.val);337. stack.pop();338. 339. prev=curr;340. 341. longend=System.nanoTime();342. System.out.println(postorderTraversaltake+(end-start)+ns);343. returnresult;344. 345. 346. /*347. *二叉树的中序遍历(非递归方式)348. *paramparentNode349. *return350. */351. publicQueuemidOrderWithoutRecursive(BinarySortTreeNodeparentNode)352. Stackstack=newStack();353. Queuequeue=newLinkedList();354. BinarySortTreeNodecurrentParent=parentNode;355. BinarySortTreeNodenode=null;356. while(currentParent!=null|!stack.isEmpty()357. stack.push(currentParent);358. /先