Java樹遍歷-java教程-PHP中文網

Java樹遍歷被定義為一種用Java程式語言實現的演算法，它以樹作為資料結構，並透過演算法的實作來存取樹的所有節點的基本原理。電腦科學資料結構術語中的遍歷表示需要存取資料結構中的所有節點才能完成手邊的更大任務。樹的元件是根節點和子節點，其中一些節點以該特定節點結束並被命名為葉子，其他節點會建立更多子樹。在本文中，我們將介紹 Java 中樹遍歷的實現，並了解可以實現相同目的的不同方法。

開始您的免費軟體開發課程

網頁開發、程式語言、軟體測試及其他

文法

Java中類別的聲明：

class <class name> {
// List the fields (variables) for the class
// Define the methods of the class to perform the specified operations
}

登入後複製

在 Java 中定義方法：

returnType <method name>() {
// Body of the method that constitutes the steps that will fulfill the assigned task
}

登入後複製

用Java宣告節點：

Node<{ Data Type }> <variable name> = new Node<{ Data Type }>(" <Value>");
Access the left of the node in Java:
<variable name>.left

登入後複製

Java中訪問節點右側：

<variable name>.right

登入後複製

如何用Java進行樹的遍歷？

在我們開始討論 Java 中遍歷樹的不同方法之前，我們首先需要知道樹是如何建構的，因為這是在 Java 中將樹建構成類別的基本元件之一。樹有節點，因此我們定義一個節點類別。該類別將具有作為表示節點資料的資料的欄位、指向節點左側的左指標和指向節點右側的另一個指標。所有這些字段構成了 Node 類別。下面是樹的示意圖：

Java樹遍歷

一旦我們定義了構成節點和指標的樹類，現在就可以看看 Java 中實現的 3 種類型的遍歷，每種類型都有自己的遍歷簽名：

1 中序遍歷

這種遍歷的定義方式是先訪問左子樹的元素，然後訪問子樹的節點，最後遍歷右子樹。偽代碼如下：

透過傳遞左節點遞歸呼叫函數，直到到達 null 節點。
顯示數據
透過傳遞正確的節點遞歸來呼叫函數，直到到達 null 節點。

中序演算法的遍歷路徑為：節點 1.1→節點 1→節點 1.2→根→節點 2。

2.預購穿越

這種遍歷的定義方式是存取根節點的元素，遍歷左子樹，最後遍歷右子樹。偽代碼如下：

先遍歷根節點。
透過傳遞左節點遞歸呼叫函數，直到到達 null 節點。
透過傳遞正確的節點遞歸來呼叫函數，直到到達 null 節點。

前序演算法的遍歷路徑為：根→節點1→節點1.1→節點1.2→節點2。

3.後序遍歷

這種遍歷的定義方式是先訪問左子樹的元素，然後訪問右子樹，最後遍歷子樹的節點，直到到達基節點。偽代碼如下：

透過傳遞左節點遞歸呼叫函數，直到到達 null 節點。
透過傳遞正確的節點遞歸來呼叫函數，直到到達 null 節點。
顯示數據

後序演算法的遍歷路徑為：節點1.1→節點1.2→節點1→節點2→根。

Java 樹遍歷範例

以下是Java樹遍歷的範例：

Java樹遍歷

範例#1

使用遞迴進行有序遍歷

文法

class NodeClass {
int value;
NodeClass left, right;
public NodeClass(int key) {
value = key;
left = right = null;
}
}
class Tree {
NodeClass base;
Tree() {
base = null;
}
void inOrderFunc(NodeClass node) {
if (node == null)
return;
inOrderFunc(node.left);
System.out.print(node.value + "->");
inOrderFunc(node.right);
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.base = new NodeClass(27);
tree.base.left = new NodeClass(9);
tree.base.right = new NodeClass(19);
tree.base.left.left = new NodeClass(91);
tree.base.left.right = new NodeClass(92);
System.out.println("In Order traversal");
tree.inOrderFunc(tree.base);
}
}

登入後複製

輸出：

Java樹遍歷

範例#2

使用遞迴進行預序遍歷

文法

class NodeClass {
int item;
NodeClass left, right;
public NodeClass(int key) {
item = key;
left = right = null;
}
}
class Tree {
NodeClass base;
Tree() {
base = null;
}
void preorderFunc(NodeClass node) {
if (node == null)
return;
//First the node:
System.out.print(node.item + "->");
//Recursively look at the left side of the tree
preorderFunc(node.left);
//Recursively look at the right side of the tree
preorderFunc(node.right);
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.base = new NodeClass(27);
tree.base.left = new NodeClass(9);
tree.base.right = new NodeClass(19);
tree.base.left.left = new NodeClass(91);
tree.base.left.right = new NodeClass(92);
// preorderFunc tree traversal
System.out.println("Preorder traversal: ");
tree.preorderFunc(tree.base);
}
}

登入後複製

輸出：

Java樹遍歷

範例 #3

透過遞迴進行後序遍歷

文法

class NodeClass {
int item;
NodeClass left, right;
public NodeClass(int key) {
item = key;
left = right = null;
}
}
class Tree {
NodeClass base;
Tree() {
base = null;
}
void postorderFunc(NodeClass node) {
if (node == null)
return;
postorderFunc(node.left);
postorderFunc(node.right);
System.out.print(node.item + "->");
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.base = new NodeClass(27);
tree.base.left = new NodeClass(9);
tree.base.right = new NodeClass(19);
tree.base.left.left = new NodeClass(91);
tree.base.left.right = new NodeClass(92);
System.out.println("Postorder traversal: ");
tree.postorderFunc(tree.base);
}
}

登入後複製

輸出：

Java樹遍歷