ruby-on-rails - 使用 Rspec 的 Ruby 递归深度搜索

Question

我目前在理解和实现 DFS 方面遇到了问题，这是我目前面临的挑战。 #find 方法假设采用 root 和 data(分类为节点)并返回 title 如果有一场比赛。这是我目前拥有的，我能找到的唯一帮助是:Ruby recursive DFS method .

class Node
  attr_accessor :title
  attr_accessor :rating
  attr_accessor :left
  attr_accessor :right

  def initialize(title, rating)
    @title = title
    @rating = rating
    @left = nil
    @right = nil
  end
end

class BinarySearchTree

  def initialize(root)
    @root = root
  end

  def insert(root, node)
    if @root.nil?
      @root = node
    else
      current = @root

      while(true) #while an of the below are true statements, keep performing while loop
        if node.rating >= current.rating
          if current.right == nil
            current.right = node
            break
          else
            current = current.right #moving down the right side until nil
          end
        else
          if current.left == nil
            current.left = node
            break
          else
          current = current.left  #moving down the left side until nil
          end
        end
      end
    end
  end

  # Recursive Depth First Search
  def find(root, data)
    #if data == nil
      #return nil
    #elsif root.title == data
      #return data
    #else
    #left = find(root.left, data) if root.left
    #right = find(root.right, data) if root.right
    #left or right
  end

我正在尝试通过 Rspec

describe "#find(data)" do
    it "handles nil gracefully" do
      tree.insert(root, empire)
      tree.insert(root, mad_max_2)
      expect(tree.find(root, nil)).to eq nil
    end

    it "properly finds a left node" do
      tree.insert(root, pacific_rim)
      expect(tree.find(root, pacific_rim.title).title).to eq "Pacific Rim"
    end

    it "properly finds a left-left node" do
      tree.insert(root, braveheart)
      tree.insert(root, pacific_rim)
      expect(tree.find(root, pacific_rim.title).title).to eq "Pacific Rim"
    end

    it "properly finds a left-right node" do
      tree.insert(root, donnie)
      tree.insert(root, inception)
      expect(tree.find(root, inception.title).title).to eq "Inception"
    end

    it "properly finds a right node" do
      tree.insert(root, district)
      expect(tree.find(root, district.title).title).to eq "District 9"
    end

    it "properly finds a right-left node" do
      tree.insert(root, hope)
      tree.insert(root, martian)
      expect(tree.find(root, martian.title).title).to eq "The Martian"
    end

    it "properly finds a right-right node" do
      tree.insert(root, empire)
      tree.insert(root, mad_max_2)
      expect(tree.find(root, mad_max_2.title).title).to eq "Mad Max 2: The Road Warrior"
    end
  end

我遇到的常见错误

BinarySearchTree#find(data) properly finds a left node
     Failure/Error: expect(tree.find(root, pacific_rim.title).title).to eq "Pacific Rim"

     NoMethodError:
       undefined method `title' for "Pacific Rim":String
     # ./binary_search_tree.rb:37:in `find'
     # ./binary_search_tree_spec.rb:66:in `block (3 levels) in <top (required)>'

我想要返回 data(节点)，但不确定如何解释测试并获得正确的输出。任何帮助和/或建议表示赞赏。谢谢。

Answer 1

这是您的#find 方法:

def find(root, data)
  if data == nil
    return nil
  elsif root.title == data
    return data
  else
    left = find(root.left, data) if root.left
    right = find(root.right, data) if root.right
    left or right
  end
end

您正在返回 data，这将是一个字符串 - 或者至少这是您比较 root.title == data 时所指示的内容。您想要返回节点本身。