数据结构
网络
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 次浏览
广告