Imprimer un arbre binaire

18

Inspiré d'une question récente sur SO ...

Écrivez une fonction pour imprimer un arbre binaire au format suivant:

   3
 /   \
1     5
 \   / \
  2 4   6
  1. La sortie doit être composée d'une ligne de nœuds, suivie d'une ligne de /et de \caractères indiquant les relations, suivie d'une ligne de nœuds, etc.
  2. Vous pouvez supposer que tous les nœuds sont représentables comme un seul caractère.
  3. Les nœuds adjacents au niveau le plus bas doivent être séparés par au moins un espace, les nœuds plus haut doivent être séparés le cas échéant.
  4. Les nœuds avec deux enfants doivent être placés précisément au milieu de leurs enfants directs.
  5. Les barres obliques de relation doivent être à mi-chemin entre le parent et l'enfant approprié (arrondissez comme vous le souhaitez).

Contribution:

L'entrée sera fournie comme argument à votre fonction. Je ne spécifierai pas la structure exacte de l'arbre, mais il doit être utilisable comme un arbre binaire réel. Aucun "arbre n'est représenté dans mon programme comme des chaînes ressemblant par coïncidence à la sortie attendue".

Vous pouvez imprimer sur un flux de sortie ou renvoyer une chaîne contenant la sortie, votre choix.

Points pour le code le plus court, mais je préférerais de loin une solution longue fonctionnant pleinement qu'une courte fonctionnant à 90%.


Mise à jour pour la prime:

Pour la prime, je (Optimizer) fais de légers changements:

  • L'entrée peut provenir de STDIN, ARGV ou d'un argument de fonction.
  • La sortie doit être sur STDOUT (ou console.logpour JS)
  • Vous pouvez supposer que l'entrée est sous forme de tableau, par exemple. [1,2,3]ou[1 2 3]

Mise à jour 2 - L'arbre binaire doit en fait être un arbre de recherche binaire. Comme je ne l'ai pas mentionné initialement, je vais permettre aux utilisateurs de traiter la conversion d'un tableau normal en un tableau d'arbre de recherche binaire comme un programme distinct et le nombre d'octets final ne sera que pour que le programme prenne le tableau en argument et l'imprime comme un arbre binaire.

Anon.
la source
Faut-il utiliser plusieurs barres obliques de relation étaient appropriées? Doit-on utiliser le nombre minimum de barres obliques? Faut-il distinguer entre avoir un seul enfant gauche et un seul enfant droit? Serait-il bien d'avoir des espaces de tête dans chaque ligne de sortie?
Que faisons-nous si l'arbre n'est pas complet (2 ^ n-1 nœuds pour certains n)? Certains nœuds (lesquels?) N'ont qu'un seul enfant. Mais si nous sommes autorisés à avoir des nœuds avec un seul enfant, l'arbre dégénéré est facile à faire (1-2-3-4-5-6 vers le bas et vers la droite, par exemple).
Keith Randall
Comment le dessinez-vous pour les grands nombres? Par exemple30000,1000,499999
Mohsen

Réponses:

9

Fortran 77-1085 caractères

      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

L'arbre est représenté dans le tableau d'entrée tde la manière habituelle, racine à 1, racine-> gauche à 2, racine-> droite à 3 racine-> gauche-> gauche à 4 ...

La sortie doit tenir dans un terminal conventionnel jusqu'à 5 niveaux de profondeur.

J'utilise exactement une barre oblique entre chaque paire de nœuds, ce qui semble assez idiot près du sommet une fois qu'il y a quatre niveaux ou plus. J'ai autorisé jusqu'à trois nœuds de chiffres.

Programme complet avec commentaires et échafaudage de lancement:

      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

Sortie avec entrée équivalente à l'exemple:

$ ./a.out 
         3             
     /      \      
     1       5     
      \    /  \  
       2   4   7 
dmckee
la source
AIDE pourquoi cette langue?
tomsmeding
9
Parce qu'il est si mal adapté au golf.
dmckee
5

CJam, 100 99 octets

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

L'entrée doit être une liste de caractères, sans aucun caractère de contrôle ascii. Les nœuds vides sont indiqués par un espace. Il doit également s'agir d'un arbre binaire parfait avec exactement 2 n -1 nœuds.

Exemple:

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

Ou utilisez simplement des chaînes:

"63714 902 5  8 "

Production:

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

Explication

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

Script de conversion

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

Il accepte des caractères ou des nombres à un chiffre.

Exemples (tous sont les mêmes):

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

Production:

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

C'est une construction d'arbre cartésienne simple.

jimmy23013
la source
Vous pouvez simplement ajouter deux octets supplémentaires et effectuer l'entrée du script de conversion sous forme d'entiers appropriés au lieu de caractères :)
Optimizer
@Optimizer Modifié pour prendre en charge les deux. Je pense que les caractères ont plus de sens car ils ne prennent en charge que les noms de nœud avec un seul caractère. Il y a beaucoup plus de caractères que de nombres à un chiffre.
jimmy23013
2

Python 2, 411 octets

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

Remarque: le premier niveau d'indentation est de 1 espace, le second d'un onglet.

Appelez favec une liste de chaînes ou de caractères à un caractère None, par ex. f(['1',None,'3']). La liste ne peut pas être vide.

Cela devrait obéir aux règles de la prime.

Script de conversion:

Convertit et tableau au format utilisé par l'imprimante d'arbre binaire. Exemple:

$ 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

Exemples:

Pour les exécuter, vous devez nommer le fichier principal bt.pyet le fichier convertisseur 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
la source
Vous ne créez pas réellement l'arbre binaire. Il suffit d'imprimer le tableau sous forme d'arbre binaire. La sortie du ['1','2','3','4','5','6','7','8','9']tableau n'est pas ce que vous avez montré. Il doit avoir 3comme enfant droit 2dont un enfant droit 1est un élément racine.
Optimizer
@Optimizer De la question: "L'entrée sera fournie comme argument à votre fonction. Je ne spécifierai pas la structure exacte de l'arbre, mais elle doit être utilisable comme un arbre binaire réel." Je ne vois pas de définition spécifique du format de tableau utilisé.
Tyilo
À l'origine, la question concerne l'impression d'un arbre binaire . Vos sorties ne sont pas des arbres binaires. Le format du tableau n'a rien à voir avec cela.
Optimizer
@Optimizer comment ne sont-ils pas des arbres binaires? De Wikipedia: un arbre binaire est une structure de données arborescente dans laquelle chaque nœud a au plus deux enfants. L'un des nœuds a-t-il plus de deux enfants?
Tyilo
Ughh. Je vois maintenant. Je pense qu'il y a ici un malentendu. Même dans les exemples initiaux, la sortie est au format d' arbre de recherche binaire . Et ma prime est également pour un arbre de recherche binaire uniquement. Désolé pour la confusion là-bas.
Optimizer
1

APL, 125 caractères

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

Exemple:

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

Testé ici.

jimmy23013
la source
Est-ce aussi le script de conversion?
Optimizer
@Optimizer Il prend le format d'entrée de tableau imbriqué, qui peut probablement être utilisé comme arbre de recherche binaire (mais je ne suis pas sûr de la complexité). Si je dois utiliser des formats plus habituels ... je le ferai peut-être plus tard.
jimmy23013
@Optimizer En lisant à nouveau la question, "tableau d'arbre de recherche binaire" signifie-t-il le tableau d'un arbre binaire complet dans l'ordre de profondeur (ou autre chose)? Je ne pensais pas que c'était quelque chose de spécifique. Et la recherche de ce terme n'a rien donné d'utile.
jimmy23013
@Optimizer Eh bien, c'est exactement ce que je voulais dire. Mais je ne pense pas qu'il soit généralement appelé "tableau d'arbre de recherche binaire", mais seulement "une sorte de stockage de tableau d'arbres binaires". Il faudra probablement quelques éclaircissements ... Et je corrigerai probablement cette réponse quelques jours plus tard, peut-être dans une autre langue ...
jimmy23013
0

Rubis, 265 octets

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

La version @proudhaskeller, 269 octets

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

Explication

La version verbeuse:

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

Exemple

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

donne:

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

(Je n'ai pas encore écrit le script de conversion.)

AlexRath
la source
vos barres obliques ne sont pas exactement au milieu
fier haskeller
@proudhaskeller "autour de la façon que vous voulez", je pensais que ça avait l'air plus cool de cette façon. Vous pouvez remplacer s / 2 par (s + 1) / 2 si vous le souhaitez.
AlexRath
Non, les barres obliques dans la première rangée ne sont pas exactement au milieu, dans cette rangée, ce n'est pas une question d'arrondi
fier haskeller
@proudhaskeller Si vous remplacez s / 2 par (s + 1) / 2, ils sont exactement au milieu, mais je préfère toujours cette façon car cela fait tourner les branches les plus à gauche et à droite.
AlexRath
c'est contre la spécification ...
fier haskeller