Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
public class Main {
/* Static variable which acts as the pointer for the postOrder list */
static int preIndex = 5;
public static void main(String[] args) {
/* InOrder Array */
char[] inOrder = { 'D', 'B', 'E', 'A', 'F', 'C' };
/* PostOrder Array */
char[] postOrder = { 'D', 'E', 'B', 'F', 'C', 'A' };
/* Call the BinaryTreeGeneratot recursive function! */
Node root = BinaryTreeGenerator(inOrder, postOrder, 0,
inOrder.length - 1);
/* Prove the tree exists */
printInorder(root);
}
/* Print inorder for proof */
public static void printInorder(Node root) {
if (root != null) {
printInorder(root.left);
System.out.println(root.data);
printInorder(root.right);
}
}
/*
* This is the function which actually does all the work. Lets go through it
* one at a time.
*/
public static Node BinaryTreeGenerator(char[] inOrder, char[] postOrder,
int inStrt, int inEnd) {
/*
* If the start of the array is bigger than the end of the array then
* obviously we need to end the recursion
*/
if (inStrt > inEnd) {
return null;
}
/*
* Here we make the new node data space and allocate the value of a
* preIndex variable and then we post decrement it so as to point to the
* next element in the postOrder array
*/
Node node = new Node(postOrder[preIndex--]);
/*
* If the start is equal to the end, its clear that we do need to end
* the recursive loop and return the current node
*/
if (inStrt == inEnd) {
return node;
}
/*
* We call the search function to return to us the element where the
* data of the node is placed in the inOrder array
*/
int inIndex = search(inOrder, inStrt, inEnd, node.data);
/*
* Call the recursive function to return the next set of nodes and place
* them right to left
*/
node.right = BinaryTreeGenerator(inOrder, postOrder, inIndex + 1, inEnd);
node.left = BinaryTreeGenerator(inOrder, postOrder, inStrt, inIndex - 1);
return node;
}
/*
* This function goes through the inorder array passed and returns the value
* where the value of the data hits the value of the element of the array
* which is passed in the parameter list, the values are checked only till
* the inEnd variable because we want to go from start to the end
*/
public static int search(char[] inOrder, int inStrt, int inEnd, char data) {
for (int i = inStrt; i <= inEnd; i++) {
if (inOrder[i] == data) {
return i;
}
}
return 0;
}
}
/*
* This is the node which we are going to consider as our ADT (Abstract Data
* Type) It has a Data Space, A Right Node Pointer, A Left Node Pointer It also
* has a constructor which sets the data, the left and right pointers as null
*/
class Node {
char data;
Node right;
Node left;
Node(char data) {
this.data = data;
this.left = null;
this.right = null;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.