Bisakah pohon dilintasi tanpa rekursi, tumpukan, atau antrian, dan hanya beberapa petunjuk?

Setengah dekade yang lalu saya duduk di kelas struktur data di mana profesor menawarkan kredit tambahan jika ada yang bisa melintasi pohon tanpa menggunakan rekursi, tumpukan, antrian, dll (atau struktur data serupa lainnya) dan hanya beberapa petunjuk. Saya datang dengan apa yang saya pikir merupakan jawaban yang jelas untuk pertanyaan yang akhirnya diterima oleh profesor. Saya duduk di kelas matematika diskrit dengan profesor lain di departemen yang sama - dan dia menegaskan bahwa tidak mungkin untuk melintasi pohon tanpa rekursi, tumpukan, antrian, dll., Dan solusi saya tidak valid.

Jadi, apakah mungkin, atau tidak mungkin? Mengapa atau mengapa tidak?

Sunting: Untuk menambahkan beberapa klarifikasi, saya menerapkan ini pada pohon biner yang memiliki tiga elemen - data yang disimpan di setiap node dan pointer ke dua anak. Solusi saya dapat diperluas ke pohon n-ary dengan hanya beberapa perubahan.

Guru struktur data saya tidak memberikan hambatan apa pun terhadap mutasi pohon, dan memang saya kemudian mengetahui bahwa solusinya sendiri adalah dengan menggunakan pointer anak untuk menunjuk kembali pohon dalam perjalanan turun. Profesor matematika diskrit saya mengatakan mutasi pohon berarti bahwa itu bukan lagi pohon sesuai dengan definisi matematika pohon, definisinya juga akan menghalangi setiap petunjuk kepada orang tua - yang akan cocok dengan kasus di mana saya menyelesaikannya di atas.

Banyak penelitian di bidang ini telah kubah, termotivasi oleh metode "murah" melintasi pohon dan struktur daftar umum dalam konteks pengumpulan sampah.

Pohon biner berulir adalah representasi yang disesuaikan dari pohon biner di mana beberapa nil-pointer digunakan untuk menautkan ke simpul penerus dalam pohon. Informasi tambahan ini dapat digunakan untuk melintasi pohon tanpa tumpukan. Namun, bit ekstra per node diperlukan untuk membedakan utas dari child-pointer. Wikipedia: Tree_traversal

Sejauh yang saya tahu pohon biner diimplementasikan menggunakan pointer dalam mode biasa (pointer kiri dan kanan per node) dapat dilalui menggunakan metode thread, dalam metode yang dikaitkan dengan Morris . NIL-pointer untuk sementara digunakan kembali untuk merutekan path kembali ke root. Bagian yang cerdik adalah bahwa selama traversal seseorang dapat membedakan tepi asli dari tautan-utas sementara, menggunakan cara mereka membentuk siklus di pohon).

Bagian yang baik: tidak ada struktur data tambahan. Bagian buruk: sedikit curang, tumpukan berada di dalam pohon dengan cara yang cerdas. Sangat pintar.

Bukti tumpukan tersembunyi ditunjukkan dalam P. Mateti dan R. Manghirmalani: Algoritma Traversal Pohon Morris, DOI: 10.1016 / 0167-6423 (88) 90063-9 yang Dipertimbangkan

JM Morris: Melintasi pohon biner secara sederhana dan murah. IPL 9 (1979) 197-200 DOI: 10.1016 / 0020-0190 (79) 90068-1

Lalu ada juga Lindstrom pemindaian . Metode ini "memutar" tiga pointer yang terlibat dalam setiap node (orang tua dan dua anak). Jika Anda ingin melakukan algoritma pre-order atau post-order yang layak, Anda memerlukan bit tambahan per node. Jika Anda hanya ingin mengunjungi semua node (tiga kali, tetapi Anda tidak pernah tahu kunjungan mana yang Anda lakukan) maka itu dapat dilakukan tanpa bit.

G. Lindstrom: Memindai struktur daftar tanpa tumpukan atau tag tag. IPL 2 (1973) 47-51. DOI: 10.1016 / 0020-0190 (73) 90012-4

Mungkin cara yang paling mudah adalah dengan metode Robson . Di sini tumpukan yang diperlukan untuk algoritma klasik di-threaded melalui daun.

JM Robson: Algoritma yang ditingkatkan untuk melintasi pohon biner tanpa tumpukan tambahan IPL 1 (1973) 149-152. 10.1016 / 0020-0190 (73) 90018-5

IPL = Surat Pemrosesan Informasi

$v$

Solusi saya adalah traversal bredth-first menggunakan nested for-loop untuk brute force pohon. Ini tidak efisien dengan cara apa pun, dan memang struktur data rekursif seperti pohon memohon untuk traversal rekursif, tetapi pertanyaannya bukan apakah pohon dapat dilintasi secara efisien, adalah apakah itu mungkin.

Pseudocode:
root = pointer root 
depth = integer 0
finished = bool false
//If we n-ary tree also track how many children have been found 
//on the node with the most children for the purposes of this psuedocode 
//we'll assume a binary tree and insert a magic number of 2 so that we 
//can use bitwise operators instead of integer division 
while(!finished)
    ++depth
    treePosition = pointer root
    finished = true;
    for i := 0..2**depth
        for j := 0..depth
            if (i & j) //bitwise operator explained below
                // if right child doesn't exist break the loop
                treePosition = treePosition.rightChild
            else
                // if left child doesn't exist break the loop
                treePosition = treePosition.leftChild
        if j has any children
            finished = false
            do anything else you want when visiting the node

Untuk beberapa level pertama akan terlihat seperti ini, seperti yang Anda lihat, operator bitwise dalam pseudocode hanya memutuskan belokan kiri atau kanan pada pohon biner:

2**1       0               1
2**2   00      01      10      11
2**3 000 001 010 011 100 101 110 111

Untuk n-ary, Anda akan mengambil i% (maxChildren ** j) / j untuk menentukan jalur mana yang akan diambil antara 0 dan maxChildren.

Pada setiap node di n-ary Anda juga perlu memeriksa untuk melihat apakah jumlah anak lebih besar dari maxChildren dan memperbaruinya dengan tepat.