Menulis Program Terpendek untuk Menghitung Tinggi Pohon Biner

18

Ketinggian pohon biner adalah jarak dari simpul akar ke simpul anak yang paling jauh dari akar.

Di bawah ini adalah contohnya:

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

Tinggi pohon biner: 4

Definisi Pohon Biner

Pohon adalah objek yang berisi nilai integer yang ditandatangani dan dua pohon lain atau pointer ke sana.

Struktur struct pohon biner terlihat seperti berikut:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;

Tantangan:

Memasukkan

Akar pohon biner

Keluaran

Angka yang mewakili ketinggian pohon biner

Dengan asumsi Anda diberi root dari pohon biner sebagai input, tulis program terpendek yang menghitung ketinggian pohon biner dan kembalikan tingginya. Program dengan jumlah byte terkecil (spasi akuntansi) menang.

T. Salim
sumber
4
Apa yang dilakukan bahasa tanpa petunjuk?
Jonathan Allan
4
... tapi kemudian objek pohon saya hanya bisa memiliki properti, katakanlah h. Mungkin lebih baik untuk mendefinisikan struktur spesifik yang dibuat hanya dari daftar untuk tujuan tantangan ini.
Jonathan Allan
11
@ T.Salim Di masa mendatang, silakan pertimbangkan untuk memposting di kotak pasir terlebih dahulu.
wizzwizz4
1
Jadi, apakah representasi yang valid adalah daftar panjang 3 di [root_value, left_node, right_node]mana masing-masing left_nodedan right_nodejuga pohon biner dapat diterima? Itu akan sepele dalam banyak bahasa, tetapi mungkin menyenangkan dalam beberapa bahasa lain.
Jonathan Allan
3
Bisakah Anda mengedit pertanyaan untuk memasukkan apa yang merupakan struktur biner yang valid? Mungkin definisi suka a tree is an object that contains a value and either two other trees or pointers to them. Definisi yang termasuk bahasa tanpa objek juga akan bagus.
Jo King

Jawaban:

11

Jelly , 3 byte

ŒḊ’

Tautan monadik yang menerima daftar yang mewakili pohon:, di [root_value, left_tree, right_tree]mana masing-masing left_treedan right_treemerupakan struktur yang sama (kosong jika perlu), yang menghasilkan ketinggian.

Cobalah online!

Bagaimana?

Sepele di Jelly:

ŒḊ’ - Link: list, as described above
ŒḊ  - depth
  ’ - decremented (since leaves are `[value, [], []]`)
Jonathan Allan
sumber
Jonathon Allen, itu adalah bahasa yang menarik yang Anda gunakan. Sebagai pendatang baru, dapatkah Anda memberikan tautan atau rujukan situs web yang mengajari orang cara menggunakan Jelly?
T. Salim
4
Klik tautan di tajuk - ini adalah bahasa golf yang dikembangkan oleh Dennis , salah satu moderator situs.
Jonathan Allan
2
Saya bertanya-tanya, seberapa kontroversialkah merepresentasikan daun sebagai xganti [x, [], []]...
Erik the Outgolfer
@EriktheOutgolfer Untuk menjaga dengan sifat "pointer" dan "struct" dari pertanyaan saya pikir setiap node harus dari bentuk yang sama.
Jonathan Allan
10

Python 2 ,  35  33 byte

Terima kasih kepada Arnauld karena telah melihat pengawasan dan penghematan 4.

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

Fungsi rekursif menerima daftar yang mewakili pohon:, di [root_value, left_tree, right_tree]mana masing-masing left_treedan right_treestruktur yang sama (kosong jika perlu), yang mengembalikan ketinggian.

Cobalah online!

Perhatikan bahwa []akan kembali False, tetapi dengan Python False==0.

Jonathan Allan
sumber
Orang yang sama diizinkan untuk memberikan dua jawaban berbeda untuk pertanyaan yang sama?
T. Salim
6
Ya, tentu saja, golf adalah kompetisi di tingkat bahasa. Bahkan entri kedua dalam bahasa yang sama terkadang dapat diterima, jika pendekatannya sangat berbeda.
Jonathan Allan
@Arnauld Tebak begitu (saya berasumsi non-integer mungkin hadir untuk beberapa alasan)
Jonathan Allan
6

Haskell, 33 byte

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

Menggunakan jenis pohon kustom data T = L | N T T Int, yang setara dengan Haskell dari struct C yang diberikan dalam tantangan.

Cobalah online!

nimi
sumber
6

Perl 6 , 25 byte

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

Input adalah daftar 3-elemen (l, r, v). Pohon kosong adalah daftar kosong.

Cobalah online!

Penjelasan

{                       }  # 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

Solusi lama, 30 byte

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

Cobalah online!

nwellnhof
sumber
The &?BLOCKtrick menarik tapi itu beberapa byte lebih pendek untuk menetapkan blok untuk $!
Jo King
@JoKing saya tidak tahu. Menyimpan solusi tantangan dalam situasi global yang fluktuatif $!atau $/terasa seperti curang bagi saya.
nwellnhof
(Ab) menggunakan variabel seperti $! dan $ / adalah latihan standar untuk bermain golf P6.
user0721090601
6

05AB1E , 11 7 5 byte

Δ€`}N

-4 byte terima kasih kepada @ExpiredData .
-2 byte terima kasih kepada @Grimy .

Format input mirip dengan jawaban Jelly: daftar yang merepresentasikan pohon:, di [root_value, left_tree, right_tree]mana masing-masing left_treedan right_treemerupakan struktur yang serupa (opsional kosong). Yaitu [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]mewakili pohon dari deskripsi tantangan.

Cobalah secara online atau verifikasi beberapa kasus uji lagi .

Penjelasan:

Δ     # 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)

Perhatikan bahwa meskipun 05AB1E berbasis 0, loop perubahan Δmenyebabkan indeks output menjadi benar, karena memerlukan iterasi tambahan untuk memeriksa tidak ada perubahan lagi.

Kevin Cruijssen
sumber
1
7 byte?
Data Kedaluwarsa
@ExpiredData Ah, tentu saja .. Terima kasih! :)
Kevin Cruijssen
1
5 byte
Grimmy
@ Grimy Saya pikir menggunakan indeks di luar loop hanya bekerja di kode warisan ..: S Terima kasih!
Kevin Cruijssen
5

JavaScript (ES6),  35  33 byte

Struktur input: [[left_node], [right_node], value]

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

Cobalah online!

Berkomentar

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
sumber
Sepertinya Anda dapat menyimpan byte dengan a&&-~.
Shaggy
1
@ Shaggy Itu akan menyebabkan perbandingan dengan undefined .
Arnauld
4

C, 43 byte

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

Struktur pohon biner adalah sebagai berikut:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;
T. Salim
sumber
2
55 byte Cobalah online! Beberapa trik golf khusus C ada di sini!
ErikF
1
@ErikF Or 45 byte
Arnauld
2
43 byte
nwellnhof
3
Jika kiriman Anda bergantung pada bendera, dapatkah Anda menambahkannya ke tajuk kiriman Anda?
Jo King
1
Bangunan di @nwellnhof 42 byte
ceilingcat
4

JavaScript (Node.js) , 32 byte

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

Cobalah online!

Menggunakan nama flatsebagai ganti flattenatau smooshmerupakan ide bagus untuk kode golf.

Menggunakan []untuk simpul nol di pohon, dan [left, right, value]untuk simpul. valuedi sini adalah bilangan bulat.

tsh
sumber
3

Haskell, 28 byte

Menggunakan definisi data berikut:

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

Tingginya adalah:

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

Skema, 72 Bytes

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

Versi Lebih Mudah Dibaca:

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

Menggunakan daftar formulir (data, kiri, kanan) untuk mewakili pohon. Misalnya

   1
  / \
  2  3
 /\
 4 5

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

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

Cobalah secara Online!

Zachary Cotton
sumber
2

R , 51 byte

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

Cobalah online!

  • Input: daftar bersarang dalam format:list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

  • Algoritma: Iteratif meratakan pohon dengan satu tingkat sampai menjadi vektor datar: jumlah iterasi sesuai dengan kedalaman maks.

Terinspirasi oleh solusi @KevinCruijssen


Alternatif rekursif:

R , 64 byte

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

Cobalah online!

Mendefinisikan ulang fungsi / operator '~' sehingga dapat menghitung kedalaman maksimum pohon yang disimpan dalam struktur daftar.

Struktur daftar pohon dalam format: list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

  • -2 Terima kasih kepada @Giuseppe
menggali semua
sumber
mengapa Anda menggunakan d=1dan kemudian d-1pada akhirnya? Tidak bisakah Anda memulai 0?
Giuseppe
Saya juga beralih >ke ~ sini sehingga kasus uji lebih mudah untuk dimasukkan
Giuseppe
@ Giuseppe: tentu saja ... Saya melewatkan 🤦‍♂️ yang jelas
digEmAll
1

K (ngn / k) , 4 byte

Larutan:

#,/\

Cobalah online!

Penjelasan:

Saya pikir saya mungkin telah melewatkan intinya.

Merepresentasikan pohon sebagai daftar 3-item (parent-node; left-child; right-child), contohnya dapat direpresentasikan sebagai

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

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

Jadi solusinya adalah dengan meratakan iteratif, dan hitung iterasinya:

#,/\ / the solution
   \ / iterate
 ,/  / flatten
#    / count
streetster
sumber
0

Arang , 29 byte

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Memodifikasi sementara pohon selama pemrosesan. Penjelasan:

⊞θ⁰

Tekan nol ke simpul akar.

⊞υθ

Dorong simpul root ke daftar semua node.

Fυ«

Lakukan pencarian pertama dari pohon.

≔⊕⊟ιθ

Dapatkan kedalaman node ini.

FΦι∧κλ

Ulangi simpul anak.

⊞υ⊞Oκθ

Beri tahu simpul anak kedalaman orangtuanya dan dorong ke daftar semua simpul.

»Iθ

Setelah semua node telah dilintasi, cetak kedalaman node terakhir. Karena traversal pertama kali lebarnya, ini akan menjadi ketinggian pohon.

Neil
sumber
0

Stax , 5 byte

▐▌µ╡⌂

Jalankan dan debug itu

Stax tidak memiliki pointer atau nilai null, jadi saya mewakili input seperti [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]] . Mungkin itu keuntungan yang tidak adil, tapi itulah yang paling dekat yang bisa saya dapatkan.

Dibongkar, tidak diseret, dan dikomentari, kode ini terlihat seperti ini.

        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

Jalankan yang ini

rekursif
sumber
0

Kotlin, 45 byte

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

Dengan asumsi kelas berikut didefinisikan

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

Cobalah online

Aso Leo
sumber
0

Julia, 27 byte

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

Dengan struct berikut mewakili pohon biner:

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

cadalah tuple yang mewakili node kiri dan kanan dan tuple kosong ()digunakan untuk memberi sinyal tidak adanya node.

pengguna3263164
sumber
0

Kotlin , 42 byte

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

Cobalah online!

Dimana

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