Membina struktur pokok rekursif dengan tatasusunan bersekutu php

Untuk membina data rata ke dalam struktur pokok rekursif, anda perlu menggunakan array bersekutu untuk memetakan nod dengan cekap; 1. Melalui data untuk membuat array bersekutu dengan ID sebagai kunci, dan setiap nod memulakan anak kosong; 2. Traverse lagi, tambahkan rujukan nod semasa ke array kanak -kanak nod induk melalui parent_id, dan letakkan nod akar ke dalam array pokok; 3. Akhirnya, struktur pokok bersarang diperolehi, dan kerumitan masa kaedah ini hampir dengan O (n), yang lebih baik daripada skema rekursif, dan sesuai untuk senario hierarki seperti klasifikasi dan komen.

Apabila bekerja dengan data hierarki dalam kategori seperti PHP, komen, atau struktur organisasi -anda sering perlu membina struktur pokok rekursif dari data rata. Arus bersekutu di PHP adalah sempurna untuk tugas ini kerana mereka membolehkan anda memetakan ID ke nod dan sarang kanak -kanak yang cekap di bawah ibu bapa mereka.

Berikut adalah cara menukar senarai rata (contohnya, dari pangkalan data) ke dalam pokok bersarang menggunakan logik rekursif dan array yang berkaitan.

Memahami data input

Anggapkan anda mempunyai pelbagai item, masing -masing dengan id , parent_id , dan beberapa data :

 $ flatData = [
    ['id' => 1, 'parent_id' => null, 'name' => 'elektronik'],
    ['id' => 2, 'parent_id' => 1, 'name' => 'telefon bimbit'],
    ['id' => 3, 'parent_id' => 1, 'name' => 'komputer riba'],
    ['id' => 4, 'parent_id' => 2, 'nama' => 'telefon pintar'],
    ['id' => 5, 'parent_id' => 4, 'name' => 'android'],
    ['id' => 6, 'parent_id' => 4, 'name' => 'ios'],
];

Matlamat kami adalah untuk menjadikannya menjadi pokok bersarang di mana setiap nod mengandungi anak -anaknya.

Langkah 1: Item Peta oleh ID

Pertama, bina array yang berkaitan di mana setiap id menunjuk ke data penuhnya, dan tambahkan array children kosong kepada setiap:

 $ item = [];
foreach ($ flatData sebagai $ item) {
    $ item ['kanak -kanak'] = [];
    $ item [$ item ['id']] = $ item;
}

Ini memberi kita akses cepat ke mana -mana nod oleh ID.

Langkah 2: Lampirkan anak kepada ibu bapa

Gelung melalui item dan lampirkan setiap item ke ibu bapa menggunakan parent_id . Jika parent_id wujud, tolak item ke dalam array children ibu bapa. Item akar (dengan ibu bapa null ) akan kekal peringkat tertinggi.

 $ pokok = [];

foreach ($ item sebagai $ id => & $ item) {
    $ parentid = $ item ['parent_id'];
    jika ($ parentid === null) {
        $ pokok [] = & $ item;
    } else {
        jika (isset ($ item [$ parentId])) {
            $ item [$ parentid] ['kanak -kanak'] [] = & $ item;
        }
    }
}
unset ($ item); // Rujukan Break

Kami menggunakan rujukan ( & ) untuk memastikan perubahan menyebarkan dengan betul.

Langkah 3: struktur pokok yang dihasilkan

Sekarang $tree mengandungi nod akar, masing -masing dengan kanak -kanak bersarang rekursif:

 print_r ($ pokok);

Output (dipermudahkan):

 Array
(
    [0] => Array
        (
            [id] => 1
            [parent_id] => 
            [Nama] => Elektronik
            [kanak -kanak] => array
                (
                    [0] => Array
                        (
                            [id] => 2
                            [parent_id] => 1
                            [Nama] => Telefon bimbit
                            [kanak -kanak] => array
                                (
                                    [0] => Array
                                        (
                                            [id] => 4
                                            [parent_id] => 2
                                            [nama] => telefon pintar
                                            [kanak -kanak] => array
                                                (
                                                    [0] => Array
                                                        (
                                                            [id] => 5
                                                            [parent_id] => 4
                                                            [nama] => Android
                                                            [kanak -kanak] => array ()
                                                        )
                                                    [1] => array
                                                        (
                                                            [id] => 6
                                                            [parent_id] => 4
                                                            [nama] => iOS
                                                            [kanak -kanak] => array ()
                                                        )
                                                )
                                        )
                                )
                        )
                    [1] => array
                        (
                            [id] => 3
                            [parent_id] => 1
                            [nama] => komputer riba
                            [kanak -kanak] => array ()
                        )
                )
        )
)

Pilihan: Fungsi rekursif untuk membina pokok (alternatif)

Anda juga boleh menggunakan rekursi untuk membina pokok itu, walaupun ia kurang efisien untuk dataset besar:

 Fungsi BuildTree ($ item, $ parentId = null) {
    $ cawangan = [];
    foreach ($ item sebagai $ item) {
        jika ($ item ['parent_id'] == $ parentid) {
            $ kanak -kanak = BuildTree ($ item, $ item ['id']);
            jika ($ kanak -kanak) {
                $ item ['kanak -kanak'] = $ kanak -kanak;
            }
            $ cawangan [] = $ item;
        }
    }
    kembali $ cawangan;
}

$ pokok = BuildTree ($ flatData);

Versi ini mengelakkan rujukan tetapi mempunyai kerumitan masa O (n²) dalam kes yang paling teruk. Kaedah pemetaan array yang berkaitan lebih berskala.

Mata utama

• Gunakan tatasusunan yang berkaitan untuk memetakan id => node untuk o (1) penampilan.
• Bina pokok secara berulang dengan melampirkan anak -anak kepada ibu bapa melalui rujukan.
• Elakkan pengimbasan berulang dengan memanfaatkan hubungan ibu bapa dan kanak-kanak.
• Berhati -hati dengan rujukan dalam PHP -selalu unset selepas gelung dengan rujukan.

Corak ini digunakan secara meluas dalam sistem CMS, kategori e-dagang, benang komen, dan struktur direktori fail.

Pada asasnya, ia tidak kompleks -tetapi menggunakan array yang berkaitan dengan bijak menjadikannya cepat dan bersih.

Atas ialah kandungan terperinci Membina struktur pokok rekursif dengan tatasusunan bersekutu php. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!