紅寶石遞歸深度搜索與Rspec

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什麼指示。你想要返回節點本身。