Распечатка бинарного дерева в Java - PullRequest
Новая
       7

Распечатка бинарного дерева в Java

1 голос
/ 11 апреля 2020

Этот вопрос касается отслеживания глубины рекурсии в рекурсивной функции.

У меня есть массив int inputArr[], хранящий входные значения. Я создал рекурсивную функцию, которая переставляет значения из int inputArr[] в бинарную древовидную структуру в соответствии со следующими правилами:

  • каждый новый левый узел формируется путем взятия среднего значения левой стороны
  • соответственно для правого узла
  • если число элементов в новом подрешетке четное (следовательно, среднего значения нет), мы берем правое из двух средних значений

Об этом уже позаботился мой foo(from: to: ).

Мы распечатываем значения таким образом, чтобы перед каждым узлом было n пробелов и значение da sh (n это глубина дерева).

Я борюсь с печатью. Сохранение глубины с последующим выделением n пробелов на основе элементов int depthArr[] просто дает неправильный вывод.

Правильные примеры: 

{1, 2, 3, 4} -> {3, 2, 1, 4}

- 3
 - 2
  - 1
 - 4

{1, 2, 3, 4, 5} -> {3, 2, 1, 5, 4}:

- 3
 - 2
  - 1
 - 5
  - 4

{1, 2, 3, 4, 5, 6, 7, 8} -> {5, 3, 2, 1, 4, 7, 6, 8}

- 5
 - 3
  - 2
   - 1
  - 4
 - 7
  - 6
  - 8

{1, 2, 3, 4, 5, 6} -> {4, 2, 1, 3, 6, 5}

- 4
 - 2
  - 1
  - 3
 - 6
  - 5

Моя функция (просто сфокусируйтесь на массиве глубины) все остальное работает): 

public void foo(int from, int to) {
    outputArr[index] = arr[getIndex(from, to)]; // Just saving the values in correct order
    depthArr[index++] = depth; // Trying out to keep track of current depth

    int prev = to;
    to = getIndex(from, to);

    if (from - to == 0) {
        depth--; // I think that I'm incorrectly decreasing the depth as the recursion goes back
        return;
    }

    depth++;
    foo(from, to - 1);

    if (prev - from != 1)
        foo(to + 1, prev);
}

public int getIndex(int from, int to) { // Get the middle value from, to
    int numOfElements = to - from + 1;
    return from + (numOfElements / 2);
}

Где getIndex(from: , to: ) просто даст мне индекс следующего среднего значения от некоторого индекса до некоторого индекса (входной массив - publi c). Например: getIndex(0, 2) из {1, 2, 3, 4, 5} равно 2 и т. Д.

Есть ли способ распечатать дерево в правильном порядке без необходимости сохранения глубины? Или есть какой-то простой и надежный способ, который я упустил?

Мой вывод: 

{1, 2, 3, 4, 5}

- 3
 - 2
  - 1
 - 5
  - 4 // Correct



{1, 2, 3, 4, 5, 6, 7, 8}

- 5
 - 3
  - 2
   - 1
  - 4
 - 7
  - 6
 - 8 // Should have one more space

{1, 2, 3, 4, 5, 6, 7}

- 4
 - 2
  - 1
 - 3 // Should have one more space
- 6 // Should have one more space
 - 5
- 7 // Should have one more space

1 Ответ

0 голосов
/ 11 апреля 2020

Решено.

int depth была переменной * stati c, которая вызывала проблему при возврате из рекурсии, поскольку к тому времени, когда левые узлы были закончены и глубина был уже вычтен, depthArr[] отслеживал вычитаемые глубины на том же этаже. Решение состоит в том, чтобы отслеживать глубины внутри с помощью аргумента: 

    public void foo(int from, int to, int depth) {
    outputArr[index] = arr[getIndex(from, to)];
    depthArr[index++] = depth;

    int prev = to;
    to = getIndex(from, to);

    if (from - to == 0) {
        return;
    }

    foo(from, to - 1, depth + 1); // <-- here

    if (prev - from != 1)
        foo(to + 1, prev, depth + 1); // <-- here
}

Теперь нам нужно вызвать функцию как `foo (0, inputArr.length, 0), и все будет работать.

...