#!/usr/bin/perl

use strict;
use warnings;
use Data::Dumper;

my @array = (3,5,1,76,2,5,9,4,1,23,72,12);
my $ref = newtree(\@array);
#print Dumper ( $ref );
ausgabe( $ref );

sub newtree {
    my $ref_liste1 = shift;
    # Wurzel des Baums erzeugen
    my $ref_wurzel = knot(shift @$ref_liste1);
    my $knoten     = $ref_wurzel;
 
    for my $zzahl (@$ref_liste1){
        while (1){
            if($zzahl < $knoten->{'zahl'}){
                if(defined($knoten->{'linksweg'})){
                    $knoten = $knoten->{'linksweg'};
                }
                else {
                    $knoten->{'linksweg'} = knot($zzahl);
                    $knoten = $knoten->{linksweg};
                    last; #Ende
                }            
            }
            #wenns Links nicht mehr weiter geht, geh rechts weiter
            else {
                if ($zzahl >= $knoten->{'zahl'}) {
                    if(defined($knoten->{'rechtsweg'})){
                        $knoten =$knoten->{'rechtsweg'};
                    }
                    else {
                        $knoten->{'rechtsweg'} = knot($zzahl);
                        $knoten = $knoten->{rechtsweg};
                        last;
                    }
                }
            }
        }
    }
    return $ref_wurzel;
}

sub knot {
    my $knoten = {
        'zahl'      => shift,
        'linksweg'  => undef,
        'rechtsweg' => undef 
    };
    return $knoten;
}

sub ausgabe {
  my $self = shift;
  my $knoten = $self;
 
    if (defined($knoten->{'linksweg'}))
    {
    ausgabe($knoten->{'linksweg'});
    }
    print " $knoten->{'zahl'} ";
    # print "$self->{'wurzel'}->{'zahl'}\n";

    if(defined($knoten->{'rechtsweg'}))
    {
    ausgabe($knoten->{'rechtsweg'});
    }
}