Untuk setiap simpul dalam pohon biner seimbang, perbedaan maksimum dalam ketinggian subtree anak kiri dan subtree anak kanan paling banyak 1.
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
Berikut ini adalah pohon biner dan laporan tentang apakah mereka seimbang atau tidak:
Pohon di atas tidak seimbang .
Pohon di atas seimbang .
Tuliskan program sesingkat mungkin yang menerima sebagai input root dari pohon biner dan mengembalikan nilai falsey jika pohon itu tidak seimbang dan nilai yang benar jika pohon itu seimbang.
Memasukkan
Akar pohon biner. Ini mungkin dalam bentuk referensi ke objek root atau bahkan daftar yang merupakan representasi yang valid dari pohon biner.
Keluaran
Mengembalikan nilai kebenaran: Jika pohon seimbang
Mengembalikan nilai falsey: Jika pohon tidak seimbang.
Definisi Pohon Biner
Sebuah pohon adalah objek yang berisi nilai dan dua pohon lain atau pointer ke sana.
Struktur pohon biner terlihat seperti berikut:
typedef struct T
{
struct T *l;
struct T *r;
int v;
}T;
Jika menggunakan representasi daftar untuk pohon biner, itu mungkin terlihat seperti berikut ini:
[root_value, left_node, right_node]
4
, apakah pohon yang tersisa seimbang?Jawaban:
Jelly , 11 byte
Cobalah online!
Pohon kosong diwakili oleh
[]
.sumber
Prolog (SWI) , 49 byte
Cobalah online!
Merupakan pohon sebagai
Value/Left_Child/Right_Child
, dengan pohon kosong menjadi atome
. Menentukan+/2
, yang menghasilkan melalui keberhasilan atau kegagalan, dengan variabel tidak terikat (atau yang sudah sama dengan tinggi pohon) di sebelah kiri dan pohon di sebelah kanan - jika argumen ketinggian tidak dapat diterima, tambahkan 9 byte untuk didefinisikan-T:-_+T.
.sumber
_/
dapat diambil untuk -2 bytes.)Bahasa Wolfram (Mathematica) , 50 byte
Gunakan
Null
untuk null,value[left, right]
untuk node. Sebagai contoh, pohon berikut ini ditulis sebagai2[7[2[Null, Null], 6[5[Null, Null], 11[Null, Null]]], 5[Null, 9[4[Null, Null], Null]]]
.Cobalah online!
sumber
Python 3.8 (pra-rilis) ,
133125 byteCobalah online!
Mengambil pohon dalam format "daftar": Node
[value, left, right]
denganleft
danright
menjadi node.Meminta fungsi
h
.Pengembalian
0
atauFalse
untuk pohon yang tidak seimbang. Pengembalian1
atauTrue
untuk pohon seimbang.Tidak Terkumpul:
-10: Logika terbalik untuk menghilangkan
not
sJika mengambil argumen di tengah panggilan diperbolehkan, ini bisa disingkat menjadi (115 byte)
dengan
_
menjadi pohon untuk diperiksa.sumber
JavaScript (Node.js) , 49 byte
Cobalah online!
-9 byte oleh Arnauld.
JavaScript, 58 byte
Cobalah online!
Gunakan
[]
untuk null, dan[left, right, value]
untuk node.sumber
JavaScript, 162 byte
Cobalah online!
Format input adalah objek
Penjelasan
Melakukan pencarian luas pertama menemukan kedalaman node pertama yang hilang satu atau lebih cabang.
Melanjutkan pencarian pertama yang lebarnya, mengembalikan nol jika ada elemen dua lebih dalam dari kedalaman simpul pertama yang hilang cabang.
Jika tidak ada simpul yang ditemukan, kembalikan 1
sumber
4
.Julia, 56 byte
Dengan struct berikut mewakili pohon biner:
c
adalah tuple yang mewakili node kiri dan kanan dan tuple kosong()
digunakan untuk memberi sinyal tidak adanya node.Nilai Falsey adalah
NaN
, bilangan bulat apa pun adalah benar.sumber
≢
, menurut penghitung byte bawaan TIO . Bagaimanapun, selamat datang di CG&CC!Kotlin , 67 byte
Dimana
Cobalah online!
sumber
C, 117 byte
Implementasi struktur adalah sebagai berikut:
Coba ini di JDoodle
sumber
<2
pemeriksaan terakhir sebagai gantinyaPython 2 ,
999694 byteCobalah online!
3 byte dari Jo King .
Mengambil input sebagai: node kosong
[]
, dan node lainnya[<value>, <leftNode>, <rightNode>]
. Output0/1
untuk False / True.sumber