0

我已经按照这个想法和这个C++ 代码从 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
4

2 回答 2

2

看起来递归打印搞砸了。这里printPreOrder应该调用自己遍历左右子树而不是调用printInOrder遍历。

public static void printPreOrder(Node root) {

            if (root!=null){
                System.out.print(" " + root.data);
                printPreOrder(root.left); 
                printPreOrder(root.right);
            }
        }
    }
于 2013-11-12T22:37:25.443 回答
1

使用显式堆栈就像使代码过于复杂，所以宁愿使用很容易掌握的递归。只需隐式计算min,max和指示数组中当前指针的索引。

TreeNode createTree(int[] a, Index i, int min, int max) {
    if (i.index >= a.length) {
        return null;
    }
    if (a[i.index] > min && a[i.index] < max) {
        int current = a[i.index];
        TreeNode t = new TreeNode(a[i.index]);
        i.index = i.index + 1;
        t.left = createTree(a, i, min, current);
        t.right = createTree(a, i, current, max);
        return t;
    }
   return null;
}

其中Index类如下：

class Index {

    int index;

    Index(int k) {
        index = k;
    }
}
于 2013-11-12T22:42:19.450 回答