Shulou(Shulou.com)06/03 Report--

这篇文章主要讲解了"Java二叉树有哪几种遍历"，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习"Java二叉树有哪几种遍历"吧!

目录

一、先序遍历与后序遍历

二、中序遍历

三、层序遍历

一、先序遍历与后序遍历

先序遍历根节点，再遍历左子树，再遍历右子树。

后序遍历先遍历左子树，再遍历右子树，再遍历根节点。

先序遍历递归实现：

public static void preOrderByRecursion(TreeNode root) { // 打印节点值 System.out.println(root.value); preOrder(root.left); preOrder(root.right);}

先序遍历的非递归实现：

非递归实现需要借助栈这样一个数据结构，实际上递归实现也是依靠栈，只不过是隐式的。

先将根节点压入栈中。

弹出栈中的节点，将弹出节点的右子节点压入栈中，再将弹出节点的左子树压入栈中。

重复步骤2，直到栈为空。

public static void preOrder(TreeNode root) { if (root == null) { return; } Stack stack = new Stack(); stack.push(root); while (!stack.empty()) { TreeNode node = stack.pop(); // 打印节点值 System.out.print(node.value + " "); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } }}

后序遍历递归实现：先序遍历反过来，就不赘述了。

public static void postOrderByRecursion(TreeNode root) { postOrderByRecursion(root.left); postOrderByRecursion(root.right); System.out.println(root.value);}

后序遍历非递归实现：后序遍历就是先序遍历反过来，所以需要两个栈，多出来的栈用来反向输出。

public static void postOrder(TreeNode root) { if (root == null) { return; } Stack s1 = new Stack(); Stack s2 = new Stack(); s1.push(root); while (!s1.empty()) { TreeNode node = s1.pop(); s2.push(node); if (node.left != null) { s1.push(node.left); } if (node.right != null) { s1.push(node.right); } } while (!s2.empty()) { System.out.println(s2.pop().value); }}二、中序遍历

中序遍历先遍历左子树，再遍历根节点，再遍历右子树。

递归遍历：

public static void inOrderByRecursion(TreeNode root) { if (root == null) { return; } inOrderByRecursion(root.left); // 打印节点值 System.out.println(root.value); inOrderByRecursion(root.right);}

非递归遍历：

将二叉树的左侧"边"从上到下依次压入栈中。

从栈中弹出节点

对以弹出节点的右子节点为根节点的子树，重复步骤1。

重复2、3步骤，直到栈为空。

public static void inOrder(TreeNode root) { if (root == null) { return; } Stack stack = new Stack(); TreeNode cur = root; while (cur != null) { stack.push(cur); cur = cur.left; } while (!stack.empty()) { TreeNode node = stack.pop(); System.out.println(node.value); cur = node.right; while (cur != null) { stack.push(cur); cur = cur.left; } }}三、层序遍历

层序遍历顾名思义就是一层一层，从左到右的遍历二叉树。需要用到队列这一数据结构。

将根节点推入队列。

从队列中取出一个节点。

先将取出节点的左子节点推入队列，再将取出节点的右子节点推入队列。

重复2、3步骤直到队列中无节点可取。

public static void floorOrder(TreeNode root) { if (root == null) { return; } Queue queue = new LinkedList(); queue.add(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); System.out.println(node.value); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } }}感谢各位的阅读，以上就是"Java二叉树有哪几种遍历"的内容了，经过本文的学习后，相信大家对Java二叉树有哪几种遍历这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是，小编将为大家推送更多相关知识点的文章，欢迎关注!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.