In: Computer Science
Traversal tree program
Traversing a tree means visiting each and every node of the tree. To add all the values in the tree or to find the largest one we can prefer this.
There are three types of traversal depending on the order in which we do this.
1. Inorder traversal
1. First, visit all the nodes in the left subtree
2. Visit the root node
3. Visit all the nodes in the right subtree
2. Preorder traversal
1. First, Visit the root node
2. Visit all the nodes in the left subtree
3. Visit all the nodes in the right subtree
3. Postorder traversal
1.First, Visit all the nodes in the left subtree
2. Visit all the nodes in the right subtree
3. Visit the root node
Traversal tree program:
Node.java
package com;
public class Node
{
int key;
Node left, right;
public Node(int n)
{
key = n;
left = right = null;
}
}
TraversalTree.java
package com;
public class TraversalTree
{
Node root;
TraversalTree()
{
root = null;
}
void DisplayInorder(Node node)
{
if (node == null)
return;
DisplayInorder(node.left);
System.out.print(node.key + " ");
DisplayInorder(node.right);
}
void DisplayPostorder(Node node)
{
if (node == null)
return;
DisplayPostorder(node.left);
DisplayPostorder(node.right);
System.out.print(node.key + " ");
}
void DisplayPreorder(Node node)
{
if (node == null)
return;
System.out.print(node.key + " ");
DisplayPreorder(node.left);
DisplayPreorder(node.right);
}
void DisplayInorder() { DisplayInorder(root); }
void DisplayPreorder() { DisplayPreorder(root); }
void DisplayPostorder() { DisplayPostorder(root); }
// main method
public static void main(String[] args)
{
TraversalTree tree = new TraversalTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("\nInorder traversal is : ");
tree.DisplayInorder();
System.out.println("\nPreorder traversal is: ");
tree.DisplayPreorder();
System.out.println("\nPostorder traversal is: ");
tree.DisplayPostorder();
}
}
Output:
Inorder traversal is :
4 2 5 1 3
Preorder traversal is:
1 2 4 5 3
Postorder traversal is:
4 5 2 3 1