Traversal binary tree: preorder, inorder, postorder, dan level order

Mengapa urutan traversal penting

Tree tidak punya satu urutan alami, jadi algoritma memilih yang cocok dengan tugasnya. Traversal inorder pada binary search tree menghasilkan key dalam urutan terurut. Preorder mengunjungi induk sebelum anak-anaknya, yang Anda butuhkan untuk menyalin tree atau menuliskannya agar bisa dibangun kembali. Postorder mengunjungi anak sebelum induk, yang Anda butuhkan untuk menghapus tree, menghitung ukuran folder, atau mengevaluasi expression tree. Level order menemukan node terdangkal lebih dulu dan mencetak tree baris demi baris.

Keempat urutan pada satu contoh

Kita memakai tree ini: root 1 dengan anak 2 dan 3; node 2 punya anak 4 dan 5; node 3 punya anak kanan 6.

        1
       / \
      2   3
     / \   \
    4   5   6

Cara mudah mengingat tiga yang pertama: namanya menunjukkan di mana node berada. Pre berarti sebelum kedua subtree, in berarti di antara keduanya, post berarti setelah keduanya. Subtree kiri selalu dikunjungi sebelum subtree kanan.

Implementasi rekursif

Versi rekursif mencerminkan definisinya secara langsung. Setiap fungsi mengunjungi node pada baris yang berbeda.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right
def preorder(node, out):
    if node:
        out.append(node.val)
        preorder(node.left, out)
        preorder(node.right, out)
    return out
def inorder(node, out):
    if node:
        inorder(node.left, out)
        out.append(node.val)
        inorder(node.right, out)
    return out
def postorder(node, out):
    if node:
        postorder(node.left, out)
        postorder(node.right, out)
        out.append(node.val)
    return out
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))
print(preorder(root, []))   # [1, 2, 4, 5, 3, 6]
print(inorder(root, []))    # [4, 2, 5, 1, 3, 6]
print(postorder(root, []))  # [4, 5, 2, 6, 3, 1]

Preorder dan inorder iteratif dengan stack

Rekursi memakai call stack. Untuk menghindari batas rekursi pada tree yang dalam, kelola stack sendiri. Untuk preorder, pop sebuah node, kunjungi, lalu push anak kanan sebelum anak kiri agar yang kiri diproses lebih dulu.

Untuk inorder, telusuri ke kiri sejauh mungkin sambil mem-push node di sepanjang jalan. Saat tidak bisa ke kiri lagi, pop sebuah node, kunjungi, lalu pindah ke anak kanannya.

def preorder_iter(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out
def inorder_iter(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:              # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out
print(preorder_iter(root))  # [1, 2, 4, 5, 3, 6]
print(inorder_iter(root))   # [4, 2, 5, 1, 3, 6]

Postorder dan level order iteratif

Postorder iteratif adalah yang paling rumit. Satu pendekatan yang rapi memakai flag: push setiap node dua kali, yang kedua kali ditandai siap dikunjungi setelah anak-anaknya. Level order memakai queue, bukan stack; memproses queue satu level sekaligus juga memberi tahu kedalaman setiap node.

from collections import deque
def postorder_iter(root):
    out, stack = [], [(root, False)] if root else []
    while stack:
        node, children_done = stack.pop()
        if children_done:
            out.append(node.val)
        else:
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    return out
def level_order(root):
    levels, queue = [], deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):   # nodes of the current level
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels
print(postorder_iter(root))  # [4, 5, 2, 6, 3, 1]
print(level_order(root))     # [[1], [2, 3], [4, 5, 6]]

Trik umum lain untuk postorder: jalankan preorder yang dimodifikasi (node, kanan, kiri) lalu balik hasilnya.

Kompleksitas waktu dan ruang

Di sini n adalah jumlah node, h tinggi tree, dan w lebar maksimum. Untuk tree seimbang h sekitar log2(n) dan w bisa sekitar n/2; untuk tree berbentuk rantai h adalah n dan w adalah 1.

Kesalahan umum

• Mem-push anak kiri sebelum anak kanan pada preorder iteratif. Stack itu LIFO, jadi anak yang ingin diproses lebih dulu harus di-push terakhir.
• Lupa menangani tree kosong: setiap fungsi harus mengembalikan hasil kosong untuk root is None.
• Memakai list dengan pop(0) sebagai queue pada level order. Itu O(n) per pop; gunakan collections.deque.
• Mengandalkan rekursi untuk tree yang sangat dalam. Python berhenti pada batas rekursinya (sekitar 1000 secara default) dengan RecursionError.
• Berharap satu traversal saja bisa mengidentifikasi sebuah tree. Preorder saja ambigu; preorder plus inorder (dengan nilai yang berbeda-beda) cukup untuk membangunnya kembali.

Kapan memakai traversal yang mana

Preorder, inorder, dan postorder semuanya adalah bentuk depth-first search; level order adalah breadth-first search yang diterapkan pada tree. Ide yang sama berlaku untuk graf umum, di mana Anda juga butuh himpunan node yang sudah dikunjungi.