Как бы я написал метод, чтобы превратить двоичное дерево поиска (BST) в отсортированный список значений в BST? - PullRequest
Новая
       21

Как бы я написал метод, чтобы превратить двоичное дерево поиска (BST) в отсортированный список значений в BST?

0 голосов
/ 31 марта 2020

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

class BinarySearchTree[A](comparator: (A, A) => Boolean) {

  var root: BinaryTreeNode[A] = null

  def search(a: A): BinaryTreeNode[A] = {
    searchHelper(a, this.root)
  }

  def searchHelper(a: A, node: BinaryTreeNode[A]): BinaryTreeNode[A] = {
    if(node == null){
      null
    }else if(comparator(a, node.value)){
      searchHelper(a, node.left)
    }else if(comparator(node.value, a)){
      searchHelper(a, node.right)
    }else{
      node
    }
  }


  def BSTtoList: List[A] = {
    var sortedList = List()
    if (root.left != null) {
      sortedList :+ searchHelper(root.value, root.left).value

    }
    else if (root.right != null){
      sortedList :+ searchHelper(root.value, root.right).value
    }
    sortedList
  }
}

1 Ответ

2 голосов
/ 31 марта 2020

Давайте сначала подумаем о том, как работает BST. В любом данном узле, скажем, со значением x, все узлы в левом поддереве будут иметь значения x. Таким образом, чтобы вернуть отсортированный список поддерева, укорененного в узле x, вам просто нужно вернуть [отсортированный список левого поддерева] + [x] + [отсортированный список правого поддерева], поэтому вам просто нужно вызвать BSTtoList рекурсивно для левые и правые поддеревья, а затем верните список, описанный выше. Оттуда вам просто нужно обработать базовый случай возврата пустого списка на узле NULL.

Вышеприведенный алгоритм - время O (N ^ 2), и есть лучшее решение, использующее хвостовую рекурсию, которая выполняется в O (N) время, псевдокод, для которого: 

def BSTtoList(root, accumulator):
    if root == NULL:
        return accumulator
    else:
        return BSTtoList(root.left_child, [root.value] + BSTtoList(root.right_child, accumulator)

Где BSTtoList первоначально вызывается с пустым списком в качестве аккумулятора. Это второе решение работает аналогично первому, но оптимизировано за счет минимизации слияния массивов (эта версия работает лучше всего, если в используемом языке есть вставка O (1) в начало списка; реализация немного отличается, если язык позволяет O (1) вставка в спину).

...