Java树遍历简介

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
}
Defining a method in Java:
returnType < method name >() {
// Body of the method that constitutes the steps that will fulfill the assigned task
}
Declaring the node in 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中将树构建为类的基本组件之一。树有节点，因此我们定义了一个节点类。此类将具有字段作为表示节点数据的数据、指向节点左侧的左指针和指向节点右侧的另一个指针。所有这些字段构成节点类。下面是树的外观示意图：

一旦定义了构成节点和指针的树类，现在就可以查看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的示例：

示例#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);
}
}

输出：

示例#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);
}
}

输出：

示例#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);
}
}

输出：