从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; 
}