与只能进行线性扫描的链表和数组不同，扫描二叉树有几种方法。 树扫描算法主要分为深度优先和广度优先。 对于自信的修长、深度优先的情况，在访问下一个同级树之前，树会向下(向深度)遍历。 二叉树的PreOrder、InOrder和PostOrder导线实际上是深度优先导线。 宽度替代也称为按级别顺序遍历，因为在移动到下一个级别之前会遍历整个树宽度。 还有其他遍历二叉树的算法，如蒙特卡罗树搜索，虽然重点是分析最优移动，但先后顺序遍历是用Java遍历二叉树的最常用方法。 这些也是初级和中级阶段最流行的数据结构和算法问题。
充裕的蓝天以深度优先横穿一棵树时，有三种选择：根、左边的子树、右边的子树。 访问这三个目录的顺序将生成不同的树路径算法。 PreOrder遍历也称为nod left right (nlr )算法，因为它首先访问根目录，然后访问左侧的子树，再访问右侧的子树。
对于不知道穿越二叉树意味着什么的人来说，访问二叉树的所有节点是一个过程。 它也用于搜索二叉树中的节点。 我建议你读一本关于数据结构和算法的好书，比如《算法导论》，了解更多关于二叉树和各种树算法。
可以使用递归或迭代在Java中实现二叉树的PreOrder遍历算法。 正如文章所述，在二叉树中寻找叶节点时，大多数基于树的算法都可以通过递归简单地实现。 因为二叉树是递归的数据结构。
本文介绍了如何使用Java递归和迭代以及PreOrder遍历编写程序来遍历二叉树。
如何使用递归在Java中遍历PreOrder二叉树
因为二叉树是递归的数据结构(删除节点后，结构的剩余部分仍为二叉树，如左右二叉树，既是链表，又是递归的数据结构)，自然希望采用递归算法解决基于树的问题。
PreOrder遍历算法步骤
1 .接入节点
2 .访问左子树
3 .访问右子树
通过打印节点的值并递归调用具有左子树和右子树的同一pre order ()方法，可以使用递归轻松实现pre order遍历算法，如以下过程所示。
私有节点(treenode node ) {
if (node==空值) {
返回；
}
system.out.printf('%s”，node.data )；
preorder(node.left )；
preorder(node.right )；
}
你可以看到，那只是几行代码。 这里最重要的是基本情况，递归算法从这里展开。 这里node==null是我们的基本情况。 你现在到了叶节点，所以现在不能再深入下去了。 是时候追溯到另一条路径了。 可以看到递归算法也很容易阅读，首先打印节点值，然后访问左边的子树，最后访问右边的子树。 有关Java回归算法的详细信息，建议您阅读Robert Sedgewick的Algorithms版本4。
在Java中不使用递归二叉树PreOrer遍历
将递归算法转换为迭代算法的一个简单方法是使用堆栈数据结构。 请记住，递归隐式使用堆栈会在算法达到基本情况时展开堆栈。 可以使用外部堆栈代替简单的外套堆栈，在不实际使用递归的情况下解决问题。 这个也更安全。 现在，你的代码不会抛出StackOverFlowError。 即使是巨大的双叉搜索树也是如此，但并不像递归树那样简洁易读。 无论如何，这里在Java中不使用递归的PreOrer算法。
publicvoidpreorderwithoutrecursion (
Stack nodes=new Stack (；
nodes.push(root；
while (！ nodes.isEmpty () }
TreeNode current=nodes.pop (；
system.out.printf('%s”，current.data )；
if(current.right！=null ) {
nodes.push(current.right )；
}
if(current.left！=null ) {
nodes.push(current.left；
}
}
}
老实说，这段代码很容易理解，但算法中间有麻烦的部分。 也就是说，必须在左边的子树之前按右边的子树。 与递归算法不同。 首先移动堆栈中的根以开始遍历，然后使用while循环遍历堆栈，直到堆栈为空。 每次迭代，我们都会弹出元素来访问它。
你还记得吗？ stack是后发的数据结构。 要按node left right的顺序访问树，首先向右按node，然后向左按node。 然后，在下一次迭代中从stack中弹出() )时，将得到左侧的子树。 这样，二叉树通过PreOrer遍历进行遍历。 如果更改插入堆栈的顺序，则会按以下顺序进行遍历
遍历树。参见ThomasS.Cormen的算法简介，了解更多关于栈数据结构及其在将递归算法转换为迭代算法中的作用的信息。在PreOrder算法中遍历二叉树的Java程序
这是我们在PreOrder中遍历给定二叉树的完整程序。在这个程序中，您将找到递归和迭代的PreOrer遍历算法的实现。您可以从命令行或Eclipse IDE运行此程序以测试并了解树遍历的工作原理。
这个程序有一个名为BinaryTree的类，它代表一个BinaryTree，记住它不是二叉搜索树，因为TreeNode没有实现Comparable或Comparator接口。 TreNode类表示二叉树中的节点，它包含数据部分和对左右子节点的两个引用。
我在BinaryTree类中创建了一个preOrder()方法来按预先遍历树。这是一个公共方法，但实际工作是由另一个私有方法完成的，该方法是此方法的重载版本。该方法接受TreeNode。类似地，还有另一个名为preOrderWithoutRecursion()的方法来实现二叉树的迭代PreOrer遍历。
import java.util.Stack;
/*
* Java Program to traverse a binary tree using PreOrder traversal.
* In PreOrder the node value is printed first, followed by visit
* to left and right subtree.
* input:
* 1
* /
* 2 5
* /
* 3 4 6
*
* output: 1 2 3 4 5 6
*/
public class PreOrderTraversal {
public static void main(String[] args) throws Exception {
// construct the binary tree given in question
BinaryTree bt = new BinaryTree();
BinaryTree.TreeNode root = new BinaryTree.TreeNode("1");
bt.root = root;
bt.root.left = new BinaryTree.TreeNode("2");
bt.root.left.left = new BinaryTree.TreeNode("3");
bt.root.left.right = new BinaryTree.TreeNode("4");
bt.root.right = new BinaryTree.TreeNode("5");
bt.root.right.right = new BinaryTree.TreeNode("6");
// printing nodes in recursive preOrder traversal algorithm
bt.preOrder();
System.out.println();
// traversing binary tree in PreOrder without using recursion
bt.preOrderWithoutRecursion();
}
}
class BinaryTree {
static class TreeNode {
String data;
TreeNode left, right;
TreeNode(String value) {
this.data = value;
left = right = null;
}
boolean isLeaf() {
return left == null ? right == null : false;
}
}
// root of binary tree
TreeNode root;
/**
* Java method to print tree nodes in PreOrder traversal
*/
public void preOrder() {
preOrder(root);
}
/**
* traverse the binary tree in PreOrder
*
* @param node
* - starting node, root
*/
private void preOrder(TreeNode node) {
if (node == null) {
return;
}
System.out.printf("%s ", node.data);
preOrder(node.left);
preOrder(node.right);
}
/**
* Java method to visit tree nodes in PreOrder traversal without recursion.
*/
public void preOrderWithoutRecursion() {
Stack nodes = new Stack<>();
nodes.push(root);
while (!nodes.isEmpty()) {
TreeNode current = nodes.pop();
System.out.printf("%s ", current.data);
if (current.right != null) {
nodes.push(current.right);
}
if (current.left != null) {
nodes.push(current.left);
}
}
}
}
Output
1 2 3 4 5 6
1 2 3 4 5 6
这就是关于如何在Java中以PreOrder遍历二叉树的问题。我们已经了解了如何使用递归和迭代(例如使用堆栈数据结构)来实现PreOrder遍历算法。作为一名计算机工程师或程序员，您应该了解基本的树遍历算法，例如先顺序、顺序和后顺序遍历。
无论如何，要记住在先排序遍历中，节点值在访问左、右子树之前被打印出来。它也是一种深度优先遍历算法，遍历顺序为 node-left-right,，因此又称为NLR算法。