Dalam artikel sebelumnya, saya telah mengatakan algoritma kalender traversal rekursif (traversal pohon biner pertama (urutan pertama)).
Ringkas algoritma non -resursif dari traversal pertama.
1) Masukkan tumpukan, terutama untuk memasukkan tumpukan node pertama, lalu kunjungi node ini
2) sementara
3) Anak yang tepat dari simpul IF adalah benar, transfer ke 1) Terus melintasi, jika tidak simpul saat ini akan keluar dan ditransfer ke node induk melintasi 1)
Pertama -tama lihat algoritma yang sesuai dengan ide ini:
Salin kode kode sebagai berikut:
Int PreorderTraversEnonRCursiveEx (const bitree & t, int (*VisitNode) (data telemtype))
{{
if (t == null)
{{
Kembali -1;
}
Bitnode *pbinode = t;
SQStack S;
Initstack (& s);
Push (& s, (selectype) t);
While (! IsStackedy (s))
{{
While (pbinode)
{{
VisitNode (pbinode-> data);
if (pbinode! = t)
{{
Push (& s, (selectype) pbinode);
}
pbinode = pbinode-> lChild;
}
if (pbinode == null)
{{
Pop (& s, (selemtype*) & pbinode);
}
if (pbinode-> rchild == null)
{{
Pop (& s, (selemtype*) & pbinode); // Jika tumpukan kosong saat ini, ada masalah
}
pbinode = pbinode-> rchild;
}
Kembali 0;
}
Catatan: 1) Struktur tumpukan digunakan di sini, dan Anda dapat melihat tumpukan yang disimpan dalam urutan struktur di atas
2) Saat menyimpan node di sini, yang saya simpan adalah alamat pointer, yaitu alamat node, mengubahnya menjadi penyimpanan int. Mengapa Anda berpikir tentang pointer sendiri?
Algoritma di atas sebenarnya salah! Mengapa? Di sini saya memeriksa untuk waktu yang lama. Karena jika tumpukan kosong setelah pop, tetapi masih ada pohon pohon yang tepat, itu tidak akan berlanjut. Ketika pohon anak kiri kosong, sebagai berikut: sebagai berikut:
Salin kode kode sebagai berikut:
Int PreorderTraversEnonrCursive (const bitree & t, int (*visitNode) (data telemtype))
{{
if (t == null)
{{
Kembali -1;
}
Bitnode *pbinode = t;
SQStack S;
Initstack (& s);
Push (& s, (selectype) t);
While (! IsStackedy (s))
{{
Gettop (s, (selectype*) & pbinode);
While (pbinode)
{{
VisitNode (pbinode-> data);
pbinode = pbinode-> lChild;
Push (& s, (selectype) pbinode);
}
if (pbinode == null)
{{
Pop (& s, (selemtype*) & pbinode);
}
if (! isStackedy (s))
{{
Pop (& s, (selemtype*) & pbinode);
pbinode = pbinode-> rchild;
Push (& s, (selectype) pbinode);
}
}
Kembali 0;
}
Ini adalah kasusnya. Tekan ke simpul anak yang tepat, dan kemudian tentukan apakah anak kiri pohon kanan kosong, dan lanjutkan siklus.
Ada dua limbah di sini: satu adalah mendorong ke node anak kosong untuk memasuki tumpukan, dan yang lainnya adalah sering menggunakan Gettop untuk mendapatkan elemen teratas dari tumpukan
Kembali ke sini untuk melihat algoritma yang dirancang terlebih dahulu, di mana node nol tidak ditekan ke pointer nol atau anak yang kosong, tetapi tidak dapat sepenuhnya output. NULL adalah NULL itu, sehingga tidak akan ada rasa malu yang tidak akan menampilkan simpul pohon sub -tree yang tepat, sebagai berikut: sebagai berikut:
Salin kode kode sebagai berikut:
// non -recursivity traversing binery tree
Int preordertraversenonrcursiveex (const bitree & t,
Int (*VisitNode) (data telemtype))
{{
if (t == null)
{{
Kembali -1;
}
Bitnode *pbinode = t;
SQStack S;
Initstack (& s);
Push (& s, (selectype) t);
While (! IsStackedy (s) || pbinode) // modifikasi utama adalah kalimat ini
{{
While (pbinode)
{{
VisitNode (pbinode-> data);
if (pbinode! = t)
{{
Push (& s, (selectype) pbinode);
}
pbinode = pbinode-> lChild;
}
if (pbinode == null)
{{
Pop (& s, (selemtype*) & pbinode);
}
if (pbinode-> rchild == null)
{{
Pop (& s, (selemtype*) & pbinode); // Jika tumpukan kosong saat ini, ada masalah
}
pbinode = pbinode-> rchild;
}
Kembali 0;
}
Setelah loop pertama ditambahkan, itu sudah cukup. Sebagai berikut, uji pohon biner di bagian sebelumnya:
Saat ini, data input masih 12 34 0 0 78 0 0. Hasil tes adalah sebagai berikut:
--- bitree ---
Harap masukkan data node bitree:
12
Harap masukkan data node bitree:
34
Harap masukkan data node bitree:
0
Harap masukkan data node bitree:
0
Harap masukkan data node bitree:
78
Harap masukkan data node bitree:
0
Harap masukkan data node bitree:
0
12 34 78
Ini tidak cukup untuk diuji, lihat pohon biner berikut
Pada saat ini, data input harus: 12 34 24 0 0 0 0 0 0 78 37 0 0 0. Hasil tes adalah sebagai berikut:
--- bitree ---
Harap masukkan data node bitree:
12
Harap masukkan data node bitree:
34
Harap masukkan data node bitree:
Dua Puluh Empat
Harap masukkan data node bitree:
0
Harap masukkan data node bitree:
0
Harap masukkan data node bitree:
50
Harap masukkan data node bitree:
0
Harap masukkan data node bitree:
0
Harap masukkan data node bitree:
78
Harap masukkan data node bitree:
37
Harap masukkan data node bitree:
0
Harap masukkan data node bitree:
0
Harap masukkan data node bitree:
0
12 34 24 50 78 37
Dapat dilihat dari traversal awal bahwa itu benar. , dan kemudian tambahkan untuk bergabung.