Drucken Sie einen binären Baum

18

Inspiriert von einer aktuellen Frage zu SO ...

Schreiben Sie eine Funktion, um einen Binärbaum im folgenden Format zu drucken:

   3
 /   \
1     5
 \   / \
  2 4   6
  1. Die Ausgabe sollte aus einer Reihe von Knoten bestehen, gefolgt von einer Reihe von /und \Zeichen, die Beziehungen angeben, gefolgt von einer Reihe von Knoten usw.
  2. Sie können davon ausgehen, dass alle Knoten als ein einzelnes Zeichen darstellbar sind.
  3. Benachbarte Knoten auf der untersten Ebene sollten durch mindestens ein Leerzeichen voneinander getrennt sein, weiter oben liegende Knoten sollten entsprechend voneinander getrennt sein.
  4. Knoten mit zwei Kindern sollten genau in der Mitte ihrer direkten Kinder platziert werden.
  5. Die Schrägstriche in der Beziehung sollten in der Mitte zwischen dem Elternteil und dem entsprechenden Kind stehen (in beliebiger Reihenfolge).

Eingang:

Die Eingabe wird als Argument für Ihre Funktion bereitgestellt. Ich werde die genaue Struktur des Baums nicht spezifizieren, er muss jedoch als tatsächlicher Binärbaum verwendbar sein. Keine "Bäume werden in meinem Programm als Strings dargestellt, die zufällig der erwarteten Ausgabe entsprechen".

Sie können in einen Ausgabestream drucken oder eine Zeichenfolge zurückgeben, die die Ausgabe Ihrer Wahl enthält.

Punkte für kürzesten Code, aber ich würde eine vollständig funktionierende lange Lösung einer zu 90% funktionierenden kurzen Lösung vorziehen.


Update für das Kopfgeld:

Für das Kopfgeld nehme ich (Optimierer) leichte Änderungen vor:

  • Die Eingabe kann über STDIN, ARGV oder ein Funktionsargument erfolgen.
  • Die Ausgabe muss auf STDOUT (oder console.logfür JS) erfolgen
  • Sie können beispielsweise davon ausgehen, dass die Eingabe in Form eines Arrays erfolgt. [1,2,3]oder[1 2 3]

Update 2 - Der Binärbaum sollte eigentlich ein binärer Suchbaum sein. Da ich dies anfangs nicht erwähnt habe, werde ich den Benutzern erlauben, das Konvertieren eines normalen Arrays in ein binäres Suchbaum-Array als separates Programm zu behandeln, und die endgültige Byteanzahl wird nur dafür sein, dass das Programm das Array als Argument aufnimmt und es ausgibt wie ein binärer Baum.

Anon.
quelle
Sollten wir mehrere Schrägstriche verwenden, die angemessen sind? Müssen wir die Mindestanzahl von Schrägstrichen verwenden? Sollte man zwischen einem einzigen linken und einem einzigen rechten Kind unterscheiden? Wäre es in Ordnung, führende Leerzeichen in jeder Ausgabezeile zu haben?
Was machen wir, wenn der Baum nicht vollständig ist (2 ^ n-1 Knoten für einige n)? Einige Knoten (welche?) Haben nur ein Kind. Wenn wir jedoch Knoten mit nur einem Kind haben dürfen, ist der entartete Baum leicht zu erstellen (1-2-3-4-5-6 nach unten und etwa rechts).
Keith Randall
Wie zeichnet man es für große Zahlen? Zum Beispiel30000,1000,499999
Mohsen

Antworten:

9

Fortran 77 - 1085 Zeichen

      subroutine q(u,t)
      implicit integer(i-z)
      character*33 f,g
      dimension t(u)
      m=ceiling(log(real(u))/log(2.))
      v=2**(m+1)-1
      do l=1,m
         n=2**(l-1)
         k=2**(m-l+2)-3
         w=(3+k)*2**(l-1)-k
         p=1+(v-w)/2
         if(l.ne.1)then
            write(f,'(A,I3,A)')'(A',p,',$)'
            print f,' '
            write(f,'(A5,I3,A3)')'(A3,A',k,',$)'
            do j=2**(l-1),2**l-1
               if(t(j/2).lt.0.or.t(j).lt.0)then
                  print f,'   ',' '
               elseif(mod(j,2).eq.0)then
                  print f,'  /',' '
               else
                  print f,' \ ',' '
               endif
            enddo
            print*
         endif
         write(f,'(A,I3,A)')'(A',p,',$)'
         print f,' '
         write(f,'(A5,I3,A3)')'(I3,A',k,',$)'
         write(g,'(A2,I3,A3)')'(A',k+3,',$)'
         do j=2**(l-1),2**l-1
            if(t(j).ge.0)then
               print f,t(j),' '
            else 
               print g,' '
            endif
         enddo
         print*
      enddo
      end

Der Baum wird im Eingabearray wie tgewohnt dargestellt: Wurzel bei 1, Wurzel-> links bei 2, Wurzel-> rechts bei 3 Wurzel-> links-> links bei 4 ...

Der Ausgang sollte in ein herkömmliches Terminal mit einer Tiefe von bis zu 5 Ebenen passen.

Ich verwende genau einen Schrägstrich zwischen jedem Knotenpaar, der in der Nähe der Spitze ziemlich albern aussieht, wenn es vier oder mehr Ebenen gibt. Ich erlaubte bis zu dreistellige Knoten.

Vollständiges Programm mit Kommentaren und einem Startgerüst:

      program tree

      parameter (l=8)          ! How many nodes to support
      dimension i(l)

c     Initialize the array to all empty nodes
      do j=1,l
         i(j)=-1
      end do
c     Fill in some values
      i(1)=3
      i(2)=1
      i(3)=5
      i(5)=2
      i(6)=4
      i(7)=7
c      i(14)=6
c      i(15)=8
c     Call the printing routine
      call q(l,i)

      stop
      end

c     Print an ASCII representation of the tree
c
c     u the length of the array containing the tree
c     t an integer array representing the tree.
c
c     The array contains only non-negative values, and empty nodes are
c     represented in the array with -1.
c
c     The printed representation uses three characters for every node,
c     and places the (back) slash equally between the two node-centers.
      subroutine q(u,t)
      implicit integer(i-z)
      character*33 f,g
      dimension t(u)
      m=ceiling(log(real(u))/log(2.)) ! maximum depth of the tree
      v=2**(m+1)-1              ! width needed for printing the whole tree
                                ! Optimized from 3*2**m + 1*((2**m)-1) at
                                ! the bottom level
      do l=1,m
         n=2**(l-1)             ! number of nodes on this level
         k=2**(m-l+2)-3         ! internode spacing
         w=(3+k)*2**(l-1)-k     ! width needed for printing this row
                                ! Optimized from 3*2**l + k*((2**l)-1) at
                                ! the bottom level
         p=1+(v-w)/2            ! padding for this row
c     Print the connecting lines associated with the previous level
         if(l.ne.1)then         ! Write the connecting lines
            write(f,'(A,I3,A)')'(A',p,',$)'
            print f,' '
            write(f,'(A5,I3,A3)')'(A3,A',k,',$)'
            do j=2**(l-1),2**l-1
               if(t(j/2).lt.0.or.t(j).lt.0)then
                  print f,'   ',' '
               elseif(mod(j,2).eq.0)then
                  print f,'  /',' '
               else
                  print f,' \ ',' '
               endif
            enddo
            print*
         endif
c     Print the nodes on this level
         write(f,'(A,I3,A)')'(A',p,',$)'
         print f,' '
         write(f,'(A5,I3,A3)')'(I3,A',k,',$)'
         write(g,'(A2,I3,A3)')'(A',k+3,',$)'
         do j=2**(l-1),2**l-1
            if(t(j).ge.0)then
               print f,t(j),' '
            else 
               print g,' '
            endif
         enddo
         print*
      enddo
      end

Ausgabe mit Eingabe entsprechend dem Beispiel:

$ ./a.out 
         3             
     /      \      
     1       5     
      \    /  \  
       2   4   7 
dmckee
quelle
HILFE warum diese Sprache?
Tomsmeding
9
Weil es so schlecht zum Golfen geeignet ist.
dmckee
5

CJam, 100 99 Bytes

q~_,2b,)2\#:Q1@{_2$<Q(S*:T*TQ2/:Q@ts[N+_0@{@1$' >{2$St2$_Q3*&2/^_4$>"\/"=t}*@)}/;U*o]o1:U$>\2*\}h];

Die Eingabe muss eine Liste von Zeichen ohne ASCII-Steuerzeichen sein. Leere Knoten sind mit einem Leerzeichen gekennzeichnet. Es muss auch ein perfekter Binärbaum mit genau 2 n -1 Knoten sein.

Beispiel:

['6 '3 '7 '1 '4 '  '9 '0 '2 '  '5 '  '  '8 ' ]

Oder verwenden Sie einfach Zeichenfolgen:

"63714 902 5  8 "

Ausgabe:

                6              
            /       \          
        3               7      
      /   \               \    
    1       4               9  
   / \       \             /   
  0   2       5           8    

Erläuterung

q~                        " Read input. ";
_,2b,                     " Get tree height. ";
)2\#:Q                    " Get (displayed) tree width and save it in Q. ";
1@                        " Push X=1 and rotate the input to top. ";
{                         " Do: ";
    _2$<                  " Get first X characters from the input. ";
    Q(S*:T                " T = (Q-1) spaces. ";
    *                     " Separate the X characters by T. ";
    TQ2/:Q@t              " Put the string in the middle of T, and divide Q by 2. ";
    s                     " Concatenate everything into a string.
                            This is the line of node labels. ";
    [
        N+                " Append a newline. ";
        _                 " Duplicate. ";
        0@                " Push a 0 and rotate the original string to top. ";
        {                 " For each character: ";
            @             " Rotate the duplicate to top. ";
            1$' >         " Test if the current character is greater than a space. ";
            {             " If true: ";
                2$St      " Set the current character in the duplicate to space. ";
                2$        " Copy the current position I (the number initialized with 0). ";
                _Q3*&2/^  " Calculate I ^ ((I & (3*Q))>>1),
                            the position of the relationship character. ";
                _4$>      " Test if it is greater than the current position. ";
                "\/"=     " Select the relationship character. ";
                t         " Change the character in the duplicate. ";
            }*
            @)            " Increment the current position. ";
        }/
                          " The last two items are the line of relationship characters
                            and the tree width. ";
        ;                 " Discard the tree width. ";
        U*                " If it is the first line, empty the line of
                            relationship characters. ";
        o                 " Output. ";
    ]o                    " Output the line of node labels. ";
    1:U                   " Mark it not the first line. ";
    $>                    " Remove the first X characters from the input. ";
    \2*\                  " Multiply X by 2. ";
}h                        " ...while the input is not empty. ";
];                        " Discard everything in the stack. ";

Konvertierungsskript

[[0LL]W]
[q~{_a_:i={'0+}*}%La2*f+
_,,]z$
1$a+
{
    {
        1$1=1$1=>:T
        {
            ~@0=2 3$1=t
            @1@ta\+
        }*
        T
    }g
}*
0=1=a
{
    {
        (M\+:M;
        La[' LL]aer~
    }%
    _[' LL]a-
}g
];
M0+`-3<']+

Es akzeptiert entweder Zeichen oder einstellige Zahlen.

Beispiele (alle sind gleich):

['6 '7 '9 '3 '1 '2 '8 '4 '0 '5]
[6 7 9 3 1 2 8 4 0 5]
"6793128405"

Ausgabe:

['6 '3 '7 '1 '4 ' '9 '0 '2 ' '5 ' ' '8 ' ]

Es ist eine einfache kartesische Baumkonstruktion.

jimmy23013
quelle
Sie können einfach zwei weitere Bytes hinzufügen und das Konvertierungsskript als richtige Ganzzahlen anstelle von Zeichen eingeben :)
Optimizer
@Optimizer Bearbeitet, um beide zu unterstützen. Ich denke, Zeichen sind sinnvoller, da sie nur Knotennamen mit einem einzelnen Zeichen unterstützen. Es gibt viel mehr Zeichen als einstellige Zahlen.
Jimmy23013
2

Python 2, 411 Bytes

import math
def g(a,o,d,l,b):
 if l<0:
    return
 c=2*b+1
 k=2*l+1
 o[k]=' '*b
 n=d-l
 p=1 if n==0 else 3*2**n-1
 o[k-1]=p/2*' '
 i=0
 for v in a[2**l-1:2**l*2-1]:
    v=' ' if v==None else v
    o[k]+=v+' '*c
    m=' ' if v==' ' else '/' if i%2==0 else '\\'
    o[k-1]+=m+max(1,b)*' ' if i%2==0 else m+p*' '
    i+=1

 g(a,o,d,l-1,c)
def f(a):
 d=int(math.log(len(a),2))
 o=['']*(d*2+2)
 g(a,o,d,d,0)
 print '\n'.join(o[1:])

Hinweis: Die erste Einrückungsstufe ist 1 Leerzeichen, die zweite ist eine Registerkarte.

Rufen Sie fmit einer Liste von Ein-Zeichen-Zeichenfolgen oder None's, z. f(['1',None,'3']). Die Liste darf nicht leer sein.

Dies sollte den Regeln für das Kopfgeld entsprechen.

Konverter-Skript:

Konvertiert und ordnet in das vom Binärbaumdrucker verwendete Format. Beispiel:

$ python conv.py [3,5,4,6,1,2]
['3', '1', '5', None, '2', '4', '6']

-

import sys

def insert(bt, i):
    if i < bt[0]:
        j = 0
    else:
        j = 1

    n = bt[1][j]
    if n == [None]:
        bt[1][j] = [i, [[None], [None]]]
    else:
        insert(bt[1][j], i)

def insert_empty(bt, i):
    if i == 0:
        return
    if bt == [None]:
        bt += [[[None], [None]]]

    insert_empty(bt[1][0], i - 1)
    insert_empty(bt[1][1], i - 1)

def get(l, level):
    if level == 0:
        if type(l) == list:
            return ([], l)
        else:
            return ([l], [])
    elif type(l) != list:
        return ([], [])

    res = []
    left = []

    for r, l in  [get(i, level - 1) for i in l]:
        res += r
        left += l

    return (res, left)

if __name__ == '__main__':
    l = eval(sys.argv[1])
    bt = [l[0], [[None], [None]]]
    map(lambda x: insert(bt, x), l[1:])

    depth = lambda l: 0 if type(l) != list else max(map(depth, l)) + 1
    d = (depth(bt) + 1) / 2

    insert_empty(bt, d - 1)

    flat = []
    left = bt
    i = 0
    while len(left) > 0:
        f, left = get(left, 1)
        flat += f

        i += 1

    for i in range(len(flat) - 1, -1, -1):
        if flat[i] == None:
            flat.pop()
        else:
            break

    flat = map(lambda x: None if x == None else str(x), flat)

    print flat

Beispiele:

Um diese auszuführen, sollten Sie die Hauptdatei bt.pyund die Konverterdatei haben conv.py.

$ python conv.py [3,5,4,6,1,2] | python -c 'import bt; bt.f(input())'
   3
  / \
 1   5
  \ / \
  2 4 6
$ python conv.py [5,4,3,7,9] | python -c 'import bt; bt.f(input())'
   5
  / \
 4   7
/     \
3     9
$ python conv.py [1,2,3,4,5,6] | python -c 'import bt; bt.f(input())'
                               1
                                       \
                                               2
                                                   \
                                                       3
                                                         \
                                                           4
                                                            \
                                                             5
                                                              \
                                                              6
$ python conv.py [6,5,4,3,2,1] | python -c 'import bt; bt.f(input())'
                                   6
                       /
               5
           /
       4
     /
   3
  /
 2
/
1
Tyilo
quelle
Sie erstellen den Binärbaum tatsächlich nicht. Drucken Sie das Array einfach als Binärbaum aus. Die Ausgabe von ['1','2','3','4','5','6','7','8','9']array ist nicht das, was Sie gezeigt haben. Es sollte 3ein rechtes Kind haben, von 2dem ein rechtes Kind 1ein Wurzelelement ist.
Optimierer
@Optimizer Aus der Frage: "Die Eingabe wird als Argument für Ihre Funktion bereitgestellt. Ich werde die genaue Struktur des Baums nicht angeben, sie muss jedoch als tatsächlicher Binärbaum verwendbar sein." Ich sehe keine spezifische Definition des verwendeten Array-Formats.
Tyilo
Bei der Frage geht es ursprünglich darum, einen Binärbaum zu drucken . Ihre Ausgaben sind keine binären Bäume. Das Format des Arrays hat nichts damit zu tun.
Optimierer
@Optimizer wie sind sie nicht binäre Bäume? Aus Wikipedia: Ein binärer Baum ist eine Baumdatenstruktur, in der jeder Knoten höchstens zwei untergeordnete Knoten hat. Hat einer der Knoten mehr als zwei Kinder?
Tyilo
Ughh. Ich sehe jetzt. Ich denke, es gibt hier einen Begriff Missverständnis. Selbst in den ersten Beispielen hat die Ausgabe das Format eines binären Suchbaums . Und mein Kopfgeld gilt auch nur für einen binären Suchbaum. Entschuldigung für die Verwirrung dort.
Optimierer
1

APL, 125 Zeichen

{⍵{x←⍵[0;d←⌈2÷⍨1⌷⍴⍵]←↑⍺
2 1∇{x[2↓⍳↑⍴x;(⍳d)+d×⍺-1]←⍵(⍺⍺⍣t←0≠⍴⍵)2↓x[;⍳d]
x[1;d+(⌈d÷4)ׯ1*⍺]←' /\'[t×⍺]}¨⍺[2 1]
x}' '⍴⍨2(×,*)≡⍵}

Beispiel:

{⍵{x←⍵[0;d←⌈2÷⍨1⌷⍴⍵]←↑⍺
2 1∇{x[2↓⍳↑⍴x;(⍳d)+d×⍺-1]←⍵(⍺⍺⍣t←0≠⍴⍵)2↓x[;⍳d]
x[1;d+(⌈d÷4)ׯ1*⍺]←' /\'[t×⍺]}¨⍺[2 1]
x}' '⍴⍨2(×,*)≡⍵}('1' ('2' ('3' ('4' ()()) ('5' ()())) ('6' ()('7' ()())))('8' ()('9' ('0' ()())())))

Hier getestet.

jimmy23013
quelle
Ist das auch das Konvertierungsskript?
Optimierer
@Optimizer Es wird das verschachtelte Array-Eingabeformat verwendet, das wahrscheinlich als binärer Suchbaum verwendet werden kann (ich bin mir jedoch nicht sicher, wie komplex es ist). Wenn ich ein paar übliche Formate verwenden muss ... mache ich das vielleicht später.
Jimmy23013
@Optimizer Wenn Sie die Frage noch einmal lesen, bedeutet "binäres Suchbaum-Array" das Array eines vollständigen Binärbaums in der Reihenfolge der Tiefe (oder etwas anderem)? Ich dachte nicht, dass es etwas Bestimmtes war. Und die Suche nach diesem Begriff hat nichts Sinnvolles ergeben.
Jimmy23013
@Optimizer Nun, das war genau das, was ich meinte. Aber ich denke nicht, dass es normalerweise "binäres Suchbaum-Array" genannt wird, sondern nur "eine Art Array-Speicherung von Binärbäumen". Es muss wahrscheinlich etwas geklärt werden ... Und ich werde diese Antwort wahrscheinlich einige Tage später
korrigieren
0

Ruby, 265 Bytes

def p(t);h=Math.log(t.length,2).to_i;i=-1;j=[];0.upto(h){|d|s=2**(h-d)-1;c=2**d;if d>0;m=' '*(s+s/2)+'I'+' '*(s-s/2);1.upto(d){m+=' '+m.reverse};w=i;puts m.gsub(/I/){|o|t[w+=1]?(w%2==0?'\\':'/'):' '};end;puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' ';};end

Die @ proudhaskeller-Version, 269 Bytes

def p(t);h=Math.log(t.length,2).to_i;i=-1;j=[];0.upto(h){|d|s=(z=2**(h-d))-1;c=2**d;if d>0;m=' '*(s+z/2)+'I'+' '*(s-z/2);1.upto(d){m+=' '+m.reverse};w=i;puts m.gsub(/I/){|o|t[w+=1]?(w%2==0?'\\':'/'):' '};end;puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' ';};end

Erklärung

Die ausführliche Version:

def p(t)
  depth = Math.log(t.length, 2).floor
  i = -1
  j = []
  (0..depth).each do |d|
    s = 2 ** (depth-d)-1
    c = 2 ** d

    if d > 0
      m = ' '*(s+s/2) + '|' + ' '*(s-s/2)
      w = i
      1.upto(d) { m += ' ' + m.reverse }
      puts m.gsub(/\|/) { |o| t[w+=1] ? (w%2==0 ? '\\' : '/') : ' ' }
    end

    puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' '
  end
end

Beispiel

n = nil
p([
  1, 2, 3, 4, 5,
  n, 7, 8, 9, 0,
  1, n, n, 4, 5,
  6, 7, 8, 9, 0,
  1, 2, 3, n, n,
  n, n, 8, 9, n,
  n
])

gibt:

               1               
          /         \          
       2               3       
    /     \               \    
   4       5               7   
 /   \   /   \           /   \ 
 8   9   0   1           4   5 
/ \ / \ / \ / \         / \    
6 7 8 9 0 1 2 3         8 9   

(Ich habe das Konvertierungsskript noch nicht geschrieben.)

AlexRath
quelle
Ihre Schrägstriche sind nicht genau in der Mitte
stolzer Haskeller
@proudhaskeller "rund wie du willst", ich fand es cooler so. Sie können s / 2 durch (s + 1) / 2 ersetzen, wenn Sie möchten.
AlexRath
Nein, die Schrägstriche in der ersten Reihe sind nicht genau in der Mitte, in dieser Reihe handelt es sich nicht um Rundungen
stolzer Haskeller
@proudhaskeller Wenn Sie s / 2 durch (s + 1) / 2 ersetzen, sind sie genau in der Mitte, aber ich bevorzuge diesen Weg, da der linke und der rechte Zweig so aussehen.
AlexRath
es ist gegen die
spezifikation