Ruby的這種用法對二叉搜索樹是錯的嗎？

Question

我試圖爲Ruby中的二叉搜索樹編寫快速實現，這是我在學習新編程語言時通常編寫的數據結構。

當我在計算機上運行它時，出現堆棧太深的錯誤。我想知道這是我的代碼問題還是我運行它的問題？

class Node 
    attr_accessor :data, :left, :right 
    def initialize(d) 
    @data = d 
    @left = Node.new(nil) 
    @right = Node.new(nil) 
    end 
end 

class BST 
    attr_accessor :root 
    def initialize 
    @root = nil 
    end 

    def add_recursive(r, d) 
    if r == nil 
     r = Node.new(d) 
    else 
     add_recursive(r.right, d) if d > r.data 
     add_recursive(r.left, d) if d < r.data 
    end 
    end 

    def add(darg) 
    add_recursive(@root, darg) 
    end 

    def pr(r) 
    if (r.left != nil) 
     pr(r.left) 
    end 
    print "#{r.data}" 
    if (r.right != nil) 
     pr(r.right) 
    end 
    end 
end 

bb = BST.new 
bb.add(100) 
bb.add(0) 
bb.add(-100) 
bb.pr(bb.root)`` 

我想知道我究竟在這個實現做錯了，因爲我確實跑了幾個簡單的測試，我在訪問數據的變量是給我的問題使用。感謝您的幫助

Answer 1

您在這裏遇到了一個以上的問題，但您的第一個Node.new(nil)調用Node#initialize發生了無限遞歸。另一個問題是，在將其初始化爲nil後，您從不更新@rootBST。 add_recursive您對r的分配對@root沒有影響。