Binary Tree

Tree အေၾကာင္းကို ေလ့လာေတာ့မယ္ဆိုရင္ ဦးစြာ Binary Tree အေၾကာင္းကို နားလည္ ဖို႔ လိုပါတယ္။

Binary Tree ဆိုတာကေတာ့ Node တစ္ခု ေအာက္မွာ branch ၂ ခု ပဲ ရွိရမယ္။ အနည္းဆံုး branch 0 ကေန 2 အဓိပဲ ရွိသည့္ tree system တစ္ခုပါ။

အခု Binary Tree ဥပမာ ေလး ၾကည့္ရေအာင္။

A ရဲ့ ေအာက္မွာ B ႏွင့္ C ရိွတယ္။ B ေအာက္မွာ D ရိွတယ္။ C ေအာက္မွာေတာ့ E နဲ့ F ရိွပါတယ္။ ဒီ ပုံ တစ္ခုလံုးကိုေတာ့ tree လို့ ဆိုႏိုင္တယ္။ A,B,C,D,E,F ေတြကေတာ့ Node ေတြပါ။ Binary tree ရဲ႕ Node မွာ left နဲ့ right ရိွပါတယ္။ left ဘက္က child နဲ့ right ဘက္က child ေပါ့။ Node A ရဲ့ left ကေတာ့ B Node ျဖစ္ျပီးေတာ့ right ကေတာ့ C Node ေပါ့။ B Node ရဲ့ left ကေတာ့ Node D ျဖစ္ျပီး right ကေတာ့ empty ျဖစ္ေနပါတယ္။ C ရဲ့ left ကေတာ့ E Node ျဖစ္ျပီးေတာ့ right node ကေတာ့ F ျဖစ္ေနပါတယ္။

ဒါဆိုရင္ ကၽြန္ေတာ္တုိ့ binary tree တစ္ခု ကို တည္ေဆာက္ၾကည့္ရေအာင္။ ကၽြန္ေတာ္တုိ့ဆီမွာ BinaryTree class တစ္ခုရိွမယ္။ left_child နဲ့ right_child ရိွမယ္။ အဲဒီ ၂ ခု လံုးက လည္း BinaryTree class ေတြ ျဖစ္ရမယ္။ ေနာက္ တစ္ခုက လက္ရိွ root key ရိွရမယ္။

class BinaryTree: def __init__(self,root): self.key = root self.left_child = None self.right_child = None

ေနာက္တဆင့္ အေနနဲ့ စဥ္းစားရင္ left ႏွင့္ right ထည့္ဖို့ လိုမယ္။ အဲဒီမွာ ဘာကို ထပ္ျပီး စဥ္းစားဖို့ လိုလဲဆိုေတာ့ left ထဲမွာ data ရိွေနရင္ အသစ္ထည့္လိုက္သည့္ tree ထဲမွာ append သြားလုပ္ဖို့လိုတယ္။ right ထဲမွာ data ရိွေနရင္လည္း အသစ္ထည့္မယ့္ tree ထဲမွာ append လုပ္ဖို့ လိုပါတယ္။

ဥပမာ။

အထက္က ပံုေလးဆိုရင္ Node အသစ္ မထည့္ရေသးဘူး။ အဲဒီ အထဲမွာ ကၽြန္ေတာ္ k Node ေလး ကို left ဘက္မွာ ထည့္လိုက္ရင္ ေအာက္ကလို ျဖစ္သြားပါမယ္။

ဒါေၾကာင့္ insert မွာ ကၽြန္ေတာ္တို့ အေနနဲ့ data ရိွျပီးသားလား မရိွရေသးဘူးလား စစ္ဖို့ လိုမယ္။ မရိွေသးဘူးဆိုရင္ တစ္ခါတည္း ထည့္မယ္။ ရိွမယ္ ဆိုရင္ေတာ့ လက္ရိွ ရိွေနသည့္ node ကို node အသစ္မွာ လာထည့္ဖို႕လိုပါလိမ့္မယ္။

class BinaryTree: 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

အခု ထပ္ျပီးေတာ့ ရိွသည့္ left, right ကို ဆြဲထုတ္ဖို႕ ေရးရေအာင္။

class BinaryTree: 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

အခု အခ်ိန္မွာေတာ့ code ေလးေတြက ခက္ခက္ခဲခဲမဟုတ္ပဲ နဲ႕နားလည္ ႏိုင္ပါတယ္။

ကၽြန္ေတာ္တို့ရဲ့ Binary Tree ကုိ စမ္းၾကည့္ရေအာင္။

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 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())

from binarytree import BinaryTree root = BinaryTree('a') print(root) print(root.get_root_val()) print(root.get_left_child()) root.insert_left('b') print(root.get_left_child().get_root_val()) root.insert_right('c') print(root.get_right_child().get_root_val()) root.get_right_child().set_root_val('hello') print(root.get_right_child().get_root_val()) root.insert_left('d') print(root.get_left_child()) print(root.get_left_child().get_left_child().get_root_val())

အဲဒီမွာ

def __repr__(self):
        return "Binary Tree, Key is " + self.key

ဆိုတာေလးကို ေတြ႕ရလိမ့္မယ္။ အဲဒါကေတာ့ ကၽြန္ေတာ္တုိ့ object ကို print နဲ့ ထုတ္သည့္ အခါမွာ <__main__.BinaryTree object at 0x10293b5f8> ဆိုျပီး မေပၚခ်င္ပဲ key ကို ထုတ္ျပခ်င္သည့္ အတြက္ေၾကာင့္ __repr__ ဆိုသည့္ function မွာ ဝင္ေရးထားတာပါ။

root.insert_left('d')
print(root.get_left_child())
print(root.get_left_child().get_left_child().get_root_val())

ဒီ code ဆိုရင္လည္း a ရဲ့ left မွာ b ရိွတယ္။ ထပ္ျပီးေတာ့ d ကိုထည့္လိုက္တယ္။ ျပီးမွ a ရဲ႕ left child ရဲ႕ left child ကို ျပန္ျပီးေတာ့ print ထုတ္ထားတာပါ။ a ရဲ႕ left child က d ျဖစ္သြားျပီးေတာ့ d ရဲ႕ left child ကေတာ့ b ျဖစ္သြားတာကို ေတြ့ရပါလိမ့္မယ္။

results matching ""

    No results matching ""