ruby二进制搜索树插入方法堆栈级别太深

ovfsdjhp  于 2021-09-29  发布在  Java
关注(0)|答案(1)|浏览(276)

我试图为二叉搜索树编写一个递归插入方法,但不断得到 stack level too deep 到底是怎么回事,它一直给我错误?
我的节点类

class Node
  attr_accessor :value, :left, :right

  def initialize(value)
    @value = value
    left = nil
    right = nil
  end
end

二叉搜索树类

class Bst
  attr_accessor :root, :size

  def initialize
    @root = nil
    @size = 0
  end

  def insert(value, root=nil)
    if @root == nil
      @root = Node.new(value)
    end
    if value < @root.value
      if @root.left == nil
        @root.left = Node.new(value)
      else
        return insert(value, @root.left)
      end
      return root
    end
    if value > @root.value
      if @root.right == nil
        @root.right = Node.new(value)
      else
        return insert(value, @root.right)
      end
    end
    return root
  end

一旦我尝试向树中添加4,就会发生这种情况

tree = Bst.new
tree.insert(10)
tree.insert(6)
tree.insert(19)
tree.insert(4)
sqyvllje

sqyvllje1#

当您递归并提供新的 root ,您仍在将该值与 @root.value .
自从 4 还不到 10 ,您将递归并传递 @root.left 作为 root . 然而, root 从未使用过;你又在比较了 @root.value ,并使用 @root.left ,而那些永远不会改变;因此,您有无限递归(或者至少无限,直到您破坏堆栈)。
你想和我比较吗 root.value ,并使用 root.left 相反
@rootroot 不同的事物是混乱的,并且会导致逻辑错误。更好的变量命名可能会防止此错误。
编辑:

class Node
  attr_accessor :value, :left, :right

  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end
end

class Bst
  attr_accessor :root, :size

  def initialize
    @root = nil
    @size = 0
  end

  def insert(value, node=nil)
    unless @root
      @root = Node.new(value)
      return
    end

    node ||= @root

    if value < node.value
      if node.left
        return insert(value, node.left)
      else
        node.left = Node.new(value)
      end
    elsif value > node.value
      if node.right
        return insert(value, node.right)
      else
        node.right = Node.new(value)
      end
    end
    @size += 1
    return node
  end
end

tree = Bst.new
tree.insert(10)
tree.insert(6)
tree.insert(19)
tree.insert(4)

p tree

相关问题