二叉搜索树不打印任何东西？

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