使用Rspec的Ruby递归深度搜索

Question

我目前面临的挑战是理解和实施DFS。假设< code>#find方法接受< code>root和< code>data(归类为节点)，如果匹配，则返回< code>title。这是我目前拥有的，也是我唯一能找到的帮助:Ruby递归DFS方法。

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

我正在努力通过

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)>'

我希望返回< code>data (node)，但不确定如何解释测试并获得正确的输出。感谢任何帮助和/或建议。谢了。

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

您将返回＜code＞数据＜/code＞，这将是一个字符串，或者至少这是在比较＜code＞根时所指示的。title==数据。您希望返回节点本身。