DFS Dalam Susunan, Pra-Susunan dan Pasca-Susunan
Laksanakan ketiga-tiga lintasan DFS secara rekursif dan lelaran dengan tindanan eksplisit, sambil menerangkan kegunaan setiap susunan.
DFS Dalam Susunan, Pra-Susunan dan Pasca-Susunan ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Tiga Susunan Lintasan DFS
DFS pada pepohon binari melawati nod dalam salah satu daripada tiga susunan berdasarkan masa akar diproses berbanding anak-anaknya. Praurutan: akar → kiri → kanan. Dalamurutan: kiri → akar → kanan. Pascaurutan: kiri → kanan → akar. Nama-nama ini menunjukkan kedudukan akar dalam jujukan. Memahami ketiga-tiganya penting kerana masalah yang berbeza memerlukan susunan yang berbeza.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build: 1 -> left=2(left=4,right=5), right=3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# pre: 1 2 4 5 3
# in: 4 2 5 1 3
# post: 4 5 2 3 1
print('Tree built successfully')Lintasan Praurutan Rekursif
Dalam praurutan, nod semasa diproses sebelum subpepohonnya. Susunan ini menyerupai cara semula jadi membaca pepohon dari atas ke bawah dan digunakan untuk menyalin pepohon, menyirikan pepohon serta menilai ungkapan awalan. Pelaksanaan rekursifnya sangat ringkas, tetapi membina timbunan panggilan dengan kedalaman O(h), dengan h ialah ketinggian pepohon.
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
# More memory-efficient with an accumulator:
def preorder_v2(root, result=None):
if result is None:
result = []
if not root:
return result
result.append(root.val) # PROCESS ROOT FIRST
preorder_v2(root.left, result)
preorder_v2(root.right, result)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_v2(root)) # [1, 2, 4, 5, 3]Lintasan Dalamurutan Rekursif
Lintasan dalamurutan melawati subpepohon kiri, kemudian akar, dan seterusnya subpepohon kanan. Untuk Pepohon Carian Binari, lintasan dalamurutan sentiasa menghasilkan jujukan tersusun — sifat ini digunakan dalam masalah seperti mengesahkan BST, mencari unsur ke-k terkecil dan menukar BST kepada tatasusunan tersusun. Ini ialah lintasan paling penting untuk diketahui bagi masalah BST.
def inorder(root, result=None):
if result is None:
result = []
if not root:
return result
inorder(root.left, result) # left subtree first
result.append(root.val) # PROCESS ROOT MIDDLE
inorder(root.right, result) # right subtree last
return result
# For a BST, inorder gives sorted output:
from collections import deque
def make_bst():
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
return root
bst = make_bst()
print(inorder(bst)) # [1, 2, 3, 4, 6] - sorted!Lintasan Pascaurutan Rekursif
Lintasan pascaurutan memproses kedua-dua anak sebelum nod semasa. Susunan dari bawah ke atas ini semula jadi apabila pengiraan induk bergantung pada hasil anak-anaknya — contohnya, ketika mengira saiz subpepohon, memadam pepohon atau menilai pepohon ungkapan. Kebanyakan masalah pepohon yang menghantar maklumat ke atas menggunakan logik pascaurutan secara tersirat.
def postorder(root, result=None):
if result is None:
result = []
if not root:
return result
postorder(root.left, result) # left subtree
postorder(root.right, result) # right subtree
result.append(root.val) # PROCESS ROOT LAST
return result
# Use case: delete a tree (children before parent)
def delete_tree(root):
if not root:
return
delete_tree(root.left)
delete_tree(root.right)
print(f'Deleting node {root.val}') # safe: children gone
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(postorder(root)) # [4, 2, 3, 1]Lintasan Praurutan Secara Lelaran dengan Timbunan
Untuk mengelakkan had kedalaman rekursi, laksanakan DFS secara lelaran menggunakan timbunan eksplisit. Untuk praurutan: masukkan akar ke dalam timbunan, kemudian dalam setiap lelaran keluarkan satu nod menggunakan pop, catatkannya, dan masukkan anak kanan diikuti anak kiri, iaitu kanan dahulu supaya kiri diproses dahulu. Cara ini meniru tingkah laku LIFO timbunan panggilan dan merupakan pendekatan utama untuk pepohon dalam, apabila had rekursi lalai Python sebanyak 1000 akan menyebabkan kegagalan.
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val) # process now
if node.right: # push right FIRST
stack.append(node.right)
if node.left: # push left second (popped first)
stack.append(node.left)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]Lintasan Dalamurutan Secara Lelaran dengan Timbunan
Lintasan dalamurutan secara lelaran sedikit lebih rumit. Gunakan timbunan dan penuding curr: bergerak ke kiri sejauh yang boleh sambil memasukkan setiap nod. Apabila anda tidak boleh bergerak lebih jauh ke kiri, keluarkan satu nod menggunakan pop, catatkan nod itu, kemudian bergerak ke kanan. Corak ini — masukkan nod kiri sehingga tiada lagi, pop dan proses, kemudian bergerak ke kanan — ialah teknik lelaran asas yang sering muncul dalam masalah lelar BST.
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
# Go as far left as possible
while curr:
stack.append(curr)
curr = curr.left
# Pop and process
curr = stack.pop()
result.append(curr.val)
# Move to right subtree
curr = curr.right
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(inorder_iterative(root)) # [4, 2, 5, 1, 3]Lintasan Pascaurutan Secara Lelaran dengan Dua Timbunan
Lintasan pascaurutan secara lelaran mempunyai satu helah yang kemas: jalankan praurutan yang diubah suai, iaitu akar → kanan → kiri, kemudian kumpulkan hasil secara terbalik. Masukkan akar, keluarkan satu nod menggunakan pop dan tambahkannya pada bahagian hadapan hasil, kemudian masukkan anak kiri diikuti anak kanan. Pembalikan itu menukar susunan akar-kanan-kiri kepada kiri-kanan-akar — tepat seperti pascaurutan. Sebagai pilihan lain, gunakan penuding prev untuk menjejaki nod yang terakhir dilawati dengan satu timbunan.
from collections import deque
def postorder_iterative(root):
if not root:
return []
result = deque()
stack = [root]
while stack:
node = stack.pop()
result.appendleft(node.val) # prepend = reverse pre-order
if node.left:
stack.append(node.left) # push left first
if node.right:
stack.append(node.right) # push right second
return list(result)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(postorder_iterative(root)) # [4, 5, 2, 3, 1]Bila Memilih Setiap Lintasan
Memilih lintasan yang betul ialah petunjuk penting dalam temu duga. Gunakan praurutan apabila anda perlu memproses induk sebelum anak-anaknya, seperti ketika menyirikan pepohon atau menyalin struktur. Gunakan dalamurutan untuk BST bagi memanfaatkan susunan tersusun. Gunakan pascaurutan apabila mengira nilai yang bergantung pada kedua-dua anak, seperti height, diameter dan jumlah subpepohon. BFS lebih sesuai untuk masalah laluan terpendek dan pengumpulan mengikut aras.
# Pattern summary:
# Pre-order -> top-down: parent info flows DOWN to children
# In-order -> BST sorted property, kth element, validate BST
# Post-order -> bottom-up: children info flows UP to parent
# BFS -> shortest path, level grouping, level averages
# Example: compute subtree sum (post-order because
# we need left + right sum before computing total)
def subtree_sum(root):
if not root:
return 0
left = subtree_sum(root.left)
right = subtree_sum(root.right)
return root.val + left + right # uses children FIRST
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(subtree_sum(root)) # 6Lintasan Morris: Ruang O(1) Dalamurutan
Lintasan Morris mencapai ruang O(1) untuk lintasan dalamurutan dengan mengubah suai pepohon buat sementara. Bagi setiap nod yang mempunyai subpepohon kiri, cari pendahulu dalamurutan, iaitu nod paling kanan dalam subpepohon kiri, dan sambungkan penuding kanannya kembali kepada nod semasa. Selepas nod dilawati, pulihkan sambungan itu. Teknik lanjutan ini sering ditanya dalam temu duga peringkat tertinggi apabila penemu duga bertanya, 'bolehkah anda melakukannya dengan ruang tambahan O(1)?'
def morris_inorder(root):
result = []
curr = root
while curr:
if not curr.left:
result.append(curr.val)
curr = curr.right
else:
# Find in-order predecessor
pred = curr.left
while pred.right and pred.right != curr:
pred = pred.right
if not pred.right:
# Make thread and move left
pred.right = curr
curr = curr.left
else:
# Remove thread, visit, move right
pred.right = None
result.append(curr.val)
curr = curr.right
return result
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(morris_inorder(root)) # [1, 2, 3, 4, 6]Membina Semula Pepohon daripada Lintasan
Diberikan tatasusunan praurutan dan dalamurutan, anda boleh membina semula pepohon asal. Unsur pertama dalam praurutan sentiasa ialah akar. Cari akar itu dalam tatasusunan dalamurutan — semua unsur di sebelah kirinya tergolong dalam subpepohon kiri, manakala semua unsur di sebelah kanannya tergolong dalam subpepohon kanan. Gunakan proses ini secara rekursif pada sub-tatasusunan. Kerumitan masa ialah O(n) dengan carian indeks menggunakan peta cincangan.
def build_from_preorder_inorder(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
# left subtree: inorder[0:mid], preorder[1:mid+1]
root.left = build_from_preorder_inorder(
preorder[1:mid+1], inorder[:mid])
# right subtree: inorder[mid+1:], preorder[mid+1:]
root.right = build_from_preorder_inorder(
preorder[mid+1:], inorder[mid+1:])
return root
pre = [3, 9, 20, 15, 7]
ino = [9, 3, 15, 20, 7]
root = build_from_preorder_inorder(pre, ino)
print(root.val, root.left.val, root.right.val) # 3 9 20Ringkasan Masa dan Ruang Lintasan
Ketiga-tiga lintasan DFS mempunyai kerumitan masa O(n) kerana setiap nod dilawati tepat sekali. Kerumitan ruang ialah O(h), dengan h ialah ketinggian pepohon — O(log n) untuk pepohon seimbang dan O(n) untuk pepohon senget, disebabkan timbunan panggilan atau timbunan eksplisit. Pelaksanaan secara lelaran mengelakkan had rekursi Python tetapi menggunakan ruang asimptotik yang sama. Lintasan Morris secara unik mencapai ruang O(1) dengan menggunakan semula penuding kanan pepohon.
# Complexity table:
# Traversal | Time | Space (recursion) | Space (iterative)
# -----------|------|-------------------|------------------
# Pre-order | O(n) | O(h) | O(h)
# In-order | O(n) | O(h) | O(h)
# Post-order | O(n) | O(h) | O(h)
# Morris | O(n) | O(1) | O(1)
# BFS | O(n) | O(w) | O(w)
# h = height, w = max width
# Balanced: h = log n, w = n/2
# Skewed: h = n, w = 1
print('O(n) time for all traversals')Semakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Ulang Kaji Pelajaran
Dalam pelajaran ini, anda telah mempelajari: tiga susunan lintasan DFS, iaitu pra, dalam dan pasca, serta masa untuk memilih setiap satunya; pelaksanaan rekursif dan secara lelaran menggunakan timbunan eksplisit; dan teknik Morris dengan ruang O(1). Seterusnya, kita meneroka pengiraan diameter, height dan keseimbangan pepohon binari.
Pelajari Python dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “DFS Dalam Susunan, Pra-Susunan dan Pasca-Susunan” percuma?
Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “DFS Dalam Susunan, Pra-Susunan dan Pasca-Susunan”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “DFS Dalam Susunan, Pra-Susunan dan Pasca-Susunan”?
Laksanakan ketiga-tiga lintasan DFS secara rekursif dan lelaran dengan tindanan eksplisit, sambil menerangkan kegunaan setiap susunan. Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?
Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.
Berapa lamakah pelajaran “DFS Dalam Susunan, Pra-Susunan dan Pasca-Susunan” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Kelas TreeNode dan BFS Mengikut Aras
- DFS Dalam Susunan, Pra-Susunan dan Pasca-Susunan
- Diameter, Ketinggian dan Pepohon Seimbang
- Jumlah Laluan dan Leluhur Sepunya Terendah