如何创建/实现镜像二叉树的算法 [英] how to create/implement an algorithm that mirrors a binary tree

问题描述

我是Elixir的新手，正在尝试实现插入/添加功能以镜像现有的二叉树。欣赏所有想法。

I'm new to Elixir, and trying to implement an insert/add function to mirror an existing binary tree. Appreciate all ideas.

不知道从哪里开始。

推荐答案

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

I'm assuming you want to implement a binary tree in Elixir, and that you are also familiar with binary trees. For that, you would need to use a struct (which is just a map behind the scenes).

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

没有查找方法，这是练习留给您的。用法很简单。在这里，我们创建一个新的树节点，将其作为根：

There's no lookup method, which is left as an exercise to you. Usage is pretty simple. Here we create a new tree node which will be the root:

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

现在我们在树中插入5：

Now we insert 5 into the tree:

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
}

树的最终形状类似于以下内容：

With the final shape of the tree resembling the following:

   10
 /    \
5     12
     /
    11

镜像现在变得非常容易。以下是实现镜像功能的模块：

Mirroring now becomes pretty easy. Here's the module that implements the mirroring functionality:

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 ：

To mirror the node we have created earlier above, we simply call 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
}

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

Now the shape of mirrored resembles the following:

   10
 /    \
12     5
  \
  11

这篇关于如何创建/实现镜像二叉树的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！