バイナリツリー - トランクを最終出力に含めるにはどうすればよいですか？

Question

初期入力は= = [1、4、6、7、9、10、14]

私の出力を[7、4、9、1、6、14、10]

を期待します.. 。

[4、9、1、6、14、10]私は私の出力配列内のトランクオブジェクトを含める方法を見つけ出すことができないよう

。

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 

そして、私のBinaryTree実装

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