如何在Julia中实现二叉搜索树? [英] How to implement a Binary Search Tree in Julia?
问题描述
我正在尝试在Julia中实现BST,但是在调用insert函数时遇到了问题.当我尝试创建新节点时,结构保持不变.
I am trying to implement BST in Julia, but I encountered problem when I call insert function. When I try to create new node, the structure stays unchanged.
我的代码:
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时,却给了我错误.
I also tried to change zero to nothing. Next version which I tried is with defined datatypes in Node, but when I try to call insert with nothing value(similar to C Null) it gave me error.
感谢答案.
推荐答案
该代码存在许多问题. 一种是它不是类型稳定的,左右都可以包含任何东西. 另一个是在insert函数中设置局部变量节点不会影响任何更改. 在样式方面,修改其参数的函数通常带有!!作为名称中的最后一个字符,例如insert!,push! setindex!.
The code has a number of issues. One is that it is not type stable, left and right could contain anything. The other is that setting the local variable node inside the insert function will not affect change anything. A stylistic issue, functions that modify their arguments generally have a ! as the last character in the name, such as insert!, push! setindex!.
我认为以下方法应该有效:
I think the following should work:
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类型,以便它可以区分叶节点与需要继续搜索以找到插入键的位置.这是一个递归定义,并且没有进行优化,因此使用循环而不是递归会更快.
This version overloads the Julia push! function, and uses the Nullable type so that it can distinguish between a leaf node and where it needs to continue searching to find where to insert the key. This is a recursive definition, and is not optimized, it would be much faster to do it with loops instead of recursive.
这篇关于如何在Julia中实现二叉搜索树?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!