Wydrukuj drzewo binarne

18

Zainspirowany ostatnim pytaniem dotyczącym SO ...

Napisz funkcję, aby wydrukować drzewo binarne w następującym formacie:

   3
 /   \
1     5
 \   / \
  2 4   6
  1. Dane wyjściowe powinny składać się z linii węzłów, po której następuje linia znaków /i \znaków wskazujących relacje, po której następuje linia węzłów itp.
  2. Możesz założyć, że wszystkie węzły są reprezentowane jako pojedynczy znak.
  3. Sąsiadujące węzły na najniższym poziomie powinny być oddzielone co najmniej jedną spacją, węzły dalej w górę powinny być odpowiednio oddzielone.
  4. Węzły z dwójką dzieci powinny być umieszczone dokładnie pośrodku ich bezpośrednich dzieci.
  5. Ukośniki relacji powinny znajdować się w połowie drogi między rodzicem a odpowiednim dzieckiem (w dowolnym kierunku).

Wejście:

Dane wejściowe zostaną przekazane jako argument funkcji. Nie podam dokładnej struktury drzewa, jednak musi on być użyteczny jako rzeczywiste drzewo binarne. Żadne „drzewa nie są reprezentowane w moim programie jako ciągi, które przypadkowo wyglądają jak oczekiwane wyniki”.

Możesz wydrukować do strumienia wyjściowego lub zwrócić ciąg zawierający dane wyjściowe, według własnego wyboru.

Punkty za najkrótszy kod, ale zdecydowanie wolałbym w pełni działające długie rozwiązanie niż 90% pracujące krótkie.


Aktualizacja nagrody

Jeśli chodzi o nagrodę, ja (Optymalizator) wprowadzam niewielkie zmiany:

  • Dane wejściowe mogą pochodzić z argumentu STDIN, ARGV lub funkcji.
  • Dane wyjściowe muszą być na STDOUT (lub console.logdla JS)
  • Możesz założyć, że dane wejściowe mają postać tablicy, na przykład. [1,2,3]lub[1 2 3]

Aktualizacja 2 - Drzewo binarne powinno być drzewem wyszukiwania binarnego. Ponieważ początkowo o tym nie wspominałem, pozwolę użytkownikom traktować konwersję normalnej tablicy na binarną tablicę drzewa wyszukiwania jako osobny program, a końcowa liczba bajtów będzie tylko dla programu, który pobierze tablicę jako argument i wydrukuje ją jak drzewo binarne.

Zaraz.
źródło
Czy powinniśmy użyć kilku ukośników relacji były odpowiednie? Czy musimy użyć minimalnej liczby ukośników? Czy należy rozróżniać posiadanie jednego lewego dziecka i jednego prawego dziecka? Czy dobrze byłoby mieć spacje wiodące w każdej linii wyjściowej?
Co robimy, jeśli drzewo nie jest kompletne (2 ^ n-1 węzłów dla niektórych n)? Niektóre węzły (które?) Mają tylko jedno dziecko. Ale jeśli wolno nam mieć węzły tylko z jednym dzieckiem, zdegenerowane drzewo jest łatwe do zrobienia (powiedzmy 1-2-3-4-5-6 w dół i na prawo).
Keith Randall
Jak rysujesz dla dużych liczb? Na przykład30000,1000,499999
Mohsen

Odpowiedzi:

9

Fortran 77 - 1085 znaków

      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

Drzewo jest reprezentowane w tablicy wejściowej tw zwykły sposób, root na 1, root-> left na 2, root-> right na 3 root-> left-> left o 4 ...

Wyjście powinno mieścić się w konwencjonalnym terminalu o głębokości do 5 poziomów.

Używam dokładnie jednego ukośnika między każdą parą węzłów, co wygląda dość głupio u góry, gdy są cztery lub więcej poziomów. Pozwoliłem na maksymalnie trzycyfrowe węzły.

Pełny program z komentarzami i rusztowaniem uruchamiającym:

      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

Dane wyjściowe z danymi wejściowymi równoważnymi z przykładem:

$ ./a.out 
         3             
     /      \      
     1       5     
      \    /  \  
       2   4   7 
dmckee
źródło
POMÓŻ, dlaczego ten język?
tomsmeding,
9
Ponieważ tak źle nadaje się do gry w golfa.
dmckee,
5

CJam, 100 99 bajtów

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];

Dane wejściowe muszą być listą znaków, bez znaków kontrolnych ASCII. Puste węzły są oznaczone spacją. Musi to być także idealne drzewo binarne z dokładnie 2 węzłami n -1.

Przykład:

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

Lub po prostu użyj ciągów:

"63714 902 5  8 "

Wynik:

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

Wyjaśnienie

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. ";

Skrypt konwersji

[[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<']+

Akceptuje znaki lub cyfry jednocyfrowe.

Przykłady (wszystkie są takie same):

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

Wynik:

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

Jest to prosta konstrukcja drzewa kartezjańskiego.

jimmy23013
źródło
Możesz po prostu dodać jeszcze dwa bajty i wprowadzić w skrypcie konwersji odpowiednie liczby całkowite zamiast znaków :)
Optimizer
@Optimizer Edytowane, aby obsługiwać oba. Myślę, że znaki mają większy sens, ponieważ obsługują tylko nazwy węzłów z jednym znakiem. Jest o wiele więcej znaków niż cyfr jednocyfrowych.
jimmy23013,
2

Python 2, 411 bajtów

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:])

Uwaga: Pierwszy poziom wcięcia to 1 spacja, drugi to jedna tabulacja.

Wywołanie fz listą ciągów lub znaków jednoznakowych None, np. f(['1',None,'3']). Lista nie może być pusta.

To powinno być zgodne z zasadami nagrody.

Skrypt konwertera:

Konwertuje i tablicę na format używany przez drukarkę drzewa binarnego. Przykład:

$ 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

Przykłady:

Aby je uruchomić, musisz mieć nazwę pliku głównego bt.pyi nazwę pliku konwertera 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
źródło
W rzeczywistości nie tworzysz drzewa binarnego. Wystarczy wydrukować tablicę jako drzewo binarne. Dane wyjściowe ['1','2','3','4','5','6','7','8','9']tablicy nie są tym, co pokazałeś. Powinien mieć 3jako właściwe dziecko, 2którego właściwe dziecko 1jest elementem głównym.
Optymalizator
@Optimizer Z pytania: „Dane wejściowe zostaną dostarczone jako argument do twojej funkcji. Nie podam dokładnej struktury drzewa, jednak musi on być użyteczny jako rzeczywiste drzewo binarne.” Nie widzę konkretnej definicji używanego formatu tablicy.
Tyilo,
Pytanie pierwotnie dotyczy drukowania drzewa binarnego . Twoje dane wyjściowe nie są drzewami binarnymi. Format tablicy nie ma z tym nic wspólnego.
Optymalizator
@Optimizer, jak to nie są drzewa binarne? Z Wikipedii: drzewo binarne to struktura danych drzewa, w której każdy węzeł ma najwyżej dwoje dzieci. Czy któryś z węzłów ma więcej niż dwoje dzieci?
Tyilo,
Uhh Teraz widzę. Myślę, że istnieje tutaj nieporozumienie. Nawet w początkowych przykładach dane wyjściowe mają format drzewa wyszukiwania binarnego . A moja nagroda dotyczy tylko drzewa wyszukiwania binarnego. Przepraszam za zamieszanie.
Optymalizator
1

APL, 125 znaków

{⍵{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(×,*)≡⍵}

Przykład:

{⍵{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' ()())())))

Testowane tutaj.

jimmy23013
źródło
Czy to także skrypt konwersji?
Optymalizator
@Optimizer Pobiera zagnieżdżony format wejściowy, który prawdopodobnie może być użyty jako drzewo wyszukiwania binarnego (ale nie jestem pewien co do złożoności). Jeśli muszę użyć bardziej typowych formatów ... może zrobię to później.
jimmy23013,
@Optimizer Czytając teraz ponownie pytanie, „tablica drzewa wyszukiwania binarnego” oznacza tablicę pełnego drzewa binarnego w kolejności głębokości (czy coś innego)? Nie sądziłem, że to było coś konkretnego. A wyszukiwanie tego terminu nie przyniosło nic użytecznego.
jimmy23013,
@Optimizer Cóż, właśnie o to mi chodziło. Ale nie sądzę, że zwykle nazywa się to „tablicą drzewa wyszukiwania binarnego”, ale tylko „rodzajem przechowywania tablicy drzew binarnych”. Prawdopodobnie wymaga wyjaśnienia ... I prawdopodobnie naprawię tę odpowiedź kilka dni później, może w innym języku ...
jimmy23013,
0

Rubinowy, 265 bajtów

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

Wersja @proudhaskeller, 269 bajtów

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

Wyjaśnienie

Pełna wersja:

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

Przykład

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
])

daje:

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

(Nie napisałem jeszcze skryptu konwersji).

AlexRath
źródło
twoje cięcia nie są dokładnie w środku
dumny haskeller
@proudhaskeller „okrągłe, jak chcesz”, pomyślałem, że w ten sposób wygląda fajniej. Możesz zamienić s / 2 na (s + 1) / 2, jeśli chcesz.
AlexRath,
Nie, ukośniki w pierwszym rzędzie nie są dokładnie w środku, w tym rzędzie nie chodzi o zaokrąglanie
dumny haskeller
@proudhaskeller Jeśli zamienisz s / 2 na (s + 1) / 2, są one dokładnie pośrodku, ale nadal wolę ten sposób, ponieważ sprawia, że ​​gałęzie znajdujące się najbardziej na lewo i na prawo wyglądają dookoła.
AlexRath,
jest to niezgodne ze specyfikacją ...
dumny haskeller