Bagaimana untuk melaksanakan traversal pokok binari menggunakan Python

Sebagai struktur data yang biasa digunakan, pepohon binari sering digunakan untuk menyimpan data, mencari dan mengisih. Melintasi pokok binari adalah salah satu operasi yang sangat biasa. Sebagai bahasa pengaturcaraan yang mudah dan mudah digunakan, Python mempunyai banyak kaedah untuk melaksanakan traversal pokok binari. Artikel ini akan memperkenalkan cara menggunakan Python untuk melaksanakan traversal prapesanan, tertib dan pasca pesanan bagi pokok binari.

Asas Pokok Binari

Sebelum mempelajari cara melintasi pokok binari, kita perlu memahami konsep asas pokok binari. Pokok binari terdiri daripada nod, setiap nod mempunyai nilai dan dua anak (anak kiri dan anak kanan). Anak-anak nod boleh kosong.

Perjalanan pokok binari

Perjalanan pokok binari merujuk kepada melawati semua nod dalam pokok binari dalam susunan tertentu. Terdapat tiga kaedah traversal yang biasa digunakan: traversal prapesanan, traversal tertib dan traversal pasca pesanan.

Preorder traversal

Turutan prapesan traversal ialah nod akar, subpokok kiri dan subpokok kanan. Dalam pelaksanaan khusus, anda boleh terlebih dahulu mengeluarkan nilai nod akar, dan kemudian melintasi subpokok kiri dan subpokok kanan secara rekursif.

Berikut ialah pelaksanaan kod Python:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorderTraversal(root: TreeNode):
    if root is None:
        return []
    res = [root.val]
    res += preorderTraversal(root.left)
    res += preorderTraversal(root.right)
    return res

Traversal tertib

Turutan traversal tertib ialah subpokok kiri, nod akar dan subpokok kanan. Dalam pelaksanaan khusus, adalah perlu untuk melintasi subpokok kiri secara rekursif, mengeluarkan nilai nod akar, dan kemudian melintasi subpokok kanan secara rekursif.

Berikut ialah pelaksanaan kod Python:

def inorderTraversal(root: TreeNode):
    if root is None:
        return []
    res = []
    res += inorderTraversal(root.left)
    res.append(root.val)
    res += inorderTraversal(root.right)
    return res

Perjalanan pasca pesanan

Turutan rentas pasca pesanan ialah subpokok kiri, subpokok kanan dan nod akar. Dalam pelaksanaan khusus, adalah perlu untuk melintasi subpokok kiri dan subpokok kanan secara rekursif, dan akhirnya mengeluarkan nilai nod akar.

Berikut ialah pelaksanaan kod Python:

def postorderTraversal(root: TreeNode):
    if root is None:
        return []
    res = []
    res += postorderTraversal(root.left)
    res += postorderTraversal(root.right)
    res.append(root.val)
    return res

Ringkasan

Dalam Python, apabila menggunakan traversal pokok binari, anda boleh mencapai prapesanan, pesanan dan pasca- perintah traversal melalui rekursi . Selain rekursi, ia juga boleh dilaksanakan menggunakan kaedah seperti carian tindanan dan keluasan pertama. Menguasai kaedah traversal pokok binari akan sangat berguna untuk kerja pengaturcaraan harian.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan traversal pokok binari menggunakan Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!