二叉搜索樹不打印任何東西？

Question

我寫了一個基本的二叉搜索樹的以下Ruby實現。

我認爲rt = Node.new(data)實際上並沒有修改底層對象，但實際上只是一個臨時變量而被丟棄。

#!/usr/bin/env ruby 

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

class BST 
    attr_accessor :root 
    def initialize 
    @root = nil 
    end 

    def add_helper(rt, d) 
    if rt != nil 
     add_helper(rt.left, d) if d < rt.data 
     add_helper(rt.right, d) if d > rt.data 
    end 
    rt = Node.new(d) 
    end 

    def add(data) 
    add_helper(root, data) 
    end 

    def print_helper(rt) 
    return if rt == nil 
    pr(rt.left) if rt.left != nil 
    puts rt.data 
    pr(rt.right) if rt.right != nil 
    end 

    def print_tree 
    print_helper(root) 
    end 
end 

########################### 
b = BST.new 
b.add(5) 
b.add(-10) 
b.print_tree 

什麼是錯我的執行？我知道我應該調試，而且我真的有。我把打印語句，並最終意識到，一切，即使是對象本身，仍然是零。

Answer 1

你的直覺是正確的：rt = Node.new(d)正在創建一個新的Node對象，但它立即被丟棄。要解決這個

一種方式是通過在父調用執行任務，你做了另一個遞歸調用之前：

def add_helper rt, d 
    if rt != nil 
    case 
    when d < rt.data 
     # If rt doesn't have a left child yet, assign it here. Otherwise, 
     # recursively descend to the left. 
     if rt.left.nil? 
     rt.left = Node.new(d) 
     else 
     add_helper(rt.left, d) 
     end 
    when d > rt.data 
     # Likewise for the right child. 
     if rt.right.nil? 
     rt.right = Node.new(d) 
     else 
     add_helper(rt.right, d) 
     end 
    else 
     # Handle duplicate additions however you'd like here. 
     raise "Attempt to add duplicate data #{d}!" 
    end 
    else 
    # Now, this can only happen when the root of the entire tree is missing! 
    @root = Node.new(d) 
    end 
end 

另一種方法，這是一個小更優美。將通過add_helper一個塊知道如何添加節點，如果它丟失：

def add_helper rt, d 
    if rt.nil? 
    # This node isn't assigned yet, so tell our caller to add it. 
    yield Node.new(d) 
    else 
    # Otherwise, perform the appropriate recursive call, passing a block that 
    # adds the new node to the correct side of the parent. 
    case 
    when d < rt.data ; add_helper(rt.left, d) { |n| rt.left = n } 
    when d > rt.data ; add_helper(rt.right, d) { |n| rt.right = n } 
    else ; raise "Duplicate insertion!" 
    end 
    end 
end 

def add data 
    # Call add_helper with a block that knows how to assign the root of the whole 
    # tree if it's not there: 
    add_helper(root, data) { |n| @root = n } 
end