我遵循了this idea和此C++ code来从Java中的PreOrder数组重构二进制搜索树。我不是在重新发明算法，而是尝试实现伪代码。
我在这里需要帮助。我没有得到正确的输出。我得到的输出在代码下方。
public class BinaryTreeMethods {
public static void main(String[] args) {
int[] arr = {7,5,3,6,9,8,10};
Node newone = CreateFromPreOrder(arr,arr.length);
printInorder(newone);
System.out.println();
printPreOrder(newone);
public static Node CreateFromPreOrder(int[] arr, int length) {
if(length==0)
return null;
Node root = new Node(arr[0]);
Stack<Node> s = new Stack<Node>();
s.push(root);
for(int i=1; i<length; i++)
{
Node tmp = new Node(arr[i]);
Node next = s.peek();
if(tmp.data < next.data)
{
next.left = tmp;
}
else
{
Node popped = null;
while(!s.isEmpty() && tmp.data > next.data)
{
popped= s.peek();
s.pop();
}
popped.right = tmp;
}
s.push(tmp);
}
return root;
}
public static void printInorder(Node root) {
if (root!=null){
printInorder(root.left);
System.out.print(" " + root.data);
printInorder(root.right);
}
}
class Node {
Node left;
Node right;
int data;
public Node(int c){
this(c, null, null);
}
public Node(int c,Node left, Node right) {
this.data = c;
this.left=left;
this.right=right;
}
}
public static void printInorder(Node root) {
if (root!=null){
printInorder(root.left);
System.out.print(" " + root.data);
printInorder(root.right);
}
}
public static void printPreOrder(Node root) {
if (root!=null){
System.out.print(" " + root.data);
printInorder(root.left);
printInorder(root.right);
}
}
}
我没有得到预期的输出：
3 5 7 6 8 9 10
7 3 5 6 8 9 10
最佳答案
看起来递归打印搞砸了。与调用printPreOrder进行遍历相比，此处printInOrder应当调用自身遍历左右子树。
public static void printPreOrder(Node root) {
if (root!=null){
System.out.print(" " + root.data);
printPreOrder(root.left);
printPreOrder(root.right);
}
}
}