Misalkan Anda memiliki pohon biner lengkap (yaitu masing-masing simpul internal memiliki dua keturunan yang tidak kosong). Setiap node berisi bilangan nol. Anda diberi tugas untuk menyandikan dan mendekode pohon ke / dari daftar bilangan bulat.
Pohon disimpan secara internal seperti:
struct node {
int data;
struct node *left, *right;
};
Dan Anda harus mengimplementasikan dua fungsi:
int *encode(struct node *root);
struct node *decode(int *array);
Terserah Anda bagaimana Anda menyandikan dan memecahkan kode.
Poin untuk:
- panjang penyandian minimum
- kompleksitas (idealnya linear dalam jumlah node)
- keaslian
Tidak ada poin untuk panjang kode sumber dan Anda tidak terbatas pada C.
Contoh pohon:
5
/ \
3 2
/ \
2 1
/ \
9 9
code-challenge
tree-traversal
Alexandru
sumber
sumber
int *
adalah kotak hitam untuk pengguna.Jawaban:
~ 1,03 N
Tampaknya semua jawaban sejauh ini membutuhkan setidaknya 2 * N * 32-bit untuk disimpan. (Kecuali solusi dalam bahasa yang memungkinkan nilai integer lebih panjang dari 32 bit, seperti solusi Haskell dan Ruby - tetapi itu masih akan mengambil byte tambahan untuk menyandikan kapan pun data lebih besar dari 16K.)
Berikut adalah solusi yang hanya membutuhkan N + langit-langit (N / 32) +1 penyimpanan int. Ini mendekati 1,03125 N untuk N besar, dan di bawah 1,1 N untuk semua N lebih besar dari 20.
Idenya adalah untuk menyimpan bit ekstra untuk setiap node di mana 1 adalah "hasChildren". Bit-bit ini dikemas dalam N / 32 kata di depan.
(selesaikan implementasi di sini)
sumber
Program Haskell ini mengkodekan sebuah pohon n node di n Integer. Kuncinya adalah bahwa itu mengkode data node dua kali lipat, dan kemudian menggunakan bit orde rendah untuk menunjukkan apakah ini adalah node daun, atau node interior.
Secara teknis,
Parser
monad di sini adalah over-kill, karena hanya ada satu parser yang dibuat,decoder
dan saya bisa meletakkan logika rantai parser langsung di sana. Tapi cara dekoder ini sangat jelas, danParser
meskipun ukurannya kecil, adalah kerangka kerja penguraian sederhana yang masuk akal.Menjalankan ini membuat Anda:
sumber
Dalam C
Encode:
Decode:
Utama:
Catatan. Setiap node dikodekan sebagai dua bilangan bulat (ditambah satu int untuk hitungan node).
Jadi pohon yang disediakan mengkodekan seperti ini:
sumber
Di Ruby, dengan penyandian yang sama dengan @MtnViewMark :
Biaya adalah satu integer per node (
data << 1 | has_childs
):sumber
Diberi pohon biner dengan
n
node, ini mengkodekannya dalam daftar2n + 1
bilangan bulat. Kedua algoritma encoding dan decoding memilikiO(n)
kompleksitas.Saya menggunakan 0 integer sebagai penanda sentinel saat menyandikan, menunjukkan saat saya membuka rekursi. Kemudian ketika saya decoding, saya meletakkan node pohon yang saya buat di stack (macam) dan menggunakan 0s dalam daftar untuk melacak di mana menambahkan node berikutnya. Saya belum mencoba, tapi saya cukup yakin decoding akan pecah jika pohon itu tidak lengkap.
Disimpan ini
encode.c
saat dikompilasi dan dieksekusi. Program ini menggunakan contoh pohon yang Anda berikan, dan saya telah berhasil mengujinya pada beberapa orang lain.sumber
Kode saya mengkodekan pohon dalam travers preorder, masing-masing daun dalam dua int (datanya diikuti oleh 0) dan setiap node internal dalam satu int (datanya diikuti oleh anak kirinya, lalu kanan). Untuk pohon biner lengkap (seperti yang Anda definisikan) dengan n node, n harus ganjil, dan ada (n + 1) / 2 daun dan (n-1) / 2 node internal, jadi itu 3n / 2 + 1 / 2 bilangan bulat untuk penyandian.
peringatan: belum diuji, ketikkan saja.
sumber
Inilah usaha saya. Ini menyimpan pohon dalam array ukuran 2 ** kedalaman + 1. Ini digunakan
a[0]
untuk menahan ukuran, dana[size]
untuk menahan indeks "simpul kosong" pertama yang ditemuinya dalam traversal kedalaman-pertama. (Node kosong adalah tempat di mana seorang anak akan disimpan jika orang tuanya memilikinya). Setiap node kosong menyimpan indeks dari node kosong berikutnya yang akan ditemui.Skema ini menghindari pemesanan bit untuk menandai anak-anak presense, sehingga setiap node dapat menggunakan rentang integer penuh. Ini juga memungkinkan pohon tidak seimbang - orangtua hanya dapat memiliki satu anak.
keluaran:
Encoder:
Dekoder:
(terima kasih @daniel sobral untuk memperbaiki pemformatan)
sumber
Scala:
Ini adalah pendekatan yang menggunakan sintaks usang, tetapi mengkompilasi tanpa kesalahan di Scala 2.9.1. Ini menghasilkan Pohon dan menerjemahkan setiap Pohon yang dikodekan ke Array yang sama seperti yang digunakan untuk pengkodean. Mungkin saya entah bagaimana menyingkirkan peringatan yang sudah usang hari ini.Wow - itu yang sederhana. Gagasan pertama bekerja segera.
sumber