yeskery

二叉树遍历的实现方式

介绍

所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一,是二叉树上进行其它运算之基础。二叉树的遍历分为:前序遍历、中序遍历和后序遍历。

实现

  1. public class BinaryTreeTraversal {
  2. /**
  3. * 二叉树结点类
  4. * @param <T> 二叉树存储的数据对象类型
  5. */
  6. private static class TreeNode<T> {
  7. /** 节点存储的值 */
  8. private T data;
  9. /** 左孩子节点 */
  10. private TreeNode<T> leftChild;
  11. /** 右孩子节点 */
  12. private TreeNode<T> rightChild;
  13. /**
  14. * 二叉树节点的构造方法
  15. * @param data 节点存储的值
  16. */
  17. TreeNode(T data) {
  18. this.data = data;
  19. }
  20. }
  21. /**
  22. * 标记节点类,用于二叉树的后序遍历时作标记使用
  23. * @param <T> 二叉树存储的数据对象类型
  24. */
  25. private static class TagNode<T> {
  26. /** 需要标记的节点 */
  27. private TreeNode<T> treeNode;
  28. /** 是否是第一次访问 */
  29. private boolean isFirst;
  30. }
  31. /**
  32. * 构建二叉树,用二叉树的前序遍历线性链表构建一颗二叉树
  33. * @param list 二叉树的前序遍历线性链表
  34. * @param <T> 二叉树存储的数据对象类型
  35. * @return 构建后的二叉树根节点
  36. */
  37. public static <T> TreeNode<T> createBinaryNode(LinkedList<T> list) {
  38. if (list == null || list.isEmpty()) {
  39. return null;
  40. }
  41. TreeNode<T> node = null;
  42. T data = list.removeFirst();
  43. if (data != null) {
  44. node = new TreeNode<>(data);
  45. node.leftChild = createBinaryNode(list);
  46. node.rightChild = createBinaryNode(list);
  47. }
  48. return node;
  49. }
  50. /**
  51. * 二叉树的前序遍历,用递归实现
  52. * @param node 需要遍历的节点
  53. * @param <T> 二叉树存储的数据对象类型
  54. */
  55. public static <T> void preOrderTraversalByRecursion(TreeNode<T> node) {
  56. if (node == null) {
  57. return;
  58. }
  59. System.out.print(node.data + " ");
  60. preOrderTraversalByRecursion(node.leftChild);
  61. preOrderTraversalByRecursion(node.rightChild);
  62. }
  63. /**
  64. * 二叉树的中序遍历,用递归实现
  65. * @param node 需要遍历的节点
  66. * @param <T> 二叉树存储的数据对象类型
  67. */
  68. public static <T> void midOrderTraversalByRecursion(TreeNode<T> node) {
  69. if (node == null) {
  70. return;
  71. }
  72. midOrderTraversalByRecursion(node.leftChild);
  73. System.out.print(node.data + " ");
  74. midOrderTraversalByRecursion(node.rightChild);
  75. }
  76. /**
  77. * 二叉树的后序遍历,用递归实现
  78. * @param node 需要遍历的节点
  79. * @param <T> 二叉树存储的数据对象类型
  80. */
  81. public static <T> void postOrderTraversalByRecursion(TreeNode<T> node) {
  82. if (node == null) {
  83. return;
  84. }
  85. postOrderTraversalByRecursion(node.leftChild);
  86. postOrderTraversalByRecursion(node.rightChild);
  87. System.out.print(node.data + " ");
  88. }
  89. /**
  90. * 二叉树的前序遍历,用栈实现
  91. *
  92. * 这种实现类似于图的深度优先遍历(DFS)。维护一个栈,将根节点入栈,然后只要
  93. * 栈不为空,出栈并访问,接着依次访问节点的右节点、左节点入栈。
  94. *
  95. * 这种方式应该是对前序遍历的一种特殊实现(看上去简单明了),但是不具备很好的
  96. * 扩展性,在中序遍历和后序遍历方式中不适用
  97. *
  98. * @param root 需要遍历的根节点
  99. * @param <T> 二叉树存储的数据对象类型
  100. */
  101. public static <T> void preOrderTraversalByStack(TreeNode<T> root) {
  102. if (root == null) {
  103. return;
  104. }
  105. Stack<TreeNode<T>> stack = new Stack<>();
  106. stack.push(root);
  107. while (!stack.isEmpty()) {
  108. TreeNode<T> node = stack.pop();
  109. System.out.print(node.data + " ");
  110. if (node.rightChild != null) {
  111. stack.push(node.rightChild);
  112. }
  113. if (node.leftChild != null) {
  114. stack.push(node.leftChild);
  115. }
  116. }
  117. }
  118. /**
  119. * 二叉树的前序遍历,用栈实现
  120. *
  121. * 利用栈模拟递归过程实现循环前序遍历二叉树,这种方式具有扩展性,它模拟递归的
  122. * 过程,将左子树节点不断压入栈,直到 <code>null</code>,然后再处理栈顶节点
  123. * 的右子树。
  124. *
  125. * @param root 需要遍历的根节点
  126. * @param <T> 二叉树存储的数据对象类型
  127. */
  128. public static <T> void preOrderTraversalByStack2(TreeNode<T> root) {
  129. if (root == null) {
  130. return;
  131. }
  132. Stack<TreeNode<T>> stack = new Stack<>();
  133. TreeNode<T> node = root;
  134. while (node != null || !stack.isEmpty()) {
  135. // 访问节点的的左孩子,并入栈
  136. while (node != null) {
  137. System.out.print(node.data + " ");
  138. stack.push(node);
  139. node = node.leftChild;
  140. }
  141. // 如果节点没有左孩子,则弹出栈顶节点,访问节点右孩子
  142. if (!stack.isEmpty()) {
  143. node = stack.pop();
  144. node = node.rightChild;
  145. }
  146. }
  147. }
  148. /**
  149. * 二叉树的中序遍历,用栈实现
  150. *
  151. * 利用栈模拟递归过程实现循环中序遍历二叉树,思想和上面先序非递归2
  152. * {@link #preOrderTraversalByStack2(TreeNode)} 相同,只是访问的时间是在
  153. * 左子树都处理完 <code>null</code> 的时候出栈并访问
  154. *
  155. * @param root 需要遍历的根节点
  156. * @param <T> 二叉树存储的数据对象类型
  157. */
  158. public static <T> void midOrderTraversalByStack(TreeNode<T> root) {
  159. if (root == null) {
  160. return;
  161. }
  162. Stack<TreeNode<T>> stack = new Stack<>();
  163. TreeNode<T> node = root;
  164. while (node != null || !stack.isEmpty()) {
  165. // 访问节点的的左孩子,并入栈
  166. while (node != null) {
  167. stack.push(node);
  168. node = node.leftChild;
  169. }
  170. // 如果节点没有左孩子,则弹出栈顶节点,访问节点右孩子
  171. if (!stack.isEmpty()) {
  172. node = stack.pop();
  173. System.out.print(node.data + " ");
  174. node = node.rightChild;
  175. }
  176. }
  177. }
  178. /**
  179. * 二叉树的后序遍历,用栈实现,额外借助一个 {@link TagNode} 类来实现标记。
  180. *
  181. * 后续遍历不同于先序和中序,它是要先处理完左子树和右子树,然后再处理根节点(回溯)
  182. *
  183. * 对于任一节点p,将其入栈,然后沿其左子树一直往下搜索,直到搜索到没有左孩子出现
  184. * 的节点,此时该节点还未出现在栈顶,但是此时不能将其出栈并访问,因为其右孩子还
  185. * 未被访问。
  186. *
  187. * 所以接下来按照相同的规则对其右子树进行相同的处理,当访问完右子树时,该节点又
  188. * 出现在栈顶,此时可以将其出栈并访问,这样就保证了正确的访问顺序。
  189. *
  190. * 可以看出,在这个过程中,每个节点都两次出现在栈顶,只有第二次出现在栈顶时,才能
  191. * 访问它。因此需要多设置一个变量标识该节点是否第一次出现在栈顶,这里是在树结构里
  192. * 加一个标记,然后合成一个新的 {@link TagNode} 。
  193. *
  194. * @param root 需要遍历的根节点
  195. * @param <T> 二叉树存储的数据对象类型
  196. */
  197. public static <T> void postOrderTraversalByStack(TreeNode<T> root) {
  198. if (root == null) {
  199. return;
  200. }
  201. Stack<TagNode<T>> stack = new Stack<>();
  202. TreeNode<T> node = root;
  203. TagNode<T> tagNode;
  204. while (node != null || !stack.isEmpty()) {
  205. // 沿着左子树一直往下搜索,直至出现没有左孩子的节点
  206. while (node != null) {
  207. tagNode = new TagNode<>();
  208. tagNode.treeNode = node;
  209. tagNode.isFirst = true;
  210. stack.push(tagNode);
  211. node = node.leftChild;
  212. }
  213. if (!stack.isEmpty()) {
  214. tagNode = stack.pop();
  215. // 表示第一次出现在栈顶
  216. if (tagNode.isFirst) {
  217. tagNode.isFirst = false;
  218. stack.push(tagNode);
  219. node = tagNode.treeNode.rightChild;
  220. } else {
  221. //第二次出现在栈顶
  222. System.out.print(tagNode.treeNode.data + " ");
  223. node = null;
  224. }
  225. }
  226. }
  227. }
  228. /**
  229. * 二叉树的后序遍历,用栈实现,无需额外借助其它类来判断节点是否访问。
  230. *
  231. * 要保证根节点在左孩子和右孩子访问之后才能访问,因此对于任一节点p,先将其入栈。
  232. * 如果p不存在左孩子和右孩子,则可以直接访问它。
  233. *
  234. * 或者p存在左孩子和或右孩子,但其左孩子和右孩子都已经被访问过了,则同样可以直接
  235. * 访问该节点。
  236. *
  237. * 若非上述两种情况,则将p的右孩子和左孩子依次入栈,这样就保证了每次取栈顶元素的
  238. * 时候,左孩子在右孩子前面被访问,左孩子和右孩子都在根节点前面被访问。
  239. *
  240. * @param root 需要遍历的根节点
  241. * @param <T> 二叉树存储的数据对象类型
  242. */
  243. public static <T> void postOrderTraversalByStack2(TreeNode<T> root) {
  244. if (root == null) {
  245. return;
  246. }
  247. Stack<TreeNode<T>> stack = new Stack<>();
  248. TreeNode<T> currentNode = null, preNode = null;
  249. stack.push(root);
  250. while (!stack.isEmpty()) {
  251. currentNode = stack.peek();
  252. // 如果当前节点没有孩子节点或者孩子节点都已经被访问过
  253. boolean isLeafNode = currentNode.leftChild == null && currentNode.rightChild == null;
  254. boolean isVisited = (preNode != null && (preNode == currentNode.leftChild
  255. || preNode == currentNode.rightChild));
  256. if (isLeafNode || isVisited) {
  257. System.out.print(currentNode.data + " ");
  258. stack.pop();
  259. preNode = currentNode;
  260. } else {
  261. if (currentNode.rightChild != null) {
  262. stack.push(currentNode.rightChild);
  263. }
  264. if (currentNode.leftChild != null) {
  265. stack.push(currentNode.leftChild);
  266. }
  267. }
  268. }
  269. }
  270. /**
  271. * 二叉树的层级遍历,使用队列实现
  272. * @param root 需要遍历的根节点
  273. * @param <T> 二叉树存储的数据对象类型
  274. */
  275. public static <T> void levelOrderTraversalByQueue(TreeNode<T> root) {
  276. Queue<TreeNode<T>> queue = new LinkedList<>();
  277. queue.offer(root);
  278. while (!queue.isEmpty()) {
  279. TreeNode<T> node = queue.poll();
  280. System.out.print(node.data + " ");
  281. if (node.leftChild != null) {
  282. queue.offer(node.leftChild);
  283. }
  284. if (node.rightChild != null) {
  285. queue.offer(node.rightChild);
  286. }
  287. }
  288. }
  289. /**
  290. * 二叉树的层级遍历,使用递归实现,对层级相同的节点进行输出
  291. * @param root 需要遍历的根节点
  292. * @param <T> 二叉树存储的数据对象类型
  293. */
  294. public static <T> void levelOrderTraversalByRecursion(TreeNode<T> root) {
  295. int depth = depth(root);
  296. for (int i = 0; i < depth; i++) {
  297. doLevelOrderTraversalByRecursion(root, 0, i);
  298. }
  299. }
  300. /**
  301. * 对二叉树相同层级的节点进行递归输出
  302. * @param node 需要遍历的根节点
  303. * @param level 遍历层级
  304. * @param target 目标层级
  305. * @param <T> 二叉树存储的数据对象类型
  306. */
  307. private static <T> void doLevelOrderTraversalByRecursion(TreeNode<T> node, int level, int target) {
  308. if (node == null) {
  309. return;
  310. }
  311. if (level == target) {
  312. System.out.print(node.data + " ");
  313. }
  314. doLevelOrderTraversalByRecursion(node.leftChild, level + 1, target);
  315. doLevelOrderTraversalByRecursion(node.rightChild, level + 1, target);
  316. }
  317. /**
  318. * 求二叉树的深度
  319. * @param root 需要遍历的根节点
  320. * @return 二叉树的根节点
  321. */
  322. private static int depth(TreeNode root) {
  323. if (root == null) {
  324. return 0;
  325. }
  326. return Integer.max(depth(root.leftChild), depth(root.rightChild)) + 1;
  327. }
  328. public static void main(String[] args) {
  329. // 构建二叉树
  330. LinkedList<Integer> list = new LinkedList<>(Arrays.asList(3, 2, 9, null, null,
  331. 10, null, null, 8, null, 4));
  332. TreeNode<Integer> root = createBinaryNode(list);
  333. System.out.print("前序遍历(递归):");
  334. preOrderTraversalByRecursion(root);
  335. System.out.println();
  336. System.out.print("中序遍历(递归):");
  337. midOrderTraversalByRecursion(root);
  338. System.out.println();
  339. System.out.print("后序遍历(递归):");
  340. postOrderTraversalByRecursion(root);
  341. System.out.println();
  342. System.out.print("前序遍历1(栈):");
  343. preOrderTraversalByStack(root);
  344. System.out.println();
  345. System.out.print("前序遍历2(栈):");
  346. preOrderTraversalByStack2(root);
  347. System.out.println();
  348. System.out.print("中序遍历(栈):");
  349. midOrderTraversalByStack(root);
  350. System.out.println();
  351. System.out.print("后序遍历1(栈):");
  352. postOrderTraversalByStack(root);
  353. System.out.println();
  354. System.out.print("后序遍历2(栈):");
  355. postOrderTraversalByStack2(root);
  356. System.out.println();
  357. System.out.print("层级遍历(队列):");
  358. levelOrderTraversalByQueue(root);
  359. System.out.println();
  360. System.out.print("层级遍历(递归):");
  361. levelOrderTraversalByRecursion(root);
  362. System.out.println();
  363. }
  364. }

评论

发表评论 点击刷新验证码

提示

该功能暂未开放