Ecrire le programme le plus court pour calculer la hauteur d'un arbre binaire

18

La hauteur d'un arbre binaire est la distance entre le nœud racine et le nœud enfant le plus éloigné de la racine.

Voici un exemple:

           2 <-- root: Height 1
          / \
         7   5 <-- Height 2
        / \   \
       2   6   9 <-- Height 3
          / \  /
         5  11 4 <-- Height 4 

Hauteur de l'arbre binaire: 4

Définition d'un arbre binaire

Un arbre est un objet qui contient une valeur entière signée et deux autres arbres ou pointeurs vers eux.

La structure de la structure d'arbre binaire ressemble à ceci:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;

Le défi:

Contribution

La racine d'un arbre binaire

Production

Le nombre qui représente la hauteur d'un arbre binaire

En supposant que la racine d'un arbre binaire vous soit donnée en entrée, écrivez le programme le plus court qui calcule la hauteur d'un arbre binaire et renvoie la hauteur. Le programme avec le moins d'octets (espaces blancs de comptabilité) gagne.

T. Salim
la source
4
Que prennent les langues sans pointeurs?
Jonathan Allan
4
... mais alors mon objet arbre pourrait juste avoir une propriété, disons h. Il serait peut-être préférable de définir une structure spécifique constituée uniquement de listes aux fins de ce défi.
Jonathan Allan
11
@ T.Salim À l'avenir, pensez d'abord à publier dans le bac à sable .
wizzwizz4
1
Alors, est une représentation valide une liste de longueur 3 [root_value, left_node, right_node]où chacun left_nodeet right_nodesont aussi des arbres binaires acceptables? Ce sera trivial dans de nombreuses langues, mais pourrait être amusant dans d'autres.
Jonathan Allan
3
Pouvez-vous modifier la question pour inclure ce qui constitue une structure binaire valide? Peut-être une définition comme a tree is an object that contains a value and either two other trees or pointers to them. Une définition qui inclut les langages sans objets serait également bien aussi.
Jo King

Réponses:

11

Gelée , 3 octets

ŒḊ’

Un lien monadique acceptant une liste représentant l'arbre:, [root_value, left_tree, right_tree]où chacune left_treeet right_treesont des structures similaires (vides si besoin est), ce qui donne la hauteur.

Essayez-le en ligne!

Comment?

Assez trivial dans Jelly:

ŒḊ’ - Link: list, as described above
ŒḊ  - depth
  ’ - decremented (since leaves are `[value, [], []]`)
Jonathan Allan
la source
Jonathon Allen, c'est un langage intéressant que vous utilisez. En tant que nouveau venu, pouvez-vous fournir un lien ou une référence de site Web qui explique aux gens comment utiliser Jelly?
T. Salim
4
Cliquez sur le lien dans l'en-tête - c'est un langage de golf développé par Dennis , l'un des modérateurs du site.
Jonathan Allan
2
Je me demande à quel point il serait controversé de représenter une feuille au xlieu de [x, [], []]...
Erik the Outgolfer
@EriktheOutgolfer Pour conserver la nature "pointeur" et "struct" de la question, je pense que chaque nœud devrait être de la même forme.
Jonathan Allan
10

Python 2 ,  35  33 octets

Merci à Arnauld d'avoir remarqué un oubli et d'économiser 4.

f=lambda a:a>[]and-~max(map(f,a))

Une fonction récursive acceptant une liste représentant l'arbre:, [root_value, left_tree, right_tree]où chacune left_treeet right_treesont des structures similaires (vides si besoin est), qui renvoie la hauteur.

Essayez-le en ligne!

Notez que []cela reviendra False, mais en Python False==0.

Jonathan Allan
la source
La même personne est autorisée à donner deux réponses différentes à la même question?
T. Salim
6
Oui, bien sûr, le golf est une compétition au niveau linguistique. Même une deuxième entrée dans la même langue est parfois acceptable, si l'approche est très différente.
Jonathan Allan
@Arnauld Guess so (j'avais supposé que des non-entiers pouvaient être présents pour une raison quelconque)
Jonathan Allan
6

Haskell, 33 octets

h L=0 
h(N l r _)=1+max(h l)(h r)

Utilisation du type d'arbre personnalisé data T = L | N T T Int, qui est l'équivalent Haskell de la structure C donnée dans le défi.

Essayez-le en ligne!

nimi
la source
6

Perl 6 , 25 octets

{($_,{.[*;*]}...*eqv*)-2}

L'entrée est une liste à 3 éléments (l, r, v). L'arbre vide est la liste vide.

Essayez-le en ligne!

Explication

{                       }  # Anonymous block
    ,        ...  # Sequence constructor
  $_  # Start with input
     {.[*;*]}  # Compute next element by flattening one level
               # Sadly *[*;*] doesn't work for some reason
                *eqv*  # Until elements doesn't change
 (                   )-2  # Size of sequence minus 2

Ancienne solution, 30 octets

{+$_&&1+max map &?BLOCK,.[^2]}

Essayez-le en ligne!

nwellnhof
la source
L' &?BLOCKastuce est intéressante mais c'est deux octets de moins pour affecter le bloc à $!
Jo King
@JoKing je ne sais pas. Stocker la solution du défi dans un monde volatil comme $!ou $/j'ai l'impression de tricher.
nwellnhof
(Ab) en utilisant des variables comme $! et $ / est une pratique assez courante pour le golf P6.
user0721090601
6

05AB1E , 11 7 5 octets

Δ€`}N

-4 octets grâce à @ExpiredData .
-2 octets grâce à @Grimy .

Le format d'entrée est similaire à la réponse Jelly: une liste représentant l'arbre:, [root_value, left_tree, right_tree]où chacune left_treeet right_treesont des structures similaires (éventuellement vide). Ie [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]représente l'arbre de la description du défi.

Essayez-le en ligne ou vérifiez quelques cas de test supplémentaires .

Explication:

Δ     # Loop until the (implicit) input-list no longer changes:
  €`  #  Flatten the list one level
}N    # After the loop: push the 0-based index of the loop we just finished
      # (which is output implicitly as result)

Notez que bien que 05AB1E soit basé sur 0, la boucle de modifications Δentraîne la correction de l'index de sortie, car il a besoin d'une itération supplémentaire pour vérifier qu'il ne change plus.

Kevin Cruijssen
la source
1
7 octets?
Données expirées
@ExpiredData Ah, bien sûr .. Merci! :)
Kevin Cruijssen
1
5 octets
Grimmy
@Grimy Je pensais que l'utilisation de l'index en dehors d'une boucle ne fonctionnait que dans le code hérité ..: S Merci!
Kevin Cruijssen
5

JavaScript (ES6),  35  33 octets

Structure d'entrée: [[left_node], [right_node], value]

f=([a,b])=>a?1+f(f(a)>f(b)?a:b):0

Essayez-le en ligne!

Commenté

f =                       // f is a recursive function taking
([a, b]) =>               // a node of the tree split into
                          // a[] = left child, b[] = right child (the value is ignored)
  a ?                     // if a[] is defined:
    1 +                   //   increment the final result for this branch
    f(                    //   and add:
      f(a) > f(b) ? a : b //     f(a) if f(a) > f(b) or f(b) otherwise
    )                     //
  :                       // else:
    0                     //   stop recursion and return 0
Arnauld
la source
On dirait que vous pouvez enregistrer un octet avec a&&-~.
Shaggy
1
@Shaggy Cela conduirait à des comparaisons avec undefined .
Arnauld
4

C, 43 octets

h(T*r){r=r?1+(int)fmax(h(r->l),h(r->r)):0;}

La structure de l'arbre binaire est la suivante:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;
T. Salim
la source
2
55 octets Essayez-le en ligne! Quelques astuces de golf spécifiques à C sont ici!
ErikF
1
@ErikF Or 45 octets
Arnauld
2
43 octets
nwellnhof
3
Si votre soumission repose sur des indicateurs, pouvez-vous les ajouter à l'en-tête de votre soumission?
Jo King
1
S'appuyant sur @nwellnhof 42 octets
plafond du
4

JavaScript (Node.js) , 32 octets

f=a=>/,,/.test(a)&&f(a.flat())+1

Essayez-le en ligne!

Utiliser le nom flatau lieu de flattenou smooshest une excellente idée pour le golf de code.

Utilisation []de noeud nul dans l'arborescence et [left, right, value]de noeuds. valuevoici un entier.

tsh
la source
3

Haskell, 28 octets

En utilisant la définition de données suivante:

data T a = (:&) a [T a]

La hauteur est:

h(_:&x)=foldr(max.succ.h)0 x
Michael Klein
la source
2

Schéma, 72 octets

(define(f h)(if(null? h)0(+ 1(max(f(car(cdr h)))(f(car(cdr(cdr h))))))))

Version plus lisible:

(define (f h)
   (if (null? h)
      0
      (+ 1 
         (max
             (f (car (cdr h)))
             (f (car (cdr (cdr h))))
         )
      )
   )
)

Utilisation de listes du formulaire (données, gauche, droite) pour représenter un arbre. Par exemple

   1
  / \
  2  3
 /\
 4 5

is represented as: (1 (2 (4 () ()) (5 () ())) (3 () ())

(1
   (2
      (4 () ())
```   (5 () ())
   (3 () ())
)

Essayez-le en ligne!

Coton Zachary
la source
2

R , 51 octets

function(L){while(is.list(L<-unlist(L,F)))T=T+1;+T}

Essayez-le en ligne!

  • Entrée: une liste imbriquée au format:list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

  • Algorithme: aplatit de façon itérative l'arbre d'un niveau jusqu'à ce qu'il devienne un vecteur plat: le nombre d'itérations correspond à la profondeur maximale.

Inspiré par solution @KevinCruijssen


Alternative récursive:

R , 64 octets

`~`=function(L,d=0)'if'(is.list(L),max(L[[2]]~d+1,L[[3]]~d+1),d)

Essayez-le en ligne!

Redéfinit la fonction / l'opérateur '~' ce qui lui permet de calculer la profondeur maximale d'un arbre stocké dans une structure de liste.

La structure de liste d'un arbre est au format: list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

  • -2 grâce à @Giuseppe
digEmAll
la source
pourquoi utilisez-vous d=1et puis d-1à la fin? Tu ne pourrais pas commencer 0?
Giuseppe
Aussi je suis passé >à ~ ici pour que les cas de test sont plus faciles à l' entrée
Giuseppe
@Giuseppe: bien sûr ... je manquais l'évidence 🤦‍♂️
digEmAll
1

K (ngn / k) , 4 octets

Solution:

#,/\

Essayez-le en ligne!

Explication:

Je pense que j'ai peut-être manqué le point.

Représentant un arbre en tant que liste à 3 éléments (nœud parent; enfant gauche; enfant droit), l'exemple peut être représenté comme

(2;
  (7;
    (,2);
    (6;
      (,5);
      (,11)
    )
  );
  (5;
    ();
    (9;
      (,4);
      ()
    )
  )
)

ou: (2;(7;(,2);(6;(,5);(,11)));(5;();(9;(,4);()))).

La solution consiste donc à aplatir itérativement et à compter les itérations:

#,/\ / the solution
   \ / iterate
 ,/  / flatten
#    / count
streetster
la source
0

Fusain , 29 octets

⊞θ⁰⊞υθFυ«≔⊕⊟ιθFΦι∧κλ⊞υ⊞Oκθ»Iθ

Essayez-le en ligne! Le lien est vers la version détaillée du code. Modifie temporairement l'arborescence pendant le traitement. Explication:

⊞θ⁰

Poussez zéro vers le nœud racine.

⊞υθ

Poussez le nœud racine dans la liste de tous les nœuds.

Fυ«

Effectuez une recherche en premier dans l'arborescence.

≔⊕⊟ιθ

Obtenez la profondeur de ce nœud.

FΦι∧κλ

Faites une boucle sur tous les nœuds enfants.

⊞υ⊞Oκθ

Indiquez au nœud enfant la profondeur de son parent et placez-le dans la liste de tous les nœuds.

»Iθ

Une fois tous les nœuds traversés, imprimez la profondeur du dernier nœud. Étant donné que la traversée était la largeur en premier, ce sera la hauteur de l'arbre.

Neil
la source
0

Stax , 5 octets

▐▌µ╡⌂

Exécuter et déboguer

Stax n'a ni pointeurs ni valeurs nulles, donc je représente l'entrée comme [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]. C'est peut-être un avantage injuste, mais c'était le plus près possible.

Décompressé, non golfé et commenté, le code ressemble à ceci.

        The input starts on top of the input stack
Z       Tuck a zero underneath the top value in the stack.  Both values end up on the main stack.
D       Drop the first element from array
F       For each remaining element (the leaves) run the rest of the program
  G^    Recursively call the entire program, then increment
  T     Get maximum of the two numbers now ow the stack

Exécutez celui-ci

récursif
la source
0

Kotlin, 45 octets

val Tree.h:Int get()=1+maxOf(l?.h?:0,r?.h?:0)

En supposant que la classe suivante est définie

class Tree(var v: Int, var l: Tree? = null, var r: Tree? = null)

Essayez-le en ligne

Aso Leo
la source
0

Julia, 27 octets

f(t)=t≢()&&maximum(f,t.c)+1

Avec la structure suivante représentant l'arbre binaire:

struct Tree
    c::NTuple{2,Union{Tree,Tuple{}}}
    v::Int
end

cest un tuple représentant les nœuds gauche et droit et le tuple vide ()est utilisé pour signaler l'absence d'un nœud.

user3263164
la source
0

Kotlin , 42 octets

fun N.c():Int=maxOf(l?.c()?:0,r?.c()?:0)+1

Essayez-le en ligne!

data class N(val l: N? = null, val r: N? = null, val v: Int = 0)
Brojowski
la source