我正在尝试在Julia中实现BST,但是在调用insert函数时遇到了问题。当我尝试创建新节点时,结构保持不变。
我的代码:
type Node
key::Int64
left
right
end
function insert(key::Int64, node)
if node == 0
node = Node(key, 0, 0)
elseif key < node.key
insert(key, node.left)
elseif key > node.key
insert(key, node.right)
end
end
root = Node(0,0,0)
insert(1,root)
insert(2,root)
我还尝试将零更改为零。我尝试的下一个版本是在Node中定义了数据类型,但是当我尝试不带任何值(类似于C Null)调用insert时,却给了我错误。
感谢您的回答。
最佳答案
该代码有很多问题。
一种是它不是类型稳定的,左右都可以包含任何东西。
另一个是在insert函数中设置局部变量节点不会影响任何更改。
在样式方面,修改其参数的函数通常带有!!作为名称中的最后一个字符,例如insert!,push! setindex!。
我认为以下应该起作用:
type BST
key::Int
left::Nullable{BST}
right::Nullable{BST}
end
BST(key::Int) = BST(key, Nullable{BST}(), Nullable{BST}())
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的推送!函数,并使用Nullable类型,以便它可以区分叶节点与需要继续搜索以查找在何处插入 key 的位置。这是一个递归定义,并且没有进行优化,因此使用循环而不是递归会更快。
关于julia - 如何在Julia中实现二叉搜索树?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36383517/