Как реализовать метод, который возвращает отсортированный по порядку массив в двоичном дереве поиска Java?

Question

Вот что я попробовал:

public int[] sortedArray() {
    int[] array = new int[size()];
    int index = 0;
    traverseInorder(root, array, index);
    return array;
}

private void traverseInorder(Node n, int[] array, int index) {
    if (n != null) {
        traverseInorder(n.left, array, index);
        array[index++] = n.value;
        traverseInorder(n.right, array, index);
    }
}

Но вывод не верный.

Если я создаю дерево с этим вводом:

{1,5,8,10,12,15,20,22,25,36,30,40,28,38,48,45,50}

Вывод, который я получаю с помощью sortedArray, будет таким:

[1, 5, 8, 10, 12, 15, 20, 22, 25, 36, 40, 48, 50, 0, 0, 0, 0]

Что я сделал не так?Я понимаю, что он пропускает все левые поддеревья с правой стороны от корня, но я просто не понимаю, почему ...

Answer 1

Измените функцию "traverseInorder" на приведенную ниже.Надеюсь, эта рекурсия сработает.

 private int traverseInorder(Node n, int[] array, int index)
 {
 if(n.left != null)
 index =  traverseInorder(n.left, array, index);

 array[index++] = n.value;

 if(n.right != null)
 index =  traverseInorder(n.right, array, index);

   return index;
}

Answer 2

Вы перезаписываете все левые элементы поддеревьев, записанные в массив.

Предполагая, что вы добавили узлы в дерево в указанном порядке, вы получите следующее (крайне несбалансированное) дерево:

   1
    \
     5
      \
       8
        \
         10
          \
           12
            \
             15
               \
                20
                 \
                  22
                   \
                    25
                     \
                     36
                    /  \
                   30   40
                  /    /  \
                 28   38   48
                          /  \
                         45   50

Вы можете видеть, что 4 элемента, отсутствующие в выходных данных по порядку (28, 30, 38 и 45), принадлежат левым поддеревьям.

Причина такого поведениязаключается в том, что после traverseInorder(n.left, array, index); запись левого поддерева в массив и возврат всех изменений, внесенных в index, являются локальными, поэтому array[index++] = n.value; и traverseInorder(n.right, array, index) перезаписывают значения левого поддерева, ранее записанные вмассив.

Чтобы исправить это, ваш рекурсивный метод должен вернуть обновленный индекс:

private int traverseInorder(Node n, int[] array, int index) {
    if (n != null) {
        index = traverseInorder(n.left, array, index);
        array[index++] = n.value;
        index = traverseInorder(n.right, array, index);
    }
    return index;
}