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树遍历