ruby 这个递归的树构建算法中到底出了什么问题,导致了它的溢出?

3duebb1j  于 2023-04-29  发布在  Ruby
关注(0)|答案(1)|浏览(117)

我正在学习二叉树,并试图写一个递归方法,当给定一个排序数组时,可以构建一个平衡二叉树。我被一个溢出条件卡住了,不知道我做错了什么,也不知道如何修复。一些指导会很有帮助。所讨论的方法是#build_balanced_tree(array),产生可再现示例的所有相关代码如下:

class Node
  attr_accessor :value, :left, :right
  
  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end
end

class Tree
  attr_reader :array
  attr_accessor :root

  def initialize
    @array = nil
    @root = nil
  end

  def build_balanced_tree(array)
    return if array.empty?
    array_mid_index = (array.length - 1) / 2
    self.root = Node.new(array[array_mid_index])
    self.root.left = build_balanced_tree(array[0..(array_mid_index - 1)])
    self.root.right = build_balanced_tree(array[(array_mid_index + 1)..(array.length - 1)])
    return root
  end
end

array = [1, 4, 7, 13, 65, 97]
tree = Tree.new
p tree.build_balanced_tree(array)

此错误消息;当代码碰到self.root.left = ...行并将数组的左半部分传递回自身时,会抛出:in 'new': stack level too deep (SystemStackError)
我怀疑问题的部分原因可能是我的递归方法正在设置self.root,并且因为@root是显式命名的,所以它递归地不断覆盖自己,但我无法想象如何匿名Node的创建和值设置,同时确保在第一次迭代时设置@root。这段代码可能还存在多个其他问题,我将感激任何帮助。谢谢大家。

fnatzsnv

fnatzsnv1#

无限递归的原因是array[0..(array_mid_index - 1)]可以变成array[0..-1],这意味着 * 整个 * 数组,而当array_mid_index为0时,你真的想得到一个 * 空 * 数组。
有几种方法可以解决这个问题;一种是使用slice,它以长度作为第二个参数,因此可以是array_mid_index。那么就不可能有这样的误解。
你也是对的,分配给self.root有问题。您只希望该赋值发生一次,这意味着您不应该在将被递归调用的函数中执行该赋值,而是在单独的函数中执行。
我建议为此创建一个 static 方法,因为调用者必须在实际调用此函数之前创建一个新的Tree示例,这让人感觉不自然。静态方法可以自己创建新示例,并在填充后返回该示例。
递归函数可以成为Node类上的静态方法,因为它不需要任何Tree类的知识。
注意:在Tree类上不需要@array属性。数组只是一个临时用于构建树的参数,然后在树的状态中没有任何作用。
下面是它看起来的样子:

class Node
  attr_accessor :value, :left, :right
  
  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end

  def self.build_balanced_tree(array)
    return if array.empty?
    array_mid_index = (array.length - 1) / 2
    node = Node.new(array[array_mid_index])
    node.left = build_balanced_tree(array.slice(0, array_mid_index))
    node.right = build_balanced_tree(array[(array_mid_index + 1)...])
    return node
  end
end

class Tree
  attr_accessor :root

  def initialize
    @root = nil
  end

  def self.build_balanced_tree(array)
    tree = Tree.new
    tree.root = Node.build_balanced_tree(array)
    return tree
  end
end

array = [1, 4, 7, 13, 65, 97]
p Tree.build_balanced_tree(array)

相关问题