Adakah yang bisa membantu saya memahami algoritme penelusuran pohon inorder Morris berikut tanpa menggunakan tumpukan atau rekursi? Saya mencoba memahami cara kerjanya, tetapi itu hanya luput dari saya.
1. Initialize current as root
2. While current is not NULL
If current does not have left child
a. Print current’s data
b. Go to the right, i.e., current = current->right
Else
a. In current's left subtree, make current the right child of the rightmost node
b. Go to this left child, i.e., current = current->left
Saya memahami pohon dimodifikasi sedemikian rupa sehingga current node
, dibuat right child
dari max node
dalam right subtree
dan menggunakan properti ini untuk traversal inorder. Tapi di luar itu, saya tersesat.
EDIT: Menemukan kode c ++ yang menyertai ini. Saya mengalami kesulitan untuk memahami bagaimana pohon dipulihkan setelah dimodifikasi. Keajaiban terletak pada else
klausa, yang dipukul setelah daun kanan dimodifikasi. Lihat kode untuk detailnya:
/* Function to traverse binary tree without recursion and
without stack */
void MorrisTraversal(struct tNode *root)
{
struct tNode *current,*pre;
if(root == NULL)
return;
current = root;
while(current != NULL)
{
if(current->left == NULL)
{
printf(" %d ", current->data);
current = current->right;
}
else
{
/* Find the inorder predecessor of current */
pre = current->left;
while(pre->right != NULL && pre->right != current)
pre = pre->right;
/* Make current as right child of its inorder predecessor */
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}
// MAGIC OF RESTORING the Tree happens here:
/* Revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else
{
pre->right = NULL;
printf(" %d ",current->data);
current = current->right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */
}
c++
binary-tree
tree-traversal
Brainydexter.dll
sumber
sumber
pre->right = NULL;
Jawaban:
Jika saya membaca algoritme dengan benar, ini seharusnya menjadi contoh cara kerjanya:
Pertama,
X
adalah root, sehingga diinisialisasi sebagaicurrent
.X
memiliki anak kiri, sehinggaX
dibuat anak paling kanan dariX
subpohon kiri - pendahulu langsungX
dalam inorder traversal. JadiX
dibuatkan anak yang tepatB
, lalucurrent
ditetapkan keY
. Pohon itu sekarang terlihat seperti ini:(Y)
di atas mengacu padaY
dan semua anaknya, yang dihilangkan karena masalah rekursi. Bagian yang penting tetap terdaftar. Sekarang pohon memiliki link kembali ke X, traversal berlanjut ...Kemudian
A
dikeluarkan, karena tidak memiliki turunan kiri, dancurrent
dikembalikan keY
, yang merupakan turunanA
kanan pada iterasi sebelumnya. Pada iterasi berikutnya, Y memiliki kedua anak. Namun, kondisi ganda dari loop membuatnya berhenti ketika mencapai dirinya sendiri, yang merupakan indikasi bahwa subpohon kiri telah dilintasi. Jadi, ia mencetak dirinya sendiri, dan berlanjut dengan subtree kanannya, yaituB
.B
mencetak dirinya sendiri, dan kemudiancurrent
menjadiX
, yang menjalani proses pemeriksaan yang sama sepertiY
sebelumnya, juga menyadari bahwa subpohon kirinya telah dilintasi, melanjutkan denganZ
. Sisa pohon lainnya mengikuti pola yang sama.Tidak diperlukan rekursi, karena alih-alih mengandalkan penelusuran kembali melalui tumpukan, tautan kembali ke akar pohon (sub) dipindahkan ke titik di mana ia akan diakses dalam algoritme penjelajahan pohon inorder rekursif - setelah itu subtree kiri telah selesai.
sumber
Rekursif di-order traversal adalah:
(in-order(left)->key->in-order(right))
. (ini mirip dengan DFS)Ketika kita melakukan DFS, kita perlu tahu ke mana harus mundur (itulah mengapa kita biasanya menyimpan tumpukan).
Saat kita pergi melalui simpul induk yang kita perlu lacak kembali -> kita menemukan simpul yang kita perlu lacak dan memperbarui tautannya ke simpul induk.
Saat kita mundur? Ketika kita tidak bisa melangkah lebih jauh. Kapan kita tidak bisa melangkah lebih jauh? Saat tidak ada anak kiri yang hadir.
Kemana kita mundur? Pemberitahuan: kepada SUCCESSOR!
Jadi, saat kita mengikuti simpul di sepanjang jalur anak-kiri, atur pendahulu di setiap langkah untuk menunjuk ke simpul saat ini. Dengan cara ini, pendahulu akan memiliki tautan ke penerus (tautan untuk mundur).
Kami mengikuti kiri selagi kami bisa sampai kami perlu mundur. Ketika kita perlu mundur, kita mencetak simpul saat ini dan mengikuti tautan yang benar ke penggantinya.
Jika kita baru saja mundur -> kita harus mengikuti anak kanan (kita selesai dengan anak kiri).
Bagaimana cara mengetahui apakah kita baru saja mundur? Dapatkan pendahulu dari node saat ini dan periksa apakah memiliki link yang benar (ke node ini). Jika memiliki - daripada kita mengikutinya. hapus tautan untuk memulihkan pohon.
Jika tidak ada tautan kiri => kami tidak mundur dan harus melanjutkan mengikuti anak-anak kiri.
Ini kode Java saya (Maaf, ini bukan C ++)
sumber
Saya telah membuat animasi untuk algoritme di sini: https://docs.google.com/presentation/d/11GWAeUN0ckP7yjHrQkIB0WT9ZUhDBSa-WR0VsPU38fg/edit?usp=sharing
Ini semoga membantu untuk memahami. Lingkaran biru adalah kursor dan setiap slide merupakan iterasi dari loop sementara luar.
Berikut kode untuk morris traversal (saya menyalin dan memodifikasinya dari geeks untuk geeks):
sumber
print(cursor.value)
setelahpre.right = None
Saya pikir kode ini akan lebih baik untuk dipahami, cukup gunakan null untuk menghindari loop tak terbatas, tidak harus menggunakan sihir lagi. Ini dapat dengan mudah dimodifikasi untuk memesan sebelumnya.
sumber
temp.left = null
pohon akan hilang.Saya menemukan penjelasan bergambar yang sangat bagus tentang Morris Traversal .
sumber
Saya harap pseudo-code di bawah ini lebih mengungkapkan:
Mengacu pada kode C ++ dalam pertanyaan, loop sementara dalam menemukan pendahulu dalam urutan dari node saat ini. Dalam pohon biner standar, anak kanan pendahulu harus nol, sedangkan dalam versi berulir, anak kanan harus menunjuk ke simpul saat ini. Jika anak yang tepat adalah null, itu diatur ke node saat ini, yang secara efektif menciptakan threading , yang digunakan sebagai titik kembali yang seharusnya disimpan, biasanya di tumpukan. Jika anak kanan bukan nol, maka algoritme memastikan bahwa pohon asli dipulihkan, dan kemudian melanjutkan traversal di subtree kanan (dalam hal ini diketahui bahwa subtree kiri dikunjungi).
sumber
Solusi Python Kompleksitas Waktu: O (n) Kompleksitas Ruang: O (1)
Penjelasan Penjelajahan Inorder Morris yang Sangat Baik
sumber
Penjelasan PFB tentang Morris In-order Traversal.
sumber