如何创建/实现镜像二叉树的算法 [英] 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屋!