реализовать реконструкцию двоичного дерева поиска из массива preOrder в Java?
Я следовал эта идея и это Код C ++ восстановить двоичное дерево поиска из массива PreOrder в Java. Я не изобретаю алгоритм заново, а пытаюсь реализовать псевдокод.
Мне нужна помощь здесь. Я не получаю правильный вывод. Вывод, который я получаю, находится ниже кода.
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);
}
}
}
Другие решения
Использование явного стека подобно чрезмерному усложнению кода, поэтому лучше использовать рекурсию, которую довольно легко понять. Просто рецессивно рассчитать 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;
}
}