Considering the tree to be as in the below diagram
/**
* @author Sachidananda
*Technically a tree consists of Node.The Node definition has been provided below.
*/
public class Node {
int nodeValue;
public Node left;
public Node right;
public Node(int val) {
nodeValue = val;
this.left = null;
this.right = null;
}
public boolean hasLeft() {
return left != null;
}
public boolean hasRight() {
return right != null;
}
public String toString() {
return toStringHelper(" ");
}
private String toStringHelper(String indent) {
String ret = "";
if (hasRight()){
ret += right.toStringHelper(indent + " ");
}
ret += indent + nodeValue + "\n";
if (hasLeft()){
ret += left.toStringHelper(indent + " ");
}
return ret;
}
}
/**
* @author sachidananda
* Class has the functionality to construct a BinaryTree from the inorder,preorder and postorder values.
*/
public class BinTreeContsructor {
/*considering that we have arrays of integer values for inorder, preorder and postorder traversal and that does not have duplicates*/
/**
* @param int []preorder
* @param int []inorder
* @return Node
*/
public static Node buildTreePreIn(int[] preorder, int[] inorder){
int preorderLength=preorder.length;
int inorderLength=inorder.length;
return buildTreePI(preorder,0,preorderLength-1,inorder,0,inorderLength-1);
}
/**
* @param int []inorder
* @param int []postorder
* @return Node
*/
public static Node buildTreeInPost(int[] inorder, int[] postorder){
int inorderLength=inorder.length;
int postorderLength=postorder.length;
return buildTreeIP(inorder, 0, inorderLength-1, postorder, 0, postorderLength-1);
}
/**
*
* @param int []pre
* @param int preStart
* @param int preEnd
* @param int []in
* @param int inStart
* @param int inEnd
* @return Node
*/
public static Node buildTreePI(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd){
if(inStart > inEnd){
return null;
}
int rootVal = pre[preStart];
int rootIndex = 0;
for(int i = inStart; i <= inEnd; i++){
if(in[i] == rootVal){
rootIndex = i;
break;
}
}
int len = rootIndex - inStart;
Node root = new Node(rootVal);
root.left = buildTreePI(pre, preStart+1, preStart+len, in, inStart, rootIndex-1);
root.right = buildTreePI(pre, preStart+len+1, preEnd, in, rootIndex+1, inEnd);
return root;
}
/**
*
* @param int []in
* @param int inStart
* @param int inEnd
* @param int []post
* @param int postStart
* @param int postEnd
* @return Node
*/
public static Node buildTreeIP(int[] in, int inStart, int inEnd, int[] post, int postStart, int postEnd){
if(inStart > inEnd){
return null;
}
int rootVal = post[postEnd];
int rootIndex = 0;
for(int i = inStart; i <= inEnd; i++){
if(in[i] == rootVal){
rootIndex = i;
break;
}
}
int len = rootIndex - inStart;
Node root = new Node(rootVal);
root.left = buildTreeIP(in, inStart, rootIndex-1, post, postStart, postStart+len-1);
root.right = buildTreeIP(in, rootIndex+1, inEnd, post, postStart+len, postEnd-1);
return root;
}
public static void main(String[] args) {
int []postOrder={10,32,25,78,40};
int []preOrder ={40,25,10,32,78};
int []inOrder= {10,25,32,40,78};
Node tree=buildTreePreIn(preOrder,inOrder);
System.out.println("Building Tree from preOrder and inOrder");
System.out.println("----------------------------------------");
System.out.println(tree);
Node tree1=buildTreeInPost(inOrder,postOrder);
System.out.println("Building Tree from inOrder and postOrder");
System.out.println("----------------------------------------");
System.out.println(tree1);
}
}
output
=============
Building Tree from preOrder and inOrder
----------------------------------------
78
40
32
25
10
Building Tree from inOrder and postOrder
----------------------------------------
78
40
32
25
10
No comments:
Post a Comment