Binary Tree နဲ့ Traversal Order များ

နားလည်ထားရမယ့် အချက်

Linked list မှာ node တစ်ခုက next တစ်ခုကိုပဲ ညွှန်ပြပေမယ့်၊ binary tree မှာ node တစ်ခုစီက child နှစ်ခုအထိ ညွှန်ပြနိုင်တယ် — left child နဲ့ right child။ Terminology အနေနဲ့ parent မရှိတဲ့ tree ရဲ့ ထိပ်ဆုံး node ကို root လို့ခေါ်ပြီး၊ child မရှိတဲ့ node ကို leaf လို့ခေါ်တယ်၊ root ကနေ node တစ်ခုအထိ ရောက်ဖို့ လိုအပ်တဲ့ edge အရေအတွက်ကို depth (ဒါမှမဟုတ် level) လို့ခေါ်ပြီး၊ tree တစ်ခုလုံးရဲ့ အနက်ဆုံး leaf ရဲ့ depth ကို height လို့ခေါ်တယ်။ Tree ရဲ့ node အားလုံးကို visit လုပ်ဖို့ traversal order (visit လုပ်တဲ့ အစီအစဉ်) အမျိုးမျိုး ရှိတယ် — in-order (left → node → right) ဟာ binary search tree မှာ sorted order ရအောင် ထုတ်ပေးတယ်၊ pre-order (node → left → right) ဟာ tree ကို serialize/copy ချင်တဲ့အခါ root ကို အရင်ဆုံး process လုပ်ချင်လို့ အသုံးဝင်တယ်၊ post-order (left → right → node) ကတော့ child တွေအားလုံး process ပြီးမှ parent ကို process လုပ်ချင်တဲ့ ကိစ္စတွေမှာ သုံးတယ် — ဥပမာ directory tree တစ်ခုကို delete ချင်ရင် file (leaf) တွေကို ဦးစွာ ဖျက်ပြီးမှ folder (parent) ကို ဖျက်ရမှာဖြစ်လို့။ ဒီ order သုံးမျိုးစလုံးက recursive definition ရှိတဲ့ node structure ကို natural recursive function တစ်ခုနဲ့ visit လုပ်တာသာဖြစ်တယ်။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform ရဲ့ course category structure (course → chapter → sub-topic) ကို binary tree (ဒါမှမဟုတ် n-ary tree) အနေနဲ့ ကိုယ်စားပြုနိုင်တယ်၊ in-order traversal ကို table-of-contents sidebar ဖန်တီးဖို့ သုံးပြီး၊ post-order ကို course တစ်ခုလုံး archive ဖျက်ချင်တဲ့အခါ sub-lesson တွေအားလုံးကို ဦးစွာ cleanup လုပ်ဖို့ သုံးနိုင်တယ်။

Node တစ်ခုစီမှာ left child နဲ့ right child ဆိုတဲ့ pointer နှစ်ခုအထိ ထားနိုင်တယ်
In-order traversal က BST ကနေ sorted order ထုတ်ပေးတယ်
Pre-order က root ကို အရင် process လုပ်ချင်ရင်၊ post-order က children ပြီးမှ parent process လုပ်ချင်ရင် သင့်တော်တယ်

အတူတူ စမ်းရေးကြည့်မယ်

python

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def in_order(node, result):
    if node is None:
        return result
    in_order(node.left, result)   # visit left subtree first
    result.append(node.value)     # then this node
    in_order(node.right, result)  # then right subtree
    return result

#        "queues"
#        /      \
# "hash-tables" "stacks"
root = Node("queues", Node("hash-tables"), Node("stacks"))
print(in_order(root, []))

You should see

`['hash-tables', 'queues', 'stacks']` ကို print ထုတ်ပေးတယ် — left child, root, right child အစီအစဉ်အတိုင်း visit လုပ်ခဲ့လို့ဖြစ်တယ်။

၅ မိနစ် စမ်းကြည့်

အထက်ပါ tree အတွက် `pre_order` နဲ့ `post_order` function နှစ်ခုကို ရေးပြီး output သုံးခုစလုံးကို နှိုင်းယှဉ် print ကြည့်ပါ။

သတိလေးတစ်ချက်

Base case (`if node is None: return`) ထည့်ဖို့မေ့ရင် recursion က leaf ကိုရောက်တဲ့အခါ `None.left` ကို access လုပ်ဖို့ ကြိုးစားလို့ AttributeError တက်တတ်တယ်

In-order traversal ဟာ binary tree မျိုးစုံအတွက် sorted output ပေးမယ်လို့ ထင်တတ်တယ် — ဒါက BST invariant (left < node < right) ရှိမှ မှန်ကန်မှာဖြစ်တယ်၊ ဒီ example tree ကတော့ BST မဟုတ်ဘူး

Wikipedia — Binary tree — Data Structures & Algorithms