Bagaimana cara melintasi pohon tanpa menggunakan rekursi?

19

Saya memiliki pohon simpul memori yang sangat besar dan perlu melintasi pohon. Melewati nilai yang dikembalikan dari setiap simpul anak ke simpul induknya. Ini harus dilakukan sampai semua node memiliki data bubble hingga ke root node.

Traversal bekerja seperti ini.

private Data Execute(Node pNode)
{
    Data[] values = new Data[pNode.Children.Count];
    for(int i=0; i < pNode.Children.Count; i++)
    {
        values[i] = Execute(pNode.Children[i]);  // recursive
    }
    return pNode.Process(values);
}

public void Start(Node pRoot)
{
    Data result = Execute(pRoot);
}

Ini berfungsi dengan baik, tapi saya khawatir bahwa tumpukan panggilan membatasi ukuran pohon simpul.

Bagaimana kode dapat ditulis ulang sehingga tidak ada panggilan rekursif untuk Executedilakukan?

Reactgular
sumber
8
Anda harus memelihara tumpukan Anda sendiri untuk melacak node, atau mengubah bentuk pohon. Lihat stackoverflow.com/q/5496464 dan stackoverflow.com/q/4581576
Robert Harvey
1
Saya juga menemukan banyak bantuan di Pencarian Google ini , khususnya Morris Traversal .
Robert Harvey
@ RobertTarvey terima kasih, Rob, saya tidak yakin ketentuan apa yang akan berlaku.
Reactgular
2
Anda mungkin akan terkejut dengan persyaratan memori jika Anda melakukan perhitungan. Sebagai contoh, pohon biner teranode yang seimbang sempurna hanya membutuhkan tumpukan 40 entri.
Karl Bielefeldt
@KarlBielefeldt Itu menganggap pohon itu sangat seimbang. Terkadang Anda perlu membuat model pohon yang tidak seimbang, dan dalam hal ini sangat mudah untuk meniup stack.
Servy

Jawaban:

27

Berikut adalah implementasi pohon traversal tujuan umum yang tidak menggunakan rekursi:

public static IEnumerable<T> Traverse<T>(T item, Func<T, IEnumerable<T>> childSelector)
{
    var stack = new Stack<T>();
    stack.Push(item);
    while (stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach (var child in childSelector(next))
            stack.Push(child);
    }
}

Dalam kasus Anda, Anda dapat menyebutnya seperti ini:

IEnumerable<Node> allNodes = Traverse(pRoot, node => node.Children);

Gunakan pencarian Queuebukan Stackuntuk bernafas terlebih dahulu, bukan kedalaman terlebih dahulu. Gunakan PriorityQueueuntuk pencarian pertama yang terbaik.

Melayani
sumber
Apakah saya benar dalam berpikir ini hanya akan meratakan pohon menjadi koleksi?
Reactgular
1
@MathewFoscarini Ya, itulah tujuannya. Tentu saja, itu tidak perlu diwujudkan menjadi koleksi yang sebenarnya. Itu hanya urutan. Anda dapat beralih di atasnya untuk mengalirkan data, tanpa perlu menarik seluruh data yang ditetapkan ke dalam memori.
Servy
Saya tidak berpikir itu menyelesaikan masalah.
Reactgular
4
Dia tidak hanya melintasi grafik yang melakukan operasi independen seperti pencarian, dia mengumpulkan data dari node anak. Meratakan pohon akan menghancurkan informasi struktur yang diperlukan untuk melakukan agregasi.
Karl Bielefeldt
1
FYI Saya pikir ini adalah jawaban yang benar yang dicari kebanyakan orang oleh Google. +1
Anders Arpi
4

Jika Anda memiliki perkiraan untuk kedalaman pohon Anda sebelumnya, mungkin itu cukup untuk kasus Anda untuk mengadaptasi ukuran tumpukan? Di C # sejak versi 2.0 ini dimungkinkan setiap kali Anda memulai utas baru, lihat di sini:

http://www.atalasoft.com/cs/blogs/rickm/archive/2008/04/22/increasing-the-size-of-your-stack-net-memory-management-part-3.aspx

Dengan begitu Anda dapat menyimpan kode rekursif Anda, tanpa harus mengimplementasikan sesuatu yang lebih kompleks. Tentu saja, membuat solusi non-rekursif dengan tumpukan Anda sendiri mungkin lebih hemat waktu dan memori, tetapi saya cukup yakin kodenya tidak akan sesederhana seperti saat ini.

Doc Brown
sumber
Saya baru saja membuat tes cepat. Di mesin saya, saya bisa membuat 14000 panggilan rekursif sebelum mencapai stackoverflow. Jika pohon seimbang, hanya 32 panggilan yang diperlukan untuk menyimpan 4 miliar node. Jika setiap node adalah 1 byte (yang tidak akan terjadi) Diperlukan 4 GB ram untuk menyimpan pohon seimbang dengan tinggi 32.
Esben Skov Pedersen
Saya kami menggunakan semua 14000 panggilan di stack. Pohon akan memakan waktu 2,6x10 ^ 4214 byte jika setiap node satu byte (yang tidak akan terjadi)
Esben Skov Pedersen
-3

Anda tidak dapat melintasi struktur data dalam bentuk pohon tanpa menggunakan rekursi - jika Anda tidak menggunakan frame stack dan panggilan fungsi yang disediakan oleh bahasa Anda, pada dasarnya Anda harus memprogram stack dan panggilan fungsi Anda sendiri, dan itu adalah tidak mungkin Anda berhasil melakukannya dalam bahasa dengan cara yang lebih efisien daripada penulis kompiler lakukan pada mesin yang menjalankan program Anda.

Karena itu, menghindari rekursi karena takut berlari ke batas sumber daya biasanya salah arah. Yang pasti, optimasi sumber daya prematur selalu salah arah, tetapi dalam kasus ini kemungkinan bahwa bahkan jika Anda mengukur dan mengonfirmasi bahwa penggunaan memori adalah hambatan, Anda mungkin tidak akan dapat meningkatkannya tanpa jatuh ke tingkat penulis kompiler.

Kilian Foth
sumber
2
Ini benar-benar salah. Sangat mungkin untuk melintasi pohon tanpa menggunakan rekursi. Bahkan tidak sulit . Anda juga dapat melakukannya dengan lebih efisien, sangat sepele, karena Anda hanya dapat memasukkan sebanyak mungkin informasi dalam tumpukan eksplisit yang Anda yakin perlu untuk traversal spesifik Anda, sedangkan menggunakan rekursi Anda pada akhirnya menyimpan lebih banyak informasi daripada yang sebenarnya Anda butuhkan di banyak kasus.
Servy
2
Kontroversi ini muncul sesekali di sini. Beberapa poster menganggap menggulung tumpukan Anda sendiri bukan untuk rekursi, sementara yang lain menunjukkan bahwa mereka hanya melakukan hal yang sama secara eksplisit bahwa runtime akan melakukannya secara implisit. Tidak ada gunanya berdebat tentang definisi seperti ini.
Kilian Foth
Bagaimana Anda mendefinisikan rekursi? Saya akan mendefinisikannya sebagai fungsi yang memanggil dirinya sendiri dalam definisi sendiri. Anda pasti dapat melintasi pohon tanpa pernah melakukan itu, seperti yang telah saya tunjukkan dalam jawaban saya.
Servy
2
Apakah saya jahat karena menikmati tindakan mengklik downvote pada seseorang dengan skor rep yang tinggi? Ini adalah kesenangan yang langka di situs web ini.
Reactgular
2
Ayo @Mat, itu barang anak-anak. Anda mungkin tidak setuju, seperti jika Anda takut membom pohon yang terlalu dalam, itu adalah kekhawatiran yang masuk akal. Anda bisa bilang begitu.
Mike Dunlavey