0.

二叉树是常见的数据结构，二叉树常见的遍历方式有前序遍历，中序遍历和后序遍历。前序遍历就是中-左-右节点的顺序，中序遍历就是左-中-右节点的顺序，后序遍历就是左-右-中节点的顺序。这三种遍历最常见的实践方式就是利用递归了，但是大家都明白，递归其实是可以用循环来代替的，所以除了递归的方式，还要循环的方法，同时递归还可以理解为栈的入栈和出栈的过程，配合循环，就可以实现相应的非递归遍历。

1.

由于实在太过简单，不说了，直接上代码：

<pre class="prettyprint linenums prettyprinted" style="box-sizing: border-box; margin: 0px; padding: 8px 0px 6px; font-family: consolas, menlo, courier, monospace, "Microsoft Yahei" !important; background: rgb(241, 239, 238); border: 1px solid rgb(226, 226, 226) !important; display: block; border-radius: 0px; overflow-y: auto; color: rgb(80, 97, 109); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 300; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial; font-size: 10px; line-height: 12px;">

1. //前序递归遍历

2. private void perorder(TreeNode treeNode)

3. {

4. if(treeNode!=null)

5. {

6. System.out.println("node is "+treeNode.val);

7. perorder(treeNode.left);

8. perorder(treeNode.right);

9. }

10. }

11. //前序非递归遍历

12. private void perorder(Stack<TreeNode> stack, TreeNode treeNode)

13. {

14. if(treeNode==null)

15. {

16. return;

17. }

18. TreeNode temp=treeNode;

19. while(temp!=null)

20. {

21. System.out.println("node is "+temp.val);

22. if(temp.right!=null)

23. {

24. stack.push(temp.right);

25. }

26. if(temp.left!=null)

27. {

28. stack.push(temp.left);

29. }

30. if(stack.empty())

31. {

32. break;

33. }

34. temp=stack.peek();

35. stack.pop();

36. }

37. }

38. //中序递归遍历

39. private void midorder(TreeNode treeNode)

40. {

41. if(treeNode!=null)

42. {

43. midorder(treeNode.left);

44. System.out.println("node is "+treeNode.val);

45. midorder(treeNode.right);

46. }

47. }

48. //中序非递归遍历

49. private void midorder(Stack<TreeNode> stack,TreeNode treeNode)

50. {

51. if(treeNode==null)

52. {

53. return;

54. }

55. TreeNode temp=treeNode;

56. while(!stack.empty() || temp!=null)

57. {

58. if(temp!=null)

59. {

60. stack.push(temp);

61. temp=temp.left;

62. }

63. else

64. {

65. temp=stack.pop();

66. System.out.println("node is "+temp.val);

67. temp=temp.right;

68. }

69. }

70. }

71. //后序递归遍历

72. private void endorder(TreeNode treeNode)

73. {

74. if(treeNode!=null)

75. {

76. endorder(treeNode.left);

77. endorder(treeNode.right);

78. System.out.println("node is "+treeNode.val);

79. }

80. }

81. //后序非递归遍历

82. private void endorder(Stack<TreeNode> stack,TreeNode treeNode)

83. {

84. if(treeNode==null)

85. {

86. return;

87. }

88. TreeNode temp=treeNode;

89. stack.push(treeNode);

90. while(!stack.empty())

91. {

92. TreeNode cur=stack.peek();

93. if(cur.left!=null && temp!=cur.left && temp!=cur.right)

94. {

95. stack.push(cur.left);

96. }

97. else if(cur.right!=null && temp!=cur.right)

98. {

99. stack.push(cur.right);

100. }

101. else

102. {

103. System.out.println("node is "+cur.val);

104. stack.pop();

105. temp=cur;

106. }

107. }

108. }

109. public static class TreeNode

110. {

111. int val;

112. TreeNode left;

113. TreeNode right;

114. public TreeNode(int val)

115. {

116. this.val=val;

117. }

118. }

</pre>

image

关注我的公众号