Bebaskan Pohon Biner

13

Jadi sebelum Anda membaca beberapa konsep dasar ilmu komputer.

  1. Pohon biner adalah struktur yang dialokasikan secara dinamis (biasanya digunakan untuk penyimpanan yang dipesan).
  2. 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.
  3. Dalam bahasa kuno, manajemen memori memerlukan manajemen memori manual.
    • Manual: Berarti Anda harus melakukannya sendiri.
  4. 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:

  1. Kompleksitas terbaik.
  2. Tie Break 1: Pertama Dikirimkan
  3. Tie Break 2: Jumlah karakter paling sedikit.
Martin York
sumber

Jawaban:

7

Tampaknya sangat dekat dengan O (n) bagi saya:

Ini melakukan langkah pertama kedalaman di pohon, dan menggunakan ->leftpointer node yang dilalui untuk melacak induknya.

struct Node * node = root;
struct Node * up = NULL;

while (node != NULL) {
    if (node->left != NULL) {
        struct Node * left = node->left;
        node->left = up;
        up = node;
        node = left;
    } else if (node->right != NULL) {
        struct Node * right = node->right;
        node->left = up;
        node->right = NULL;
        up = node;
        node = right;
    } else {
        if (up == NULL) {
            free(node);
            node = NULL;
        }
        while (up != NULL) {
            free(node);
            if (up->right != NULL) {
                node = up->right;
                up->right = NULL;
                break;
            } else {
                node = up;
                up = up->left;
            }
        }
    }
}
Arnaud Le Blanc
sumber
+1 Tambahkan centang untuk satu-satunya jawaban. Ini sedikit lebih kompleks daripada solusi yang saya sajikan di bawah ini tetapi sangat bagus.
Martin York
4

C99, 94, O (n)

Sunting: semua orang tampaknya merujuk struct Nodeseolah Node-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.

void f(Node*n){for(Node*q;n;n=q)(q=n->left)?n->left=q->right,q->right=n:(q=n->right,free(n));}

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

 1
/ \
2 3
 \
 4

Algoritma akan memutasi pointer sehingga pohon akan

2
 \
 1
/ \
4 3

sekarang kita dapat menghapus simpul paling atas dengan mudah.

haskeller bangga
sumber
Saya tidak menggunakan typedef karena milik saya di C ++ (Anda lupa perbedaan kecil antara bahasa). Saya telah memperbarui pertanyaan sehingga berfungsi sama di C dan C ++.
Martin York
@LokiAstari Saya sebenarnya tidak tahu c ++, dan saya baru mulai belajar C baru-baru ini. Tapi saya cukup tahu untuk menjawab ini :-)
haskeller bangga
1
Saya akan melakukan +1 untuk saat ini. Tapi saya masih belum mengetahui bagaimana cara kerjanya sehingga saya akan kembali setelah kalkun. :-)
Martin York
@LokiAstari pada dasarnya menggunakan fakta bahwa C menggabungkan ekspresi dan pernyataan bersama untuk melakukan sesuatu hanya dengan menggunakan ekspresi
haskeller bangga
1

C / C ++ / Objective-C 126 karakter (termasuk baris tambahan yang diperlukan)

#define b(t)(t->left||t->right)
void f(Node*r){while(r&&b(r)){Node**p=&r,*c=b(r);while(c)p=&c,c=b(c);free(*p);*p=0;}free(r);}

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:

void freeTree (Node * root) {
    while (root && (root->left || root->right)) {
        Node ** prev = &root;
        Node * curr = root->left || root->right;
        while (curr != 0) {
            prev = &curr;
            curr = curr->left || curr->right;
        }
        free(*prev);
        *prev = 0;
    }
    free(root);
}
Thomas Eding
sumber
Sayangnya itu tidak akan berhasil. Anda tidak mengatur penunjuk ke daun ke NULL sebelum membebaskannya. Dengan demikian Anda akan terus-menerus membebaskan simpul daun yang sama dan tidak pernah sampai ke titik di mana Anda membebaskan pohon.
Martin York
@LokiAstari: Terima kasih telah memperhatikan bug. Itu harus diperbaiki sekarang (walaupun saya belum menguji kodenya).
Thomas Eding
1

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.

void freeNode(Node* t)
{
    if (t == NULL)
    {   return;
    }

    // Points at the bottom left node.
    // Any right nodes are added to the bottom left as we go down
    // this progressively flattens the tree into a list as we go.    
    Node* bottomLeft    = findBottomLeft(t);


    while(t != NULL)
    {
        // Technically we don't need the if (it works fine without)
        // But it makes the code easier to reason about with it here.
        if (t->right != NULL)
        {
            bottomLeft->left = t->right;
            bottomLeft = findBottomLeft(bottomLeft);
        }
        // Now just free the curent node
        Node*   old = t;
        t = t->left;
        free(old);
    }
}

Node* findBottomLeft(Node* t)
{
    while(t->left != NULL)
    {
        t = t->left;
    }
    return t;
}

Versi Golf

void f(Node*t){Node*o,*l=t;for(;t;free(o)){for(;l->left;l=l->left);l->left=t->right;o=t;t=t->left;}}

Golf Diperluas

void f(Node* t)
{
        Node*o,*l    = t;

        for(;t;free(o))
        {
            for(;l->left;l = l->left);
            l->left = t->right;
            o = t;
            t = t->left;
        }
}
Martin York
sumber
0

C, 150 byte

f(T*r,int s){T*t[s];t[0]=r;T**f=&t[0],**e=&t[0];while(f<=e){if(*f){if((*f)->left){*++e=(*f)->left;}if((*f)->right){*++e=(*f)->right;}}free(*f);f++;}}

Cobalah Di JDoodle

T. Salim
sumber