자바에서 순회 순회에서 이진 검색 트리를 구성하십시오.

Question

다음에 post-order traversal array에서 BST(binary search tree)을 구성하는 코드를 구현하고 있습니다. 나는 binary Search Tree을 돌려받지 못했다. 나는 무의미한 것을 얻고있다. 여기 내 코드는

public class BinaryTreemethods { 
    public static void main(String[] args) { 
      int[] preOrder = { 5, 3, 1, 4, 8, 6, 9 }; 
     int[] inOrder = { 1, 3, 4, 5, 6, 8, 9 }; 
     int[] postOrder = {1,4,3,8,6,9,5}; 

      static int postIndex=postOrder.length-1; 
      Node postordertree= buildBinarytreefromPostOrder(postOrder, 0, postOrder.length-1); 
      System.out.println("pre order traversal of node from postorder reconstructed tree "); 
      printPreOrder(postordertree); 

     } 
     private static void printPreOrder(Node tree) { 
     if (tree != null) { 
      System.out.print(" " + tree.data); 
      printPreOrder(tree.left); 
      printPreOrder(tree.right); 
     } 

    } 
     //this just reconstructs BT from post-order traversal elements 
    public static Node buildBinarytreefromPostOrder(int[] post, int start, int end){ 
     if (postIndex<start || start > end){ 
      return null; 
     } 

     Node root = new Node(post[postIndex]); 
     postIndex--; 
     if (end == start){ 
      //System.out.println("called"); 
      return root; 
     } 

     int i = 0; 
     for (i=end;i>=start;i--){ 
      if (post[i]<root.data) 
       break; 
     } 

     // Use the index of element found in postorder to divide postorder array 
     // in two parts. Left subtree and right subtree 
      root.right=buildBinarytreefromPostOrder(post,i+1, postIndex); 
     root.left=buildBinarytreefromPostOrder(post,start,i); 
      //root.left=buildBinarytreefromPostOrder(post,start,i); 
     //root.right=buildBinarytreefromPostOrder(post,i+1, postIndex); 

     return root; 
    } 
} 

pre-order traversal is 5 9 6 8 3 4에 인쇄 할 때 출력이 올바르지 않습니다.

내가 잘못 될 수있는 아이디어가 있습니까?

편집 : root.right and root.left (이전에 주석 처리 된 행) 순서를 바꾼 후 left tree이 올바르게 빌드되었지만 올바른 트리가 아닌 것입니다. 내가 얻는 결과는 5 3 1 4 9 6 8

Answer 1

입니다. 각 하위 트리의 루트는 전체 구조에 대해 전체적으로 postIndex입니다. 하위 배열의 마지막 요소 (end)를 가져와야합니다.

당신이 [코드를 디버깅] 봤어 그것은 오히려이

public static Node buildBinarytreefromPostOrder(int[] post, int start, int end) 
{ 
    if (end < start) 
     return null; 

    Node root = new Node(post[end]); 

    if (end == start) 
     return root; 

    int i; 
    for (i = end; i >= start; i--) 
     if (post[i] < root.data) 
      break; 

    root.left = buildBinarytreefromPostOrder(post, start, i); 
    root.right = buildBinarytreefromPostOrder(post, i + 1, end - 1); 

    return root; 
}