Свести бинарное дерево к списку (упорядочено) - PullRequest
Новая
       10

Свести бинарное дерево к списку (упорядочено)

1 голос
/ 24 марта 2019

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

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


    def reduce(nil, op, init), do: init
    def reduce({:node, n, left, right}, op, init) do
      reduce(right, op, reduce(left, op, op.(n, init)))
    end

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


    result = reduce(tree, fn (node, acc) -> [acc|node] end, [])

Любые подсказки?

1 Ответ

0 голосов
/ 29 марта 2019

Как правило, вы можете просто вызвать &Enum.reverse/1 в результирующем списке.Многие алгоритмы, которые вы найдете, делают это под капотом из-за характера построения списков в erlang.Я думаю, что даже &Enum.map/2 использует его.

Кроме этого, есть гораздо более простой способ написать свою функциональность с помощью функциональных головок.Я полагаю, что вы ищете обход дерева по порядку, в котором каждый посещенный узел добавляется в список, но вы можете легко изменить его, включив также обход по порядку и порядку.Вот модуль с функциями отображения / сокращения, которые вы ищете. 

defmodule Tree do
  # This just uses the reduce functions defined below to create a map.
  def map_inorder(root) do
    root
    |> reduce_inorder([], fn val, acc ->
      [val | acc]
    end)
    |> Enum.reverse()
  end

  # This is the core functionality of the function for an inorder traversal
  # It processes the left subtree then calls the reducer on the root node
  # and then processes the right subtree.
  def reduce_inorder({:node, val, left, right}, acc, fun) do
    left_subtree = reduce_inorder(left, acc, fun)
    visit_root = fun.(val, left_subtree)
    reduce_inorder(right, visit_root, fun)
  end

  # Nil means that you've reached a leaf. There's nothing else to process
  def reduce_inorder(nil, acc, _fun) do
    acc
  end

  # Node does not match the spec you have for the record. Return an error
  def reduce_inorder(_other, _, _) do
    :malformed_node
  end
end

Алгоритмы обхода двоичного дерева очень просты для понимания.Вот пост, который хорошо их объясняет.

https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

Ура!

РЕДАКТИРОВАТЬ

Я понял, что вы говоритео ширине первого поиска (BFS), который является совершенно другим алгоритмом.По сути, вы должны помещать узлы в очередь, а не в стек, как это делают алгоритмы обхода preorder / postorder / inorder.

BFS обеспечивает обработку всех узлов в порядке слева направо на одной и той же глубинедерево.Как правило, вы начинаете с корневого узла как единственного узла в очереди.Вы обрабатываете этот узел и затем помещаете его левого и правого потомков в очередь в указанном порядке, а затем повторяете новую очередь.К счастью, я вспомнил, что в erlang есть модуль :queue, который делает это намного проще.Вы можете найти код ниже: 

defmodule Tree do
  def map_tree(root) do
    root
    |> reduce_tree([], fn val, acc ->
      [val | acc]
    end)
    |> Enum.reverse()
  end

  def reduce_tree(root, acc, reducer) do
    :queue.new()
    |> queue_in(root)
    |> process_queue(acc, reducer)
  end

  def process_queue(queue, acc, reducer) do
    case queue_out(queue) do
      {{:value, {:node, val, left, right}}, popped} ->
        # Process the head of the queue which is the next item in the traversal
        new_acc = reducer.(val, acc)

        # Push in the left then right so that they are processed in that order
        # and so that they are processsed behind earlier nodes that have been
        # found
        popped
        |> queue_in(left)
        |> queue_in(right)
        |> process_queue(new_acc, reducer)

      _other ->
        # Your queue is empty. Return the reduction
        acc
    end
  end

  # These are convenience methods. If the value being pushed in is nil then
  # ignore it so that it is not processed
  def queue_in(queue, nil) do
    queue
  end

  def queue_in(queue, val) do
    :queue.in(val, queue)
  end

  def queue_out(queue) do
    :queue.out(queue)
  end
end

Самое замечательное в этом подходе состоит в том, что он имеет хвостовую рекурсию.

Надеюсь, это поможет.Вот отличная статья о BFS:

https://medium.com/basecs/breaking-down-breadth-first-search-cebe696709d9

...