Here is the code for binary tree traversal
1. Normal Traversal
2. Zigzag Traversal
3. LevelByLevel Traversal.
The following Binary Tree is created and traversal is done on that
import java.util.Stack;
/**
*
* @author Soumitra Chatterjee(onlinesoumitra@gmail.com)
*/
public class Tree {
static Stack currentLevel = new Stack();
static Stack nextLevel = new Stack();
static Stack temp = new Stack();
static boolean leftToRight = true;
public static void main(String args[]) {
Node rootnode = new Node(25);
System.out.println(
"Building tree with rootvalue " + rootnode.data);
System.out.println("=================================");
insert(rootnode, 11);
insert(rootnode, 15);
insert(rootnode, 9);
insert(rootnode, 10);
insert(rootnode, 6);
insert(rootnode, 16);
insert(rootnode, 23);
insert(rootnode, 79);
insert(rootnode, 66);
insert(rootnode, 81);
System.out.println("Traversing tree in order");
System.out.println("=================================");
printTree(rootnode);
System.out.println("Traversing tree in Zigzag order");
System.out.println("=================================");
printTreeZigZag(rootnode);
System.out.println("Traversing tree in Level by level");
System.out.println("=================================");
printLevelbyLevel(rootnode);
}
public static void insert(Node n, int value) {
if (n == null) {
return;
}
if (n.data > value) {
if (n.left != null) {
insert(n.left, value);
} else {
n.left = new Node(value);
System.out.println(" Inserted " + value + " to left of node " + n.data);
}
} else if (n.data < value) {
if (n.right != null) {
insert(n.right, value);
} else {
n.right = new Node(value);
System.out.println(" Inserted " + value + " to right of node " + n.data);
}
///System.out.println("value = " + value);
}
}
public static void printLevelbyLevel(Node n) {
if (n == null) {
return;
}
System.out.println("data = " + n.data);
currentLevel.push(n);
while (!currentLevel.isEmpty()) {
Node x = (Node) currentLevel.pop();
if (x != null) {
// System.out.println("data = " + x.data);
if (x.right != null) {
nextLevel.push(x.right);
}
if (x.left != null) {
nextLevel.push(x.left);
}
if (x.left != null) {
System.out.println("data = " + x.left.data);
}
if (x.right != null) {
System.out.println("data = " + x.right.data);
}
}
if (currentLevel.isEmpty()) {
temp = currentLevel;
currentLevel = nextLevel;
nextLevel = temp;
}
}
}
public static void printTreeZigZag(Node n) {
if (n == null) {
return;
}
currentLevel.push(n);
while (!currentLevel.isEmpty()) {
n = (Node) currentLevel.peek();
Node x = (Node) currentLevel.pop();
// System.out.println("data:" + x.data);
if (n != null) {
System.out.println("data = " + x.data);
if (leftToRight) {
if (x.left != null) {
nextLevel.push(x.left);
}
if (x.right != null) {
nextLevel.push(x.right);
}
} else {
if (x.right != null) {
nextLevel.push(x.right);
}
if (x.left != null) {
nextLevel.push(x.left);
}
//righttoleft = true;
}
}
if (currentLevel.isEmpty()) {
leftToRight = !leftToRight;
//swap stacks
temp = currentLevel;
currentLevel = nextLevel;
nextLevel = temp;
// System.out.println("x = " + (Node)(nextLevel.pop());
}
}
}
public static void printTree(Node n) {
if (n == null) {
return;
}
System.out.println("root = " + n.data);
if (n.left != null) {
System.out.println("left child = " + n.left.data);
printTree(n.left);
}
if (n.right != null) {
System.out.println("right child = " + n.right.data);
printTree(n.right);
}
}
}
class Node {
int data;
Node left;
Node right;
public Node(int val) {
this.data = val;
}
}
10xxxxxxxxxxxxx
ReplyDeleteexcellent
ReplyDeletethanx
ReplyDelete(Y)
ReplyDelete