Aim: - To learn about different Tree Traversal techniques
Tree traversal or traversing a tree examines all the nodes of the tree. There are two aspects to traversing a tree. One is that we need to follow references (pointers) from parent to child. The second is that we need to “visit” the node for some computation, e.g. getting or setting a field of an element referenced by that node. There are several different ways in which we can traverse a tree. They differ in the order in which the nodes are visited
Depth-first Traversals
In these traversals, a node and all its descendents are visited before the next sibling is visited. There are three ways to do depth-first-traversal of a tree, depending on whether you visit a node before its descendents or after its descendents.
There are three Depth-first Traversals
Preorder :- Performs the following operations recursively at each node
1. Visit the root.
2. Traverse the left subtree.
3. Traverse the right subtree.
Inorder :- Performs the following operations recursively at each node
1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree
Postorder :- Performs the following operations recursively at each node
1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root.
Breadth-first Traversal
Trees can also be traversed in level-order, where we visit every node on a level before going to a lower level.
Java Program to implement Tree traversal
import java.io.*;
class BinTree{
private Node root;
private static class Node{
Node left;
Node right;
int data;
public Node(int cdata){
left=null;
right=null;
data=cdata;
}
}
public BinTree() throws Exception {
root=null;
}
public void insert(int data) {
root=insert(root,data);
}
public Node insert(Node node,int data) {
if(node==null)
node=new Node(data);
else if(data<=node.data)
node.left=insert(node.left, data);
else
node.right=insert(node.right, data);
return(node);
}
public void Disp(int ch) {
if(root==null)
System.out.println(" No Elements in the Tree ") ;
else
{
switch(ch)
{
case 1: System.out.println("\n\n\n Preorder Traversal ");
preorder(root);
break;
case 2: System.out.println("\n\n\n Inorder Traversal ");
inorder(root);
break;
case 3: System.out.println("\n\n\n Postorder Traversal ");
postorder(root);
break;
case 4: System.out.println(" Height of the tree = "+height(root));
break;
case 0: break;
default:
System.out.println(" Invalid choice ") ;
}
}
}
public int height(Node node) {
if(node==null)
return(0);
return max( height(node.left)+1, height(node.right)+1);
}
int max(int a,int b) {
return(a>b?a:b);
}
public void preorder(Node node) {
if(node!=null)
{
System.out.print(" "+node.data);
preorder(node.left);
preorder(node.right);
}
}
public void inorder(Node node) {
if(node!=null)
{
inorder(node.left);
System.out.print(" "+node.data);
inorder(node.right);
}
}
public void postorder(Node node) {
if(node!=null)
{
postorder(node.left);
postorder(node.right);
System.out.print(" "+node.data);
}
}
}
public class Traversal {
public static void main(String agrs[]) throws Exception {
BinTree B= new BinTree();
int n, item;
DataInputStream in= new DataInputStream(System.in);
System.out.print("Enter number of items to be inserted ");
n=Integer.parseInt(in.readLine());
System.out.println("Enter any "+n+" integers ");
while(n>0)
{
item=Integer.parseInt(in.readLine());
B.insert(item);
n--;
}
int choice;
do
{
System.out.println("\n Binary Tree Traversal operation ");
System.out.println(" Enter the choice \n\t\t 1.preorder\n\t\t 2.inoreder\n\t\t 3.postorder\n\t\t 4.height of tree \n\t\t 0.Exit\n");
choice=Integer.parseInt(in.readLine());
B.Disp(choice);
}while(choice!=0);
}
}
OUTPUT:
Enter number of items to be inserted 8
Enter any 8 integers
4 3 5 6 7 2 1 8
Binary Tree Traversal operation
Enter the choice
1.preorder
2.inoreder
3.postorder
4.height of tree
0.Exit
1
Preorder Traversal 4 3 2 1 5 6 7 8
Binary Tree Traversal operation
Enter the choice
1.preorder
2.inoreder
3.postorder
4.height of tree
0.Exit
2
Inorder Traversal 1 2 3 4 5 6 7 8
Binary Tree Traversal operation
Enter the choice
1.preorder
2.inoreder
3.postorder
4.height of tree
0.Exit
3
Postorder Traversal 1 2 3 8 7 6 5 4
Binary Tree Traversal operation
Enter the choice
1.preorder
2.inoreder
3.postorder
4.height of tree
0.Exit
4
Height of the tree = 5
Binary Tree Traversal operation
Enter the choice
1.preorder
2.inoreder
3.postorder
4.height of tree
0.Exit
0
No comments:
Post a Comment