时间戳

首页 > 解决方案 > 展平二叉树以列出（有序）

binary - 展平二叉树以列出（有序）

问题描述

我正在尝试实现一种算法，该算法将树作为输入并以正确的顺序返回所有值的列表（从上到下，每行从左到右），但我遇到了麻烦。实现无序的简单方法是减少每个节点附加到累积列表的整个列表。

这是我为减少一棵树（用 elixir 编写）而编写的代码，其中每个节点都有一个左右分支，可以是另一个节点或 nil：

    def reduce(nil, op, init), do: init
    def reduce({:node, n, left, right}, op, init) 做
      减少（右，操作，减少（左，操作，操作。（n，初始化）））
    结尾

像这样调用来获取树（但顺序错误）：

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

有小费吗？

标签： binary

解决方案

作为一般的经验法则，您可以只调用&Enum.reverse/1结果列表。由于在 erlang 中构建列表的方式的性质，您会发现许多算法在后台执行此操作。我认为甚至&Enum.map/2使用它。

除此之外，还有一种更简单的方法可以使用函数头编写功能。我相信您正在寻找树的中序遍历，其中每个访问的节点都添加到列表中，但是您可以轻松地对其进行修改以包括后序和前序遍历。这是一个带有您正在寻找的 map/reduce 功能的模块。

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)，这是一种完全不同的算法。基本上，您必须将节点推入队列而不是堆栈，这是前序/后序/中序遍历算法所做的。

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/break-down-breadth-first-search-cebe696709d9

推荐阅读