二叉树 - 如何在最终输出中包含树干？

Question

初始输入 = [7, 4, 9, 1, 6, 14, 10]

预期 = [1, 4, 6, 7, 9, 10, 14]

我的输出...

[4, 9, 1, 6, 14, 10]

我似乎无法弄清楚如何在我的输出数组中包含 trunk 对象。

def insert_node(element,trunk)
  if element < trunk.payload && trunk.left == nil
    # Build node and place it on left of trunk
    trunk.left = BinaryTree.new(element, nil, nil)
  elsif element > trunk.payload && trunk.right == nil
    # Build node and place it on right of trunk
    trunk.right = BinaryTree.new(element, nil, nil)
  elsif element < trunk.payload
    # Update pointer
    insert_node(element, trunk.left)
  elsif element > trunk.payload
    # Update pointer
    insert_node(element, trunk.right)
  end
end

def build_tree(array)
    trunk = BinaryTree.new(array.first, nil, nil)
    array.shift
    output = []

    array.each do |element|
      # Insert each element
      output << insert_node(element,trunk).payload
    end

  return output
end

还有我的二叉树实现

class BinaryTree
  attr_accessor :payload, :left, :right

  def initialize(payload, left, right)
    @payload = payload
    @left = left
    @right = right
  end

end

Answer 1

你还需要走树的方法：

class BinaryTree
  attr_reader :payload, :left, :right

  def initialize(payload, left = nil, right = nil)
    @payload = payload
    @left = left
    @right = right
  end

  def walk
    (left ? left.walk : []) + [payload] + (right ? right.walk : [])
  end

  def insert_node(element)
    if element < payload && left == nil
      # Build node and place it on left of trunk
      @left = self.class.new(element)
    elsif element > payload && right == nil
      # Build node and place it on right of trunk
      @right = self.class.new(element)
    elsif element < payload
      # Update pointer
      left.insert_node(element)
    elsif element > payload
      # Update pointer
      right.insert_node(element)
    end
  end

  def self.build_from_array(array)
    new(array.shift).tap do |trunk|
      array.each { |element| trunk.insert_node(element) }
    end
  end
end

input =  [7, 4, 9, 1, 6, 14, 10]
expected =  [1, 4, 6, 7, 9, 10, 14]
output = BinaryTree.build_from_array(input).walk
p output
p output == expected

二叉树 - 如何在最终输出中包含树干？

Binary Tree - How do I include the trunk in the final output?

ruby

binary-tree