2016-04-03 49 views
5

我想在Julia中實現BST,但是當我調用插入函數時遇到了問題。當我嘗試創建新節點時,結構保持不變。如何在Julia中實現BST?

我的代碼:

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)時,它給了我錯誤。

感謝您的回答。

+0

不知道我明白這個問題 - 你期望'insert'函數做什麼?運行你的代碼返回'Node(1,0,0)'爲倒數第二行,'Node(2,0,0)'爲最後一行,這似乎是正確的? –

+0

我不確定BST是什麼,但是閱讀你的代碼就是你想要寫的一個函數,它需要一個'node'(帶有'key','left'和'right'的字段)和一個然後執行以下兩種操作之一:(i)如果未定義節點,則在其「key」字段中使用「key」參數創建一個新的「Node」實例,爲「left」和「或者(ii)如果'node'存在,用'key'參數更新函數的'left'或'right'字段? –

+0

BST代表二進制搜索樹。功能插入結構的新節點。零不代表任何東西。 – pavelf

回答

14

該代碼有一些問題。 一個是它不是類型穩定的,左右可以包含任何東西。 另一個是設置插入函數內部的局部變量節點不會影響任何改變。 一個風格問題,修改它們的參數的函數通常有一個!作爲名字中的最後一個字符,比如insert !,推! 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) 

這個版本重載朱莉婭推!函數,並使用Nullable類型,以便它可以區分葉節點和它需要繼續搜索以找到插入密鑰的位置的位置。這是一個遞歸定義,並沒有進行優化,使用循環而不是遞歸進行循環會更快。