Ruby中的二叉搜索树插入方法

Question

我正在研究数据结构，我遇到了一个难题。目标是根据数组元素的值将数组元素插入到二叉搜索树中，即（主树的根节点为数组[0]，左子树的根_node小于父节点，右子树的根节点大于父节点）。这将递归进行，直到所有数组元素都插入BST。

我实现了两个类：

1. 这表示具有属性的节点（数据，左，右）：

class Node
  attr_reader :data
  attr_accessor :left, :right

  def initialize(data)
    @data = data
  end
end

class BST
  attr_accessor :root

  def initialize
    @root = nil
  end

  def insert(node)
    insert_node(@root, node)
  end

  def pre_order(node = @root)
    return '' if node.nil?

    print "#{node.data} "
    pre_order(node.left)
    pre_order(node.right)
  end

  private

  def insert_node(node, element)
    if node.nil?
      node = element
    elsif node.data > element.data
      node.left = insert_node(node.left, element)
    else
      node.right = insert_node(node.right, element)
    end

    node
  end
end

• insert_node是BST的私有方法，它执行将节点插入树的实际工作。我将其与插入分开，因为需要使用RSpec评估的预期解决方案。
• 然后，我做了一个pre_order遍历，将每个节点打印到终端窗口。

def binary_search_tree(array)
  tree = BST.new
  array.each { |e| tree.insert(Node.new(e)) }
  tree.pre_order
end

如果我使用< code>[8，3，10，1，6，14，4，7，13]作为参数运行< code>binary_search_tree方法，我希望以< code># =

样本输入：

将binary_search_tree（[8,3,10,1,6,14,4,7,13]）

预期产出：

8 3 1 6 4 7 10 14 13

得到了：

Answer 1

return '' if node.nil?

这是递归pre_order的停止条件，它是您从binary_search_tree返回的。您似乎没有任何东西可以将您的树格式化为您想要的形状，"8 3 1 6 4 7 10 14 13"。所以添加该逻辑并在binary_search_tree方法的末尾调用它。

Answer 2

哦，我终于找到了一个绕过挑战的方法。我将演示我是如何做到的，以供将来参考：

因此，我决定去掉冗余代码并想出一种方法来解决这个挑战，而不是使用两个单独的方法插入和insert_helper节点。这是BST类结构：

class BST
  attr_accessor :root

  def initialize
    @root = nil
  end

  def insert(node, head = @root)
    return @root = node if @root.nil?

    return node if head.nil?

    if node.data < head.data
      head.left = insert(node, head.left)
    elsif node.data > head.data
      head.right = insert(node, head.right)
    end

    head
  end

  def pre_order(node = @root)
    return '' if node.nil?

    result = ''
    result += "#{node.data} "
    result += pre_order(node.left)
    result += pre_order(node.right)
  end
end

< code>insert方法现在接受两个参数< code>node和(< code>head，这是一个可选参数)，允许我们在子树节点上执行递归操作并生成所需的结果。

pre_order打印每个节点的数据，这是在递归方法中完成的，因此二进制搜索树中的每个节点都以pre_ order格式打印出来。

例如，现在如果您调用BST pre_order方法:

def binary_search_tree(array)
  tree = BST.new
  array.each { |e| tree.insert(Node.new(e)) }
  tree.pre_order
end

puts binary_search_tree([8, 3, 10, 1, 6, 14, 4, 7, 13])

您得到结果8 3 1 6 4 7 10 14 13。通过更改pre_order方法，您可以在post_order、inorder等中打印树节点。

我希望这对其他人有用。编码愉快！！