从字符串构造 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

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

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

从字符串构造 Ruby 二叉树

Constructing a Ruby Binary Tree from String

ruby

algorithm

binary-tree