Конвертировать дерево в массив preOrder (рекурсивно)

Question

Я пытаюсь преобразовать дерево в его массив предзаказа, например, если дерево выглядит так:

1
/ \
2 3 ________
тогда его массив preOrder должен быть | 1 | 2 | 3 |
- - - - - - - -

Вот некоторые входные данные дерева:

//  2 3 4 5 6 7 8 -1 -1 -1 -1 -1 -1 -1 -1
//  10 9 4 -1 -1 5 8 -1 6 -1 -1 3 -1 -1 -1
//  1 2 9 3 4 -1 10 5 -1 -1 5 -1 -1 -1 -1 -1 6 -1 7 -1 8 -1 -1
//  1 2 6 3 7 -1 -1 4 -1 -1 8 5 -1 -1 9 -1 -1 -1 10 -1 -1
//  1 2 3 -1 -1 -1 -1

Код в моем Main.java:

public class Main {
    public static void main(String[] args) throws QueueEmptyException {
        Scanner in = new Scanner(System.in);

        BinaryTreeNode<Integer> root = BinaryTreeNode.takeInput_LEVEL_WISE(in);        // tree input taken
        BinaryTreeNode.print_Binary_Tree_LEVEL_WISE(root);

        // create its preOrder array
        int pre[] = BinaryTreeNode.preOrder_Array(root);
        for (int val : pre) {
            System.out.print(val + " ");
        }

        // create its postOrder array
    }
}

Вот мой Tree Node:

public class BinaryTreeNode<T> {
    public T data;
    public BinaryTreeNode<T> left;
    public BinaryTreeNode<T> right;

    BinaryTreeNode(T data) {
        this.data = data;
        left = null;
        right = null;
    }
}

Метод ввода ввода: (Нет проблем в этом)

public static BinaryTreeNode<Integer> takeInput_LEVEL_WISE(Scanner in) {
        Queue<BinaryTreeNode<Integer>> q = new LinkedList<>();
        System.out.println("enter root ");
        int data = in.nextInt();
        if (data == -1)                // no root is formed
            return null;
        BinaryTreeNode<Integer> root = new BinaryTreeNode<>(data);
        q.add(root);

        int left, right;
        while (!q.isEmpty()) {
            BinaryTreeNode<Integer> currentRoot = q.poll();
            System.out.println("enter left of " + currentRoot.data + " :  ");
            left = in.nextInt();

            if (left == -1) {
                currentRoot.left = null;
            } else {
                BinaryTreeNode<Integer> leftChild = new BinaryTreeNode<>(left);
                currentRoot.left = leftChild;
                q.add(leftChild);
            }


            System.out.println("enter right of " + currentRoot.data + " :  ");
            right = in.nextInt();
            if (right == -1) {
                currentRoot.right = null;
            } else {
                BinaryTreeNode<Integer> rightChild = new BinaryTreeNode<>(right);
                currentRoot.right = rightChild;
                q.add(rightChild);
            }
        }
        return root;
    }

Код для функции печати: (нет проблем в этом тоже)

public static void print_Binary_Tree_LEVEL_WISE(BinaryTreeNode<Integer> root) {
        Queue<BinaryTreeNode<Integer>> q = new LinkedList<>();
        q.add(root);

        String print = "";
        while (q.size() != 0) {        // until not empty
            BinaryTreeNode<Integer> currentRoot = q.poll();
            print = currentRoot.data + ":";

            // adding the right and left
            if (currentRoot.left != null) {
                q.add(currentRoot.left);
                print += "L:" + currentRoot.left.data + ",";
            } else {
                print += "L:" + -1 + ",";
            }
            if (currentRoot.right != null) {
                q.add(currentRoot.right);
                print += "R:" + currentRoot.right.data;
            } else {
                print += "R:" + -1;
            }

            System.out.println(print);
        }
    }

---

Вот код для массива PreOrder: (Столкнувшись с проблемой в этом)

    public static int[] preOrder_Array(BinaryTreeNode<Integer> root) {
        if (root == null)
            return new int[0];        // array of 0 size

        int n = noOfNodesIN_Tree(root);
        int pre[] = new int[n];

        preOrder_Array_Helper(pre, root, 0);
        return pre;
    }

    private static void preOrder_Array_Helper(int[] pre, BinaryTreeNode<Integer> root, int index) {
        if (root == null)
            return;        //-> base case

        pre[index] = root.data;
//      index++;
        if (index == pre.length) {
            return;
        } else {        // call for recursion
            preOrder_Array_Helper(pre, root.left, index + 1);
            preOrder_Array_Helper(pre, root.right, index + 1);
        }
    }

Я понимаю проблему, это связано с индексами в рекурсии (значения продолжают переопределяться в том же месте / индексе), но я понятия не имею, как решить эту проблему, как мне сделать приращение индексов.

Это может быть легко сделано с помощью arrayList, но я хочу сделать это с массивами.

Answer 1

Вы можете вернуть последний обновленный индекс как результат метода и использовать его в рекурсивном вызове:

private static int preOrder_Array_Helper(int[] pre, BinaryTreeNode<Integer> root, int index) {
    if (root == null)
        return index;        //return the same as get

    pre[index] = root.data;
    index++; 
    if (index == pre.length) {
        return index;  //return new value after add
    } else {  
        index = preOrder_Array_Helper(pre, root.left, index);  //get last after left branch visit
        return preOrder_Array_Helper(pre, root.right, index); //use new index in right branch
    }
}

или вы можете использовать List<Integer> чтобы избежать всех этих проблем с управлением индексами:

public static List<Integer> preOrder_Array(BinaryTreeNode<Integer> root) {
    if (root == null)
        return new ArrayList<>();        // array of 0 size

    List<Integer> pre = new ArrayList<>();

    preOrder_Array_Helper(pre, root);
    return pre;
}

private static void preOrder_Array_Helper(List<Integer> pre, BinaryTreeNode<Integer> root) {
    if (root == null)
        return;

    pre.add(root.data);
    preOrder_Array_Helper(pre, root.left);
    preOrder_Array_Helper(pre, root.right);

}