從Java中的Post-order遍歷構造二進制搜索樹

Question

我正在實施代碼以構建BST(binary search tree)，其中從this algorithm開始。我不回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; 
}