ruby - 从字符串构建 Ruby 二叉树

Question

计算科学的新手。

我有 Ruby 中二叉树的基础知识:

class Node
  attr_accessor :left, :right, :value
  def initialize(value)
    @value = value
  end
end

如果我手动构造它，这会很好地工作，例如，如果我希望 tom 成为 ben 的子节点:

ben = Node.new('Ben')
tom = Node.new('Tom')

ben.left = tom

我需要解决的挑战之一是如何为输入的父/子对构建树。这是一个示例输入字符串:

peter tom
peter marie
marie john
tom oscar

我的二叉树看起来像这样:

    peter
      |
 tom     marie
  |        |
oscar     john

我想知道是否可以找到一些方向将以下格式的多个字符串 "[parent] [child]" 转换为二叉树。

谢谢 :)

Answer 1

使用散列来存储数据:

data = Hash.new { |h, k| h[k] = Node.new k }

while !(line = gets.strip).empty?
    parent, child = line.split.map { |value| data[value] }
    if !parent.left
        parent.left = child
    elsif !parent.right
        parent.right = child
    else
        raise "#{parent.value} already has both a left and right child"
    end
end