0

我编写了以下基本二叉搜索树的 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

我的实施有什么问题？我知道我应该调试，我真的有。我放了 print 语句，最终意识到一切，甚至是 Node 对象本身，仍然是 nil。

4

1 回答 1

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
于 2013-10-28T19:11:53.773 回答