如何 create/implement 一个镜像二叉树的算法

Question

我是 Elixir 的新手，正在尝试实现一个 insert/add 函数来镜像现有的二叉树。欣赏所有想法。

不知道从哪里开始。

Answer 1

我假设您想在 Elixir 中实现二叉树，并且您也熟悉二叉树。为此，您需要使用结构（它只是幕后的地图）。

defmodule TreeNode do
  defstruct value: nil, left: nil, right: nil 

  def new(value), do: %TreeNode{value: value}

  def insert(root = %TreeNode{value: rootValue}, value) when value < rootValue do
    %{root | left: insert(root.left, value)}
  end

  def insert(root = %TreeNode{value: rootValue}, value) when value >= rootValue do
    %{root | right: insert(root.right, value)}
  end

  def insert(nil, value) do
    %TreeNode{value: value}
  end
end

没有查找方法，留给大家练习。用法非常简单。这里我们创建一个新的树节点，它将成为根节点：

iex(1)> node = TreeNode.new(10)
%TreeNode{left: nil, right: nil, value: 10}

现在我们向树中插入 5:

iex(2)> node = TreeNode.insert(node, 5)
%TreeNode{
  left: %TreeNode{left: nil, right: nil, value: 5},
  right: nil,
  value: 10
}

和 12：

iex(3)> node = TreeNode.insert(node, 12)
%TreeNode{
  left: %TreeNode{left: nil, right: nil, value: 5},
  right: %TreeNode{left: nil, right: nil, value: 12},
  value: 10
}

和 11：

iex(4)> node = TreeNode.insert(node, 11)
%TreeNode{
  left: %TreeNode{left: nil, right: nil, value: 5},
  right: %TreeNode{
    left: %TreeNode{left: nil, right: nil, value: 11},
    right: nil,
    value: 12
  },
  value: 10
}

树的最终形状如下所示：

镜像现在变得非常简单。这是实现镜像功能的模块：

defmodule TreeMirror do
  def mirror(nil), do: nil

  def mirror(node) do
    %TreeNode{value: node.value, left: mirror(node.right), right: mirror(node.left)}
  end
end

要镜像我们之前创建的节点，我们只需调用 TreeMirror.mirror:

iex(5)> mirrored = TreeMirror.mirror node
%TreeNode{
  left: %TreeNode{
    left: nil,
    right: %TreeNode{left: nil, right: nil, value: 11},
    value: 12
  },
  right: %TreeNode{left: nil, right: nil, value: 5},
  value: 10
}

现在 mirrored 的形状类似于以下内容：

如何 create/implement 一个镜像二叉树的算法

how to create/implement an algorithm that mirrors a binary tree

binary

tree

add

elixir