Jelaskan Kombinatorik dari Pohon biner

Kelompok dari sepasang simpul dalam sebuah pohon dapat digambarkan sebagai pasangan dari aksara dalam tanda kurung. Oleh sebab itu, (a,b) menunjukan pohon biner di mana sub pohon kirinya adalah a sedangkan sub pohon kanannya adalah b. Benang dari tanda kurung yang seimbang mungkin dapat digunakan untuk menunjukan pohon biner pada umumnya. Himpunan dari semua benang yang mungkin yang terdiri dari keseluruhan tanda kurung yang seimbang dikenal sebagal bahasa Dyck.

Diketahui n+1 simpul, jumlah seluruh jalan di mana simpul tersebut dapat disusun kedalam sebuah pohon biner dengan sebuah bilangan Catalan . Sebagai contoh,  adalah pernyataan bahwa (ab)c dan a(bc) merupakan dua pohon biner yang mungkin, yang memiliki 3 simpul.

Kemampuan untuk menggambarkan pohon biner sebagai benang dari simbol-simbol dan tanda kurung secara tidak langsung menyatakan bahwa pohon biner dapat mewakili elemen dari magma. Sebaliknya, himpunan dari semua pohon biner yang mungkin, bersama-sama dengan operasi natural memasangkan pohon dari satu ke yang lain, dari sebuah magma, magma bebas.

Memberikan benang yang menggambarkan sebuah pohon biner, operator untuk mendapatkan sub pohon kiri dan kanan kadang-kadang mengacu sebagai CAR dan CDR.

Metode untuk menyimpan pohon biner

Pohon biner dapat dikonstruksi dari bahasa pemrograman primitif dalam berbagai cara. Dalam bahasa yang menggunakan records dan referensi, pohon biner secara khas dikonstruksi dengan mengambil sebuah struktur simpul pohon yang memuat beberapa data dan referensi ke anak kiri dan anak kanan. Kadang-kadang itu juga memuat sebuah referensi ke ayahnya yang khas. Jika sebuah simpul mempunyai kurang dari dua anak, beberapa penunjuk anak dapat diatur kedalam nilai nol khusus, atau ke sebuah simpul sentinel.

Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai((i-1)/2) (asumsikan akarnya memiliki indeks kosong). Metode ini menguntungkan dari banyak penyimpanan yang rapat dan memiliki referensi lokal yang lebih baik, tersitimewa selama sebuah preorder traversal. Bagaimanapun juga, ini terlalu mahal untuk perkembangannya dan boros tempat sebanding dengan 2h - n untuk sebuah pohon dengan tinggi h dengan nsimpul.

Dalam bahasa dengan tagged union seperti ML, sebuah simpul pohon sering kali sebuah tagged union dari dua jenis simpul, di mana yang satu merupakan data dari 3-tupel, anak kiri, dan anak kanan, dan yang lain di mana sebuah daun, yang tidak memuat data dan fungsi seperti nilai nol dalam bahasa dengan penunjuk (pointers)