julia - 如何在 Julia 中定义二叉搜索树的类型？

Question

我尝试使用以下内容在 Julia 中定义整数二叉搜索树的类型:

mutable  struct BST
    key::Int
    left::Union{BST, Nothing}
    right::Union{BST, Nothing}
end

现在我想定义构造函数和基本的 Push!使用这种简单方法的方法:

BST(key::Int) = BST(key, Nothing, Nothing)
BST() = BST(0)

function Base.push!(node::BST, key)
    if key < node.key
        if node.left.isnull
            node.left = BST(key)
        else
            push!(node.left.value, key)
        end
    elseif key > node.key
        if node.right.isnull
            node.right = BST(key)
        else
            push!(node.right.value, key)
        end
    end
end

root = BST()
push!(root, 1)
push!(root, 2)

当然它不适用于 Julia 1.0!我当然没有正确理解 union 的用法。它们只是抽象类型吗？定义此数据结构的正确方法是什么？

Julia 文档对这个主题的解释很差。

上一个问题涉及现已弃用的 Nullable 类型: How to implement a Binary Search Tree in Julia?

Answer 1

代码如下(假设您不想在 BST 中存储重复值，但我想这就是您想要的):

BST(key::Int) = BST(key, nothing, nothing)
BST() = BST(0)

function Base.push!(node::BST, key)
    if key < node.key
        if node.left === nothing
            node.left = BST(key)
        else
            push!(node.left, key)
        end
    elseif key > node.key
        if node.right === nothing
            node.right = BST(key)
        else
            push!(node.right, key)
        end
    end
end

实际上你的定义几乎没问题，只是有一些语法问题:

• nothing 是一个值，而 Nothing 是一种类型，因此您必须编写 BST(key, Nothing, Nothing) 而不是 BST(键，无，无)
• 使用这种比较来测试某些东西是否没有node.left === Nothing(使用===，因为编译器可以更轻松地优化此代码)
• 您必须 push! 到 BST 对象，而不是存储在其中的值，因此 push!(node.right, key)不是 push!(node.right.value, key)