package tree; public class Node{ private Node left; private Node right; private int data; public Node(int data){ this.data=data; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } public int getData() { return data; } public void setData(int data) { this.data = data; } }
package tree; /* 50 /\ 40 60 /\ /\ 30 45 55 70 /\ 20 35 */ public class ConstructBSTFromInorderAndPostOrderTraversal { public static void main(String[] args) { new ConstructBSTFromInorderAndPostOrderTraversal(); } public ConstructBSTFromInorderAndPostOrderTraversal() { int inorder[] = {20, 30, 35, 40, 45, 50, 55, 60, 70}; int postorder[] = {20, 35, 30, 45, 40, 55, 70, 60, 50}; int inStart = 0; int inEnd = inorder.length-1; int postStart =0; int postEnd = postorder.length-1; Node n = buildTree(inorder, inStart, inEnd, postorder, postStart, postEnd); System.out.println(n); } public Node buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd){ if(inStart > inEnd || postStart > postEnd) return null; int rootValue = postorder[postEnd]; Node root = new Node(rootValue); int k=0; for(int i = inStart; i <= inEnd; i++){ if(inorder[i]==rootValue){ k = i; break; } } int len = k - inStart; root.setLeft(buildTree(inorder, inStart, k-1, postorder, postStart, postStart+len-1)); root.setRight(buildTree(inorder, k+1, inEnd, postorder, postStart+len, postEnd-1)); return root; } }
No comments:
Post a Comment