Jadi sebelum Anda membaca beberapa konsep dasar ilmu komputer.
- Pohon biner adalah struktur yang dialokasikan secara dinamis (biasanya digunakan untuk penyimpanan yang dipesan).
- Karena sifatnya traversal pohon biner biasanya bersifat rekursif;
Ini karena linear traversal (via loop) tidak alami ketika ada dua jalan looping.- Rekursif: Ini berarti fungsi yang memanggil dirinya sendiri.
- Dalam bahasa kuno, manajemen memori memerlukan manajemen memori manual.
- Manual: Berarti Anda harus melakukannya sendiri.
- Ketika Anda melakukan manajemen memori manual, Anda perlu meminta sistem dasar untuk membebaskan setiap anggota pohon.
- Gratis: pulihkan memori ke poo global sehingga dapat digunakan kembali dan Anda tidak kehabisan memori.
- Membebaskan: ini dilakukan dengan memanggil fungsi
free()
dan meneruskannya pointer yang ingin Anda pulihkan. - Pointer: Ini seperti tongkat virtual. Pada akhirnya adalah memori. Ketika Anda meminta memori, Anda diberi pointer (tongkat virtual) yang memiliki memori. Setelah selesai, Anda mengembalikan pointer (tongkat virtual).
Solusi rekursif:
freeTree(Node* node)
{
freeTree(node->left);
freeTree(node->right);
free(node);
}
Masalahnya kemudian adalah rekursi berarti Anda berulang kali memanggil fungsi yang sama. Ini menumbuhkan tumpukan. Menumbuhkan tumpukan menggunakan lebih banyak memori. Alasan Anda membebaskan pohon adalah Anda ingin memori kembali menggunakan lebih banyak memori kontraproduktif (bahkan jika Anda mendapatkan kedua bit memori kembali).
Akhirnya pertanyaan:
SO masalah berpusat pada mengubah versi rekursif di atas menjadi solusi linear (sehingga Anda tidak perlu menggunakan memori).
Berikan tipe simpul
typedef struct Node Node;
struct Node
{
Node* left;
Node* right;
};
Tulis fungsi untuk membebaskan pohon dari simpul-simpul ini.
Pembatasan:
- Tidak dapat menggunakan rekursi (bahkan secara tidak langsung)
Tidak dapat mengalokasikan ruang dinamis apa pun untuk pelacakan.
Perhatikan ada solusi O (n)
Pemenang:
- Kompleksitas terbaik.
- Tie Break 1: Pertama Dikirimkan
- Tie Break 2: Jumlah karakter paling sedikit.
sumber
C99, 94, O (n)
Sunting: semua orang tampaknya merujuk
struct Node
seolahNode
-olahtypedef
ed itu, jadi saya juga melakukannya.ini sebenarnya golf C pertama saya. banyak segfault.
Bagaimanapun, ini membutuhkan C99 karena menggunakan deklarasi di dalam pernyataan pertama for loop.
bahkan tidak menggunakan
#define
!Algoritma ini berfungsi dengan mentransformasikan pohon sehingga simpul atas tidak memiliki anak kiri, dan kemudian menghapusnya dan beralih ke anak kanannya.
misalnya, jika kita mulai dengan pohon
Algoritma akan memutasi pointer sehingga pohon akan
sekarang kita dapat menghapus simpul paling atas dengan mudah.
sumber
C / C ++ / Objective-C 126 karakter (termasuk baris tambahan yang diperlukan)
Tidak berjalan dalam waktu O (n). Tetapi OP tidak memerlukannya, jadi inilah solusi O (n 2 ) saya.
Algoritma: Berjalan ke daun dari akar. Lepaskan. Ulangi sampai tidak ada daun. Lepaskan root.
Tidak Disatukan:
sumber
c ++ 99 O (n)
Hal di sini loop sangat bagus untuk merantai sepanjang daftar tetapi tidak naik turun hierarki. user300 berhasil (saya terkesan) tetapi kode ini sulit dibaca.
Solusinya adalah mengubah pohon menjadi daftar.
Triknya adalah melakukannya bersamaan dengan menghapus node.
Versi Golf
Golf Diperluas
sumber
C, 150 byte
Cobalah Di JDoodle
sumber