0

我尝试在 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)``

我想知道我在这个实现中做错了什么，因为我确实运行了一些简单的测试，并且我在访问数据变量时的使用给我带来了问题。谢谢你的帮助

4

1 回答 1

1

您在这里遇到的问题不止一个，但是您的无限递归发生在您第一次Node.new(nil)调用Node#initialize. 另一个问题是您@root在BST将其初始化为nil. 在add_recursive你的分配对r没有影响@root。

于 2013-10-19T03:44:19.400 回答