public class TreeTraversal {
public static void main(String args[]) {
Node rootNode = new Node("4");
rootNode.left = new Node("2");
rootNode.left.left = new Node("1");
rootNode.left.right = new Node("3");
rootNode.right = new Node("6");
rootNode.right.right = new Node("7");
rootNode.right.left = new Node("5");
// System.out.println(rootNode);
System.out.println("********pre order*********");
preorderTraversal(rootNode);
System.out.println("\n\n********in order*********");
inorderTraversal(rootNode);
System.out.println("\n\n********post order*********");
postorderTraversal(rootNode);
System.out.println("\n\n********* pre order without recursion******");
preOrderWithoutRecursion(rootNode);
System.out.println("\n\n********in order without recursion********");
inOrderWithoutRecursion(rootNode);
System.out.println("\n\n*******post without recursion****");
postOrderWithoutRecursion(rootNode);
}
public static void preorderTraversal(Node rootNode) {
if(null!=rootNode) {
System.out.print(rootNode.value);
preorderTraversal(rootNode.left);
preorderTraversal(rootNode.right);
}
}
public static void inorderTraversal(Node rootNode) {
if(null!=rootNode) {
inorderTraversal(rootNode.left);
System.out.print(rootNode.value);
inorderTraversal(rootNode.right);
}
}
public static void postorderTraversal(Node rootNode) {
if(null!=rootNode) {
postorderTraversal(rootNode.left);
postorderTraversal(rootNode.right);
System.out.print(rootNode.value);
}
}
public static void preOrderWithoutRecursion(Node root) {
Stack<Node> stNodes = new Stack<>();
Node current = root;
while(!stNodes.isEmpty() || current!=null) {
if(null!=current) {
stNodes.push(current);
System.out.print(current.value);
current = current.left;
}else {
Node node = stNodes.pop();
current = node.right;
}
}
}
public static void inOrderWithoutRecursion(Node root) {
Stack<Node> stNodes = new Stack<>();
Node current = root;
while(!stNodes.isEmpty() || current!=null) {
if(null!=current) {
stNodes.push(current);
current = current.left;
}else {
Node node = stNodes.pop();
System.out.print(node.value);
current = node.right;
}
}
}
public static void postOrderWithoutRecursion(Node root) {
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();
Node current = root;
stack1.push(root);
while(!stack1.isEmpty() ) {
Node node = stack1.pop();
stack2.push(node);
if(null!=node.left) {
stack1.push(node.left);
}if(null!=node.right) {
stack1.push(node.right);
}
}
while(!stack2.isEmpty()) {
System.out.print(stack2.pop().value);
}
}
}
class BinayTree{
static class Node{
String value;
Node left;
Node right;
Node(String val){
value = val;
left = right = null;
}
}
}
output:
********pre order*********
4213657
********in order*********
1234567
********post order*********
1325764
********* pre order without recursion******
4213657
********in order without recursion********
1234567
*******post without recursion****
1325764
public static void main(String args[]) {
Node rootNode = new Node("4");
rootNode.left = new Node("2");
rootNode.left.left = new Node("1");
rootNode.left.right = new Node("3");
rootNode.right = new Node("6");
rootNode.right.right = new Node("7");
rootNode.right.left = new Node("5");
// System.out.println(rootNode);
System.out.println("********pre order*********");
preorderTraversal(rootNode);
System.out.println("\n\n********in order*********");
inorderTraversal(rootNode);
System.out.println("\n\n********post order*********");
postorderTraversal(rootNode);
System.out.println("\n\n********* pre order without recursion******");
preOrderWithoutRecursion(rootNode);
System.out.println("\n\n********in order without recursion********");
inOrderWithoutRecursion(rootNode);
System.out.println("\n\n*******post without recursion****");
postOrderWithoutRecursion(rootNode);
}
public static void preorderTraversal(Node rootNode) {
if(null!=rootNode) {
System.out.print(rootNode.value);
preorderTraversal(rootNode.left);
preorderTraversal(rootNode.right);
}
}
public static void inorderTraversal(Node rootNode) {
if(null!=rootNode) {
inorderTraversal(rootNode.left);
System.out.print(rootNode.value);
inorderTraversal(rootNode.right);
}
}
public static void postorderTraversal(Node rootNode) {
if(null!=rootNode) {
postorderTraversal(rootNode.left);
postorderTraversal(rootNode.right);
System.out.print(rootNode.value);
}
}
public static void preOrderWithoutRecursion(Node root) {
Stack<Node> stNodes = new Stack<>();
Node current = root;
while(!stNodes.isEmpty() || current!=null) {
if(null!=current) {
stNodes.push(current);
System.out.print(current.value);
current = current.left;
}else {
Node node = stNodes.pop();
current = node.right;
}
}
}
public static void inOrderWithoutRecursion(Node root) {
Stack<Node> stNodes = new Stack<>();
Node current = root;
while(!stNodes.isEmpty() || current!=null) {
if(null!=current) {
stNodes.push(current);
current = current.left;
}else {
Node node = stNodes.pop();
System.out.print(node.value);
current = node.right;
}
}
}
public static void postOrderWithoutRecursion(Node root) {
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();
Node current = root;
stack1.push(root);
while(!stack1.isEmpty() ) {
Node node = stack1.pop();
stack2.push(node);
if(null!=node.left) {
stack1.push(node.left);
}if(null!=node.right) {
stack1.push(node.right);
}
}
while(!stack2.isEmpty()) {
System.out.print(stack2.pop().value);
}
}
}
class BinayTree{
static class Node{
String value;
Node left;
Node right;
Node(String val){
value = val;
left = right = null;
}
}
}
output:
********pre order*********
4213657
********in order*********
1234567
********post order*********
1325764
********* pre order without recursion******
4213657
********in order without recursion********
1234567
*******post without recursion****
1325764
No comments:
Post a Comment