Сохранение в порядке посещения двоичного дерева в массиве

Question

Вопрос заключается в следующем: существует ли алгоритм, который, учитывая двоичное дерево T и массив, позволяет хранить в массиве результат соответствующего посещения дерева по порядку?

Псевдокод "нормального" посещения по порядку:

inOrder(x){ // x is a node of a binary tree
   if(x != NIL){ // the node is not null
      inOrder(x.left)
      print(x.key)
      inOrder(x.right)
   }
}

// Function calling inOrder
printInOrder(T){ // T is a binary tree
   inOrder(T.root) // T.root is the root of the tree
}

Пример: для следующего дерева

     5 
   /   \
  3     8
 / \   / 
2   7 1   

приведенный выше алгоритм должен вывести 2 3 7 5 1 8.

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

Answer 1

Запись в массив (вместо печати) означает, что вам нужно отслеживать, по какому индексу записывать в массив. Если вам нужно сделать это без какого-либо изменяемого состояния, кроме самого массива, вам нужно передать текущий индекс в качестве аргумента и вернуть новый текущий индекс.

Код ниже записан в stati c форма одиночного присваивания , поэтому даже локальные переменные не видоизменяются. Если этого не требуется, код можно немного упростить. Я предполагаю, что длина массива известна; если это нужно вычислить, это отдельная проблема.

inOrder(x, arr, i) {
    if(x == NIL) {
        return i
    } else {
        i2 = inOrder(x.left, arr, i)
        arr[i2] = x.key
        i3 = inOrder(x.right, arr, i2 + 1)
        return i3
    }
}

getArrayInOrder(T, n) {
    arr = new array of length n
    inOrder(T.root, arr, 0)
    return arr
}

Answer 2

Если ваш язык / сценарий использования позволяет помещать целые числа в массив, вы можете сохранить индекс в массиве. Я иду назад, потому что тогда все проще:

inOrder(x, arr){
   if(x != NIL){
      inOrder(x.right)
      arr[--arr[0]] = x.key
      inOrder(x.left)
   }
}

saveInOrder(T, n){
   arr = new int[n]
   arr[0] = n
   inOrder(T.root, arr)
   return arr
}

Answer 3

Сначала о массивах: чтобы заполнить массив, вам нужно заранее знать длину массива. Если вам не нужно указывать длину для создания экземпляра массива (в зависимости от языка, который вы используете), тогда это не совсем массив. Это динамическая структура данных c, размер которой автоматически увеличивается в результате языковой реализации.

Теперь я предполагаю, что вы заранее не знаете размер дерева. Если вы знаете размер, вы можете создать экземпляр массива указанного размера. Предполагая, что вы не знаете размер массива, вам нужно go с динамической c структурой данных, такой как ArrayList в Java.

Так на каждом print(x.key) в вашем коде просто добавьте x.key в список (например, list.add(x.key)). После завершения обхода вы можете превратить ваш List в array.

Вы также можете использовать итерационную версию обхода.

Одно простое решение для рекурсии Подход заключается в использовании одного элемента массива для отслеживания индекса, например:

void inOrder(x, int[] idx, int[] arr):
    if x != NIL:
       inOrder(x.left, idx, arr)
       arr[idx[0]++] = x.key
       inOrder(x.right, idx, arr)

, хотя я уверен, что могут быть и другие способы, которые могут стать громоздкими (возможно). В любом случае я предпочитаю итеративную версию.