Tree traversal Java

Java tree traversal is defined as an algorithm that is implemented in Java programming language, which comprises of the tree as a data structure and incorporates the fundamental of visiting all nodes of the tree through the implementation of the algorithm. Traversal in computer science data structure terminology denotes that all nodes in the data structure need to be visited in order to complete the bigger task at hand. The components of a tree are root and child nodes, some of which end at that particular node and is named as leaves and the others creating more sub-trees. In this article, we will go through the implementation of tree traversal in Java and look at the different methods through which we can achieve the same.

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

Syntax

Declaration of class in 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

Access the right of the node in Java:

<variable name>.right

How to perform Tree traversal in Java?

Before we start discussing the different ways of traversing a tree in Java, we first need to know how a tree is structured because this is one of the essential components in order to build the tree as a class in Java. The tree has nodes, and hence we define a node class. This class will have fields as the data that is representing the data of the node, a left pointer that points to the left of the node, and another pointer that points to the right of the node. All these fields constitute the Node class. Below is a schematic of how a tree looks like:

Once we have defined the tree class that constitutes the nodes and the pointer, it is now time to look at the 3 types of traversals that are implemented in Java and each of them having its own signature of traversal:

1 In-order Traversal

The way this traversal is defined is we visit the elements of the left subtree, followed by the node of the subtree, and then finally traverse the right subtree. The pseudocode is as follows:

• Recursively call the function by passing the left node till we reach node as null.
• Display the data
• Recursively call the function by passing the right node till we reach node as null.

The path of traversal of the In-order algorithm will be: Node 1.1→Node 1→Node 1.2→Root→ Node 2.

2. Pre-order Traversal

The way this traversal is defined is to visit the elements of the root node, traverse the left subtree, and then finally traverse the right subtree. The pseudocode is as follows:

• Traverse the root node first.
• Recursively call the function by passing the left node till we reach node as null.
• Recursively call the function by passing the right node till we reach node as null.

The path of traversal of the pre-order algorithm will be: Root→Node 1→Node 1.1→Node 1.2→ Node 2.

3. Post-order Traversal

The way this traversal is defined is we visit the elements of the left subtree, followed by the right subtree, and then finally traverse the node of the subtree till we reach the base node. The pseudocode is as follows:

• Recursively call the function by passing the left node till we reach node as null.
• Recursively call the function by passing the right node till we reach node as null.
• Display the data

The path of traversal of the post-order algorithm will be: Node 1.1→Node 1.2→ Node 1→Node 2→ Root.

Examples of Tree traversal Java

Given below are the examples of Tree traversal Java:

Example #1

In order traversal using recursion

Syntax

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);
}
}

Output:

Example #2

Pre-order traversal using recursion

Syntax

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);
}
}

Output:

Example #3

Postorder traversal through recursion

Syntax

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);
}
}

Output:

Conclusion

This article looked at all the various ways of implementing tree traversal in Java, along with examples from the real world. Readers are encouraged to look at the traversal by adding more nodes into the code and seeing the traversal results!

The above is the detailed content of Tree traversal Java. For more information, please follow other related articles on the PHP Chinese website!