Binärer Baum - Wie schließe ich den Stamm in die endgültige Ausgabe ein?

Question

Anfangseingabe = [7, 4, 9, 1, 6, 14, 10]

= erwartete [1, 4, 6, 7, 9, 10, 14]

Und meinen Ausgang .. .

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

I den Stamm nicht, um herauszufinden, wie man schließt Objekt in meinem Ausgangsarray scheinen kann.

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 

Und meine BinaryTree Implementierung

class BinaryTree 
    attr_accessor :payload, :left, :right 

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

end 

Answer 1

Sie auch Art und Weise müssen Sie den Baum gehen:

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