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。もう 1 つの問題は、に初期化した後に更新@rootしないことです。への割り当てでは、 には影響しません。BSTniladd_recursiver@root

于 2013-10-19T03:44:19.400 に答える