資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Java 程式實現中序遍歷二叉樹
在本文中，我們將探討如何使用兩種不同的方法來執行二叉樹的中序遍歷：遞迴方法和非遞迴（迭代）方法。中序遍歷透過首先訪問左子樹，然後訪問節點本身，最後訪問右子樹來處理每個節點。這對於某些型別的樹結構（例如 二叉搜尋樹）特別有用，因為中序遍歷將按排序順序列印值。
問題陳述
編寫一個 Java 程式來執行中序樹遍歷。下面是演示：
輸入
Run the program
輸出
The In-Order traversal of the tree_object is: 5->12->6->1->9->
使用遞迴方法
遞迴中序遍歷的步驟如下：
- 首先，我們定義一個節點類來表示二叉樹中的每個節點。
- 在 樹類中，我們實現了遞迴的inOrder() 方法，該方法呼叫自身以首先遍歷左子樹，處理當前節點，然後遍歷右子樹。
- 遞迴的基本情況檢查當前節點是否為null，如果是，則方法返回。
- 我們建立一個樹物件，透過為左子樹和右子樹分配值來定義其結構，然後呼叫inOrder() 方法以按正確的順序遍歷並列印節點。
示例
這裡，我們使用了遞迴方法進行中序遍歷：
class Node {
int item;
Node left_node, right_node;
public Node(int key) {
item = key;
left_node = right_node = null;
}
}
public class Tree {
Node root;
Tree() {
root = null;
}
void inOrder(Node node) {
if (node == null)
return;
inOrder(node.left_node);
System.out.print(node.item + "->");
inOrder(node.right_node);
}
public static void main(String[] args) {
Tree tree_object = new Tree();
System.out.println("A tree_object object is defined: ");
tree_object.root = new Node(1);
tree_object.root.left_node = new Node(12);
tree_object.root.right_node = new Node(9);
tree_object.root.left_node.left_node = new Node(5);
tree_object.root.left_node.right_node = new Node(6);
System.out.println("The In-Order traversal of the tree_object is: ");
tree_object.inOrder(tree_object.root);
}
}
輸出
A tree_object object is defined: The In-Order traversal of the tree_object is: 5->12->6->1->9->
使用非遞迴方法
以下是遞迴方法中序遍歷的步驟：
- 從 java.util 包中匯入 Stack 類。
- 與遞迴方法類似，我們首先定義一個節點類來表示樹節點。
- 在樹類中，我們定義了一個inorder() 方法，該方法使用棧在沒有遞迴的情況下執行遍歷。
- 該演算法首先初始化一個棧並將指標設定為根節點。
- 然後，我們迭代，直到有節點需要處理或棧不為空，首先將所有左節點壓入棧中。
- 到達最左節點後，節點將一個接一個地從棧中彈出，處理當前節點並移動到右子樹。
- 我們建立一個樹物件，定義樹結構，並呼叫inorder() 方法以按所需的順序列印節點。
示例
這裡，我們使用非遞迴方法進行中序遍歷：
import java.util.Stack;
class Node {
int data;
Node left_node, right_node;
public Node(int item) {
data = item;
left_node = right_node = null;
}
}
public class tree {
Node root;
void inorder() {
if (root == null)
return;
Stack<Node> temp_stack = new Stack<Node>();
Node current_node = root;
while (current_node != null || temp_stack.size() > 0) {
while (current_node != null) {
temp_stack.push(current_node);
current_node = current_node.left_node;
}
current_node = temp_stack.pop();
System.out.print(current_node.data + " ");
current_node = current_node.right_node;
}
}
public static void main(String args[]) {
tree tree = new tree();
System.out.println("A tree_object object is defined: ");
tree.root = new Node(1);
tree.root.left_node = new Node(2);
tree.root.right_node = new Node(3);
tree.root.left_node.left_node = new Node(4);
tree.root.left_node.right_node = new Node(5);
System.out.println("The In-Order traversal of the tree_object is: ");
tree.inorder();
}
}
輸出
A tree_object object is defined: The In-Order traversal of the tree_object is: 4 2 5 1 3
更新於： 2024年9月20日
788 次瀏覽
廣告