Java中二叉樹的PreOrder遍歷——遞迴與迭代例項

二叉樹 Java · 發表 2019-02-22 11:48:00

摘要：與只能線性遍歷的連結串列和陣列不同，遍歷二叉樹有幾種方法。樹遍歷演算法主要分為深度優先和廣度優先兩部分。顧名思義，在深度優先的情況下，在訪問下一個同級樹之前，樹向下（向深度）遍歷，二叉樹的PreOrder，InOrder和PostOrder遍歷實際上是深度優先遍歷。在廣度優先上，樹的整個寬度在...

與只能線性遍歷的連結串列和陣列不同，遍歷二叉樹有幾種方法。樹遍歷演算法主要分為深度優先和廣度優先兩部分。顧名思義，在深度優先的情況下，在訪問下一個同級樹之前，樹向下（向深度）遍歷，二叉樹的PreOrder，InOrder和PostOrder遍歷實際上是深度優先遍歷。在廣度優先上，樹的整個寬度在移到下一個級別之前被遍歷，因此它也被稱為級別順序遍歷。還有其他遍歷二叉樹的演算法，例如蒙特卡洛樹搜尋，它集中於分析最優的移動，但先序、後序和順序遍歷是在Java中遍歷二叉樹的最流行的方法。它們也是初級和中級階段最流行的資料結構和演算法問題。

當你以深度優先的方式遍歷一棵樹時，你有三個選擇，例如根、左子樹和右子樹。根據您訪問這三個目錄的順序，會產生不同的樹遍歷演算法。在PreOrder遍歷中，首先訪問根目錄，然後訪問左子樹，然後訪問右子樹，因此它也被稱為NLR（nod left right）演算法。

對於那些不知道遍歷二叉樹的意義的人，訪問二叉樹的所有節點是一個過程。它還用於搜尋二叉樹中的節點。我還建議你讀一本關於資料結構和演算法的好書，例如《演算法導論》，瞭解更多關於二叉樹和各種樹演算法的知識。

您可以使用遞迴或迭代在Java中實現二叉樹PreOrder遍歷演算法。正如我在文章中提到的，在二叉樹中查詢葉節點時，大多數基於樹的演算法都可以使用遞迴輕鬆實現，因為二叉樹是一種遞迴資料結構。

在本文中，我將展示如何使用Java中的遞迴和迭代，以及PreOrder遍歷來編寫程式，遍歷二叉樹。

如何使用遞迴在Java中遍歷PreOrder中的二叉樹

由於二叉樹是遞迴資料結構（為什麼？因為在刪除節點後，結構的其餘部分也是二叉樹，例如左右二叉樹，類似於連結串列，也是遞迴資料結構），自然使用遞迴演算法解決基於樹的問題是比較好的選擇。

PreOrder遍歷演算法的步驟

1. 訪問節點

2. 訪問左子樹

3. 訪問右子樹

通過列印節點的值，然後遞迴呼叫具有左子樹和右子樹的同一pre order（）方法，可以很容易地使用遞迴實現PreOrder遍歷演算法，如下程式所示：

<b>private</b> <b>void</b> preOrder(TreeNode node) {
<b>if</b> (node == <b>null</b>) {
<b>return</b>;
}
System.out.printf(<font>"%s "</font><font>, node.data);
preOrder(node.left);
preOrder(node.right);
}
</font>

你可以看到它只是幾行程式碼。這裡最重要的是基本情況，遞迴演算法從這裡開始展開。這裡node == null是我們的基本情況，因為你現在已經到達了葉節點，現在不能再深入了，是時候回溯到另一條路徑了。遞迴演算法也非常易讀的，您可以看到，首先列印節點值，然後訪問左子樹，最後是右子樹。建議閱讀Robert Sedgewick的Algorithms第4版，以瞭解更多關於Java的迴歸演算法。

在Java中不使用遞迴的二叉樹PreOrer遍歷

將遞迴演算法轉換為迭代演算法的一種簡單方法是使用堆疊資料結構。如果您還記得，遞迴隱式地使用一個堆疊，當您的演算法達到基本情況時，該堆疊將開始展開。您可以使用外部堆疊替換該隱式堆疊，並在不實際使用遞迴的情況下解決問題。這也更安全，因為現在你的程式碼不會丟擲StackOverFlowError，即使對於巨大的二叉搜尋樹也是如此，但它們通常不像遞迴樹一樣簡潔易讀。無論如何，這裡是在Java中不使用遞迴的PreOrer演算法。

<b>public</b> <b>void</b> preOrderWithoutRecursion() {
Stack<TreeNode> nodes = <b>new</b> Stack<>();
nodes.push(root);

<b>while</b> (!nodes.isEmpty()) {
TreeNode current = nodes.pop();
System.out.printf(<font>"%s "</font><font>, current.data);

<b>if</b> (current.right != <b>null</b>) {
nodes.push(current.right);
}
<b>if</b> (current.left != <b>null</b>) {
nodes.push(current.left);
}
}
}
</font>

老實說，這個程式碼很容易理解，但在演算法的中間有一個棘手的部分，即在左子樹之前必須推右子樹，這與遞迴演算法不同。我們首先推動棧中的根來開始遍歷，然後使用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遍歷。

<b>import</b> java.util.Stack;

<font><i>/*
 * 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
 */ \
 *25
 */ \\
 * 346
 * 
 * output: 1 2 3 4 5 6 
 */</i></font><font>
<b>public</b> <b>class</b> PreOrderTraversal {

<b>public</b> <b>static</b> <b>void</b> main(String[] args) throws Exception {

</font><font><i>// construct the binary tree given in question</i></font><font>
BinaryTree bt = <b>new</b> BinaryTree();
BinaryTree.TreeNode root = <b>new</b> BinaryTree.TreeNode(</font><font>"1"</font><font>);
bt.root = root;
bt.root.left = <b>new</b> BinaryTree.TreeNode(</font><font>"2"</font><font>);
bt.root.left.left = <b>new</b> BinaryTree.TreeNode(</font><font>"3"</font><font>);

bt.root.left.right = <b>new</b> BinaryTree.TreeNode(</font><font>"4"</font><font>);
bt.root.right = <b>new</b> BinaryTree.TreeNode(</font><font>"5"</font><font>);
bt.root.right.right = <b>new</b> BinaryTree.TreeNode(</font><font>"6"</font><font>);

</font><font><i>// printing nodes in recursive preOrder traversal algorithm</i></font><font>
bt.preOrder();

System.out.println();

</font><font><i>// traversing binary tree in PreOrder without using recursion</i></font><font>
bt.preOrderWithoutRecursion();

}

}

<b>class</b> BinaryTree {
<b>static</b> <b>class</b> TreeNode {
String data;
TreeNode left, right;

TreeNode(String value) {
<b>this</b>.data = value;
left = right = <b>null</b>;
}

<b>boolean</b> isLeaf() {
<b>return</b> left == <b>null</b> ? right == <b>null</b> : false;
}

}

</font><font><i>// root of binary tree</i></font><font>
TreeNode root;

</font><font><i>/**
* Java method to print tree nodes in PreOrder traversal
*/</i></font><font>
<b>public</b> <b>void</b> preOrder() {
preOrder(root);
}

</font><font><i>/**
* traverse the binary tree in PreOrder
* 
* @param node
*- starting node, root
*/</i></font><font>
<b>private</b> <b>void</b> preOrder(TreeNode node) {
<b>if</b> (node == <b>null</b>) {
<b>return</b>;
}
System.out.printf(</font><font>"%s "</font><font>, node.data);
preOrder(node.left);
preOrder(node.right);
}

</font><font><i>/**
* Java method to visit tree nodes in PreOrder traversal without recursion.
*/</i></font><font>
<b>public</b> <b>void</b> preOrderWithoutRecursion() {
Stack<TreeNode> nodes = <b>new</b> Stack<>();
nodes.push(root);

<b>while</b> (!nodes.isEmpty()) {
TreeNode current = nodes.pop();
System.out.printf(</font><font>"%s "</font><font>, current.data);

<b>if</b> (current.right != <b>null</b>) {
nodes.push(current.right);
}
<b>if</b> (current.left != <b>null</b>) {
nodes.push(current.left);
}
}
}

}

Output
1 2 3 4 5 6 
1 2 3 4 5 6 
</font>

這就是關於如何在Java中以PreOrder遍歷二叉樹的問題。我們已經瞭解瞭如何使用遞迴和迭代（例如使用堆疊資料結構）來實現PreOrder遍歷演算法。作為一名計算機工程師或程式設計師，您應該瞭解基本的樹遍歷演算法，例如先順序、順序和後順序遍歷。

無論如何，要記住在先排序遍歷中，節點值在訪問左、右子樹之前被打印出來。它也是一種深度優先遍歷演算法，遍歷順序為 node-left-right,，因此又稱為NLR演算法。

Java中二叉樹的PreOrder遍歷——遞迴與迭代例項

您可能也會喜歡…