Tree Traversals

Tree traversals ဆိုတာကေတာ့ tree တစ္ခုမွာ node တစ္ခု ျခင္းဆီ ကို သြားသည့္ process လို့ ဆိုရပါမယ္။ Tree Traversals ၂ မ်ဳိး ရိွပါတယ္။

  • Depth-first search
  • Breadth-first search

ဆိုျပီး ရိွပါတယ္။

Depth-first search (DFS)

DFS ကို အသံုးျပဳျပီး data ေတြကို ျပန္ျပီး ထုတ္ျပဖို့ အတြက္ ထုတ္ျပနည္း ၃ ခု ရိွပါတယ္။

  • in order
  • pre order
  • post order

ဆိုျပီး ရိွပါတယ္။

In Order

In order ဆိုတာကေတာ့ ဘယ္ဘက္ က data ကို ျပမယ္။ ျပီးမွ center ကို ျပမယ္။ ျပီးရင္ ညာဘက္ ကို ျပမယ္။

အဲဒီ ပံုေလးကို in order အရ ထုတ္မယ္ ဆိုရင္

  • F
  • D
  • G
  • B
  • E
  • A
  • C

ဆိုျပီး ထုတ္ပါမယ္။ ဘယ္ဘက္ က ေအာက္ဆံုးကို အရင္ ထုတ္တယ္။ ျပီးေတာ့ သူ႕ရဲ႕ parent ကို ထုတ္ျပတယ္။ ျပီးေတာ့ ညာဘက္ က node ကို ထုတ္တယ္။

ဘယ္ဘက္ ေအာက္ဆံုးက F ျဖစ္ျပီးေတာ့ F ရဲ႕ parent က D ပါ။ ျပီးေတာ့ ညာဘက္ G ကို ထုတ္မယ္။ ညာဘက္ node က ဆက္မရိွေတာ့သည့္ အတြက္ parent ကို ျပန္သြားမယ္။ parent က လည္း ကိစၥ ျပီးျပီ ျဖစ္သည့္ အတြက္ သူ႕ရဲ႕ parent ကို ျပန္သြားမယ္။ အဲဒီ parent က node ကို B ကို ထုတ္ျပပါတယ္။ ျပီးေတာ့ ညာဘက္ က E ကို ထုတ္ျပတယ္။ parent ကို ျပန္သြားတယ္။ A ကို ထုတ္ျပတယ္။ ျပီးေတာ့ ညာဘက္က C ကို ထုတ္ျပတယ္။

In order ကေတာ့ ေအာက္ဆံုးမွာ ရိွသည့္ ဘယ္ဘက္ က node ကို အရင္ျပမယ္။ ျပီးရင္ parent ကို ျပမယ္။ ျပီးရင္ ညာဘက္ ေအာက္ဆံုး ထိ ဆင္းျပီးမွ ျပမယ္။

သြားသည့္ flow ေလးကို ၾကည့္ရေအာင္။

အဲဒီ flow ေလးကို ၾကည့္လိုက္ရင္ in order ကို ေကာင္းမြန္စြာ နားလည္သြားပါလိမ့္မယ္။

အခု code ေလး ကို ၾကည့္ ရေအာင္။

def inorder(self):
    if self != None:
        if self.get_left_child() != None:
            self.get_left_child().inorder()

        print(self.get_root_val())

        if self.get_right_child() != None:
            self.get_right_child().inorder

ကၽြန္ေတာ္တို့ recursive ကို သံုးျပီးေတာ့ left child ေတြ အကုန္ သြားပါတယ္။ ေနာက္ဆံုး အဆင့္မွာ root value ကို print ထုတ္ထားတယ္။ ျပီးသြားမွာ parent ရဲ႕ value ကို ထုတ္ထားတယ္။ ျပီးရင္ right ေတြ အကုန္ျပန္ ဆင္းခ်ထားတာကို ေတြ႕ႏိုင္ပါတယ္။

Pre Order

In Order ကို နားလည္သြားရင္ေတာ့ pre order က node value ကို အရင္ထုတ္ျပီးမွ left ကို သြားတာပါ။ အနည္းငယ္ ကြာျခားသြားတယ္။

အဲဒီ ပံုေလးကို pre order အရ ထုတ္မယ္ဆိုရင္ေတာ့

  • A
  • B
  • D
  • F
  • G
  • E
  • C

ဆိုျပီး ထြက္လာပါလိမ့္မယ္။

In order ကို နားလည္ထားျပီးျပီေတာ့ အေသးစိတ္ မရွင္းေတာ့ပါဘူး။ code ေလးကို ၾကည့္ရေအာင္။

def preorder(self):
    if self != None:
        print(self.get_root_val())

        if self.get_left_child() != None:
            self.get_left_child().preorder()

        if self.get_right_child() != None:
            self.get_right_child().preorder()

အရင္ဆံုး node ရဲ႕ value ကို ထုတ္လုိက္ပါတယ္။ ျပီးမွ left ကို သြားပါတယ္။ left အကုန္ျပီးမွ right ကို သြားတာကို ေတြ႕ပါလိမ့္မယ္။

Post Order

Pre order နဲ႕ အနည္းငယ္သာ ကြဲျပားပါတယ္။ အရင္ဆံုး left ကို ထုတ္တယ္။ ျပီးမွ right ကို ထုတ္တယ္။ ျပီးမွ node ရဲ႕ value ကို ထုတ္မယ္။

အထက္ပါ binary tree ကို ထုတ္မယ္ဆိုရင္

  • F
  • G
  • D
  • E
  • B
  • C
  • A

ဆိုျပီး ထြက္လာပါမယ္။

ေအာက္ဆံုး F က အရင္ လာမယ္။ ျပီးရင္ ညာဘက္က G လာမယ္။ ျပီးမွ သူ႕ရဲ႕ parent D လာပါမယ္။ ျပီးရင္ ညာဘက္ က E လာမယ္။ ျပီးမွ parent B လာပါမယ္။ B ရဲ႕ ညာဘက္က C လာမယ္။ ျပီးမွ parent A လာပါမယ္။

code ကေတာ့ ဆင္တူပါပဲ။

def postorder(self):
    if self != None:
        if self.get_left_child() != None:
            self.get_left_child().postorder()

        if self.get_right_child() != None:
            self.get_right_child().postorder()

        print(self.get_root_val())

အခု ဆုိရင္ေတာ့ ကၽြန္တာ္တုိ႕ေတြ binary Tree တစ္ခု လံုး ကို သြားတတ္ေနပါျပီ။

code ေလးကို ၾကည့္ရေအာင္။

class BinaryTree: def __repr__(self): return "Binary Tree, Key is " + self.key def __init__(self,root): self.key = root self.left_child = None self.right_child = None def insert_left(self,new_node): if self.left_child == None: self.left_child = BinaryTree(new_node) else: t = BinaryTree(new_node) t.left_child = self.left_child self.left_child = t def insert_right(self,new_node): if self.right_child == None: self.right_child = BinaryTree(new_node) else: t = BinaryTree(new_node) t.right_child = self.right_child self.right_child = t def get_right_child(self): return self.right_child def get_left_child(self): return self.left_child def set_root_val(self,obj): self.key = obj def get_root_val(self): return self.key def inorder(self): if self != None: if self.get_left_child() != None: self.get_left_child().inorder() print(self.get_root_val()) if self.get_right_child() != None: self.get_right_child().inorder() def postorder(self): if self != None: if self.get_left_child() != None: self.get_left_child().postorder() if self.get_right_child() != None: self.get_right_child().postorder() print(self.get_root_val()) def preorder(self): if self != None: print(self.get_root_val()) if self.get_left_child() != None: self.get_left_child().preorder() if self.get_right_child() != None: self.get_right_child().preorder() root = BinaryTree("A") root.insert_left("B") root.insert_right("C") b = root.get_left_child() b.insert_left("D") b.insert_right("E") d = b.get_left_child() d.insert_left("F") d.insert_right("G") print("---- In Order ----") root.inorder() print("---- Pre Order ----") root.preorder() print("---- Post Order ----") root.postorder()

Exercise

၁။ အထက္ပါ binary tree တစ္ခု တည္ေဆာက္ပါ။ ထို binary tree အတြက္ dfs ကို သံုးျပီး search function ကို ေရးပါ။ ဥပမာ ။ F လုိ႕ ထည့္လိုက္လွ်င္ binary tree တြင္ ပါဝင္ေသာေၾကာင့္ true ဟု return ျပန္ပါမည္။ H ဟု ထည့္လိုက္လွ်င္ ရွာ မေတြ႕ေသာေၾကာင့္ false ဟု return ျပန္ရမည္။

Breadth-first search (BFS)

အခု ကၽြန္ေတာ္တို့ ေနာက္တနည္းျဖစ္သည့္ BFS ကို အသံုးျပဳျပီးေတာ့ Binary Tree က node ေတြကို အဆင့္လိုက္သြားပါမယ္။

ဆိုသည့္ ပံုမွာ BFS အရ ဆိုရင္ေတာ့

  • A
  • B , C
  • D , E
  • F , G

ဆိုျပီးေတာ့ level အဆင့္လိုက္ ထုတ္ျပပါလိမ့္မယ္။

ကၽြန္ေတာ္တုိ့ေတြ အေနနဲ႕ ပထမဆံုး root ကေန စပါမယ္။ root က A ပါ။ A ရဲ႕ left ႏွင့္ right ကို array ထဲမွာ မွတ္ထားတယ္။ B,C ေပါ့။ ျပီးရင္ B ရဲ႕ left ႏွင့္ right ကို array ထဲမွာ မွတ္ထားမယ္။ D,E ပါ။ C ရဲ႕ left ႏွင့္ right ကို ထပ္ျပီးေတာ့ မွတ္ထားမယ္။ သို့ေပမယ့္ C မွာ child မရိွသည့္ အတြက္ေၾကာင့္ D,E ပဲ ရိွပါေတာ့မယ္။ အကယ္၍ C မွာ left ႏွွင့္ right မွာ child ရိွခဲ့လွ်င္ မွတ္ထားသည့္ value က D,E,left Of C, right of C ျဖစ္သြားပါမယ္။ အခုေတာ့ D,E မွာ D ရဲ႕ left နဲ႕ right F,G ကို မွတ္ထားပါတယ္။ E မွာ child မရိွသည့္ အတြက္ေၾကာင့္ မွတ္ထားသည့္ array ထဲမွာ F,G ပဲ ရိွမယ္။ F မွာ child မရိွေတာ့ဘူး။ G မွာလည္း child မရိွေတာ့ပါဘူး။ array အခန္းထဲမွာ မရိွေတာ့သည့္ အတြက္ေၾကာင့္ loop ကေန ထြက္သြားပါမယ္။ node ေတြ အားလံုးကိုလည္း ေရာက္ခဲ့ျပီးပါျပီ။

Pseudo code နဲ႕ စဥ္းစားၾကည့္ရေအာင္ဗ်ာ။

current_level = [Root_A]
Loop Until current_level is not empty
    next_level = [] //create empty array for saving
    level_data = [] //to store current level value

    For node in current_level
        level_data.append(node.value)

        if node.left_child is not empty
            next_level.append(node.left_child)

        if node.right_child is not empty
            next_level.append(node.right_child)
    End For Loop

    Print level_data

    current_level = next_level // start again for child data

End Loop

အဲဒါေလးေတြကေတာ့ စဥ္းစားျပီး ေရးခ်ထားသည့္ pseudo code ေတြပါ။ ပထမဆံုး ထိပ္ဆံုး root ကေန စတယ္။ ျပီးရင္ သူ႕ေအာက္ level က child ကို array ထဲမွာ ထည့္တယ္။ အစကေန loop ျပန္ပတ္တယ္။ child ထဲမွာ ရိွသည့္ left,right ကို array ထဲကို ထည့္တယ္။ အကုန္ျပီးသြားရင္ အစကေန loop ျပန္ပတ္ထားတာကို ေတြ႕ႏိုင္ပါတယ္။ ဘယ္ အခ်ိန္ loop ပတ္ေနလဲ ဆိုေတာ့ child ေတြ တစ္ခုမွ မရိွေတာ့သည့္ အဓိ loop ပတ္ေနပါတယ္။

python code ေျပာင္းေရးၾကည့္ရေအာင္။

class BinaryTree: def __repr__(self): return "Binary Tree, Key is " + self.key def __init__(self,root): self.key = root self.left_child = None self.right_child = None def insert_left(self,new_node): if self.left_child == None: self.left_child = BinaryTree(new_node) else: t = BinaryTree(new_node) t.left_child = self.left_child self.left_child = t def insert_right(self,new_node): if self.right_child == None: self.right_child = BinaryTree(new_node) else: t = BinaryTree(new_node) t.right_child = self.right_child self.right_child = t def get_right_child(self): return self.right_child def get_left_child(self): return self.left_child def set_root_val(self,obj): self.key = obj def get_root_val(self): return self.key def bfs(self): thislevel = [self] while thislevel: nextlevel = [] level = [] for n in thislevel: level.append(n.get_root_val()) if n.get_left_child() != None: nextlevel.append(n.get_left_child()) if n.get_right_child() != None: nextlevel.append(n.get_right_child()) print(",".join(level)) thislevel = nextlevel root = BinaryTree("A") root.insert_left("B") root.insert_right("C") b = root.get_left_child() b.insert_left("D") b.insert_right("E") d = b.get_left_child() d.insert_left("F") d.insert_right("G") root.bfs()

အထက္ပါ code မွာ print(",".join(level)) ဆိုသည္မွာ array အား string အေနျဖင့္ ျပရန္ အတြက္ ျဖစ္သည္။ array မွ data မ်ားအား comma(,) ျဖင့္ ေဖာ္ျပရန္ အတြက္ ",".join အား အသံုးျပဳထားျခင္း ျဖစ္သည္။

အခု ဆိုရင္ေတာ့ BFS ကို အသံုးျပဳျပီးေတာ့ binary tree ရဲ႕ node ေတြ အားလံုးကို သြားတတ္ျပီလုိ႕ထင္ပါတယ္။

Binary tree ဟာ left ႏွင့္ right ၂ ခု ပဲရိွပါတယ္။ ကိုယ္တိုင္ binary tree မဟုတ္ပဲ တစ္ခုထက္ မက node ေတြကို child အျဖစ္ထည့္သြင္းသည့္ class လည္း အခု အခ်ိန္မွာ လြယ္လင့္ တကူ ဖန္တီး ႏိုင္ပါျပီ။ ထို့ အတူ DFS , BFS ကို ထို Tree structure မွာ ျပန္လည္ အသံုးခ်ႏိုင္ပါလိမ့္မယ္။

Exercise

၁။ အထက္ပါ binary tree တစ္ခု တည္ေဆာက္ပါ။ ထို binary tree အတြက္ bfs ကို သံုးျပီး search function ကို ေရးပါ။ ဥပမာ ။ F လုိ႕ ထည့္လိုက္လွ်င္ binary tree တြင္ ပါဝင္ေသာေၾကာင့္ true ဟု return ျပန္ပါမည္။ H ဟု ထည့္လိုက္လွ်င္ ရွာ မေတြ႕ေသာေၾကာင့္ false ဟု return ျပန္ရမည္။

၂။ အထက္ပါ binary tree တစ္ခု တည္ေဆာက္ပါ။ Path လမ္းေၾကာင္း ျပ function တစ္ခု ဖန္တီးပါ။ ဥပမာ။။ path('A','F') ဟု ဆိုလွ်င္ ['A','C','F'] ဟု ပတ္လမ္းေၾကာင္း ကို array ျဖင့္ return ျပန္ေပးရမည္။

results matching ""

    No results matching ""