Cetak Pohon Biner

18

Terinspirasi oleh pertanyaan terbaru tentang ...

Tulis fungsi untuk mencetak pohon biner dalam format berikut:

   3
 /   \
1     5
 \   / \
  2 4   6
  1. Outputnya harus terdiri dari garis node, diikuti oleh garis /dan \karakter yang menunjukkan hubungan, diikuti oleh garis node, dll.
  2. Anda dapat menganggap semua node direpresentasikan sebagai satu karakter.
  3. Node yang berdekatan pada level terendah harus dipisahkan oleh setidaknya satu ruang, node lebih jauh harus dipisahkan sebagaimana mestinya.
  4. Node dengan dua anak harus ditempatkan tepat di tengah anak-anak langsung mereka.
  5. Garis miring hubungan harus berada di tengah antara orang tua dan anak yang sesuai (putaran ke arah mana pun yang Anda inginkan).

Memasukkan:

Input akan diberikan sebagai argumen untuk fungsi Anda. Saya tidak akan menentukan struktur pohon yang tepat, namun itu harus dapat digunakan sebagai pohon biner yang sebenarnya. Tidak "pohon diwakili dalam program saya karena string secara kebetulan tampak seperti hasil yang diharapkan".

Anda dapat mencetak ke aliran output atau mengembalikan string yang berisi output, pilihan Anda.

Poin untuk kode terpendek, tapi saya lebih suka solusi panjang yang sepenuhnya berfungsi daripada 90% -pekerja pendek.


Perbarui untuk karunia:

Untuk hadiah, saya (Pengoptimal) melakukan sedikit perubahan:

  • Masukan dapat dari argumen STDIN, ARGV atau fungsi.
  • Output harus pada STDOUT (atau console.loguntuk JS)
  • Anda dapat berasumsi bahwa input dalam bentuk array, misalnya. [1,2,3]atau[1 2 3]

Pembaruan 2 - Pohon biner sebenarnya harus pohon pencarian biner. Karena saya tidak menyebutkan ini pada awalnya, saya akan memungkinkan pengguna untuk memperlakukan mengubah array normal menjadi array pohon pencarian biner sebagai program terpisah dan jumlah byte terakhir hanya akan untuk program untuk mengambil dalam array sebagai argumen dan mencetaknya seperti pohon biner.

Segera.
sumber
Haruskah kita menggunakan beberapa garis miring hubungan yang sesuai? Haruskah kita menggunakan jumlah garis miring minimum? Haruskah seseorang membedakan antara memiliki anak kiri tunggal dan anak kanan tunggal? Apakah baik-baik saja untuk memiliki ruang terdepan di setiap jalur keluaran?
Apa yang kita lakukan jika pohon tidak lengkap (2 ^ n-1 node untuk beberapa n)? Beberapa node (yang mana?) Hanya memiliki satu anak. Tetapi jika kita diizinkan memiliki simpul dengan hanya satu anak, pohon degenerasi mudah dibuat (1-2-3-4-5-6 ke bawah dan ke kanan, katakanlah).
Keith Randall
Bagaimana Anda menggambarnya dalam jumlah besar? Misalnya30000,1000,499999
Mohsen

Jawaban:

9

Fortran 77 - 1085 karakter

      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

Pohon diwakili dalam larik input t dengan cara biasa, root di 1, root-> kiri di 2, root-> kanan di 3 root-> kiri-> kiri di 4 ...

Output harus sesuai dengan terminal konvensional hingga 5 level.

Saya menggunakan tepat satu garis miring di antara setiap pasangan node, yang terlihat cukup konyol di dekat bagian atas begitu ada empat atau lebih level. Saya mengizinkan hingga tiga digit node.

Program lengkap dengan komentar dan scaffold peluncuran:

      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

Output dengan input yang setara dengan contoh:

$ ./a.out 
         3             
     /      \      
     1       5     
      \    /  \  
       2   4   7 
dmckee
sumber
BANTUAN mengapa bahasa ini?
tommeding
9
Karena itu sangat tidak cocok untuk bermain golf.
dmckee
5

CJam, 100 99 byte

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

Input harus berupa daftar karakter, tanpa karakter kontrol ascii. Node kosong dilambangkan dengan spasi. Itu juga harus pohon biner yang sempurna dengan tepat 2 n -1 node.

Contoh:

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

Atau cukup gunakan string:

"63714 902 5  8 "

Keluaran:

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

Penjelasan

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

Skrip konversi

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

Ini menerima karakter atau angka satu digit.

Contoh (semuanya sama):

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

Keluaran:

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

Ini adalah konstruksi pohon Cartesian yang lurus ke depan.

jimmy23013
sumber
Anda bisa menambahkan dua byte lagi dan menjadikan input skrip konversi sebagai bilangan bulat yang tepat alih-alih karakter :)
Pengoptimal
@Optimizer Diedit untuk mendukung keduanya. Saya pikir karakter lebih masuk akal karena hanya mendukung nama simpul dengan satu karakter. Ada lebih banyak karakter daripada angka satu digit.
jimmy23013
2

Python 2, 411 byte

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

Catatan: Level indentasi pertama adalah 1 spasi, yang kedua adalah satu tab.

Panggil fdengan daftar string satu karakter atau None, misalnya.f(['1',None,'3']). Daftar tidak boleh kosong.

Ini harus mematuhi aturan untuk hadiah.

Skrip konverter:

Mengkonversi dan mengatur ke format yang digunakan oleh printer pohon biner. Contoh:

$ 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

Contoh:

Untuk menjalankan ini, Anda harus memiliki nama file utama bt.pydan nama file konverter 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
sumber
Anda sebenarnya tidak membuat pohon biner. Hanya mencetak array sebagai pohon biner. Output dari ['1','2','3','4','5','6','7','8','9']array bukanlah yang Anda tunjukkan. Seharusnya 3sebagai anak kanan 2yang merupakan anak kanan 1yang merupakan elemen root.
Pengoptimal
@Optimizer Dari pertanyaan: "Input akan diberikan sebagai argumen untuk fungsi Anda. Saya tidak akan menentukan struktur pohon yang tepat, namun harus dapat digunakan sebagai pohon biner yang sebenarnya." Saya tidak melihat definisi spesifik dari format array yang digunakan.
Tyilo
Pertanyaan awalnya adalah tentang mencetak pohon biner . Output Anda bukan pohon biner. Format array tidak ada hubungannya dengan itu.
Pengoptimal
@ Opptizer bagaimana mereka bukan pohon biner? Dari Wikipedia: pohon biner adalah struktur data pohon di mana setiap simpul memiliki paling banyak dua anak. Apakah ada simpul yang memiliki lebih dari dua anak?
Tyilo
Ughh. Saya mengerti sekarang. Saya pikir ada istilah kesalahpahaman di sini. Bahkan dalam contoh awal, outputnya berupa format pohon pencarian biner . Dan karunia saya juga hanya untuk pohon pencarian biner. Maaf atas kebingungan di sana.
Pengoptimal
1

APL, 125 karakter

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

Contoh:

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

Diuji di sini.

jimmy23013
sumber
Apakah ini skrip konversi juga?
Pengoptimal
@ Opptizer Dibutuhkan format input array bersarang, yang mungkin dapat digunakan sebagai pohon pencarian biner (tapi saya tidak yakin tentang kerumitannya). Jika saya harus menggunakan beberapa format yang lebih biasa ... mungkin saya akan melakukannya nanti.
jimmy23013
@Optimizer Sekarang membaca lagi pertanyaan, apakah "susunan pohon pencarian biner" berarti susunan pohon biner lengkap dalam urutan mendalam (atau yang lainnya)? Saya tidak berpikir itu sesuatu yang spesifik. Dan mencari istilah ini tidak memberikan manfaat apa pun.
jimmy23013
@ Pengoptimal Yah, itulah yang saya maksud. Tapi saya tidak berpikir itu biasanya disebut "array pohon pencarian biner", tetapi hanya "semacam penyimpanan array pohon biner". Mungkin perlu beberapa klarifikasi ... Dan saya mungkin akan memperbaiki jawaban ini beberapa hari kemudian, mungkin dalam bahasa lain ...
jimmy23013
0

Ruby, 265 byte

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

Versi @proudhaskeller, 269 byte

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

Penjelasan

Versi verbose:

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

Contoh

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

memberi:

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

(Saya belum menulis skrip konversi.)

AlexRath
sumber
tebasan Anda tidak tepat di tengah
haskeller bangga
@proudhaskeller "berputar ke arah mana pun yang Anda inginkan", saya pikir itu terlihat lebih keren seperti ini. Anda dapat mengganti s / 2 dengan (s + 1) / 2 jika Anda mau.
AlexRath
Tidak, garis miring pada baris pertama tidak tepat di tengah, pada baris ini ini bukan masalah pembulatan
bangga haskeller
@proudhaskeller Jika Anda mengganti s / 2 dengan (s + 1) / 2 mereka persis di tengah, tapi saya masih lebih suka cara ini karena itu membuat cabang paling kiri dan paling kanan terlihat bulat.
AlexRath
itu bertentangan dengan spec ...
haskeller bangga