Tree

ကၽြန္ေတာ္တုိ့ binary tree ကို ျပန္လည္ျပဳျပင္ျပီးေတာ့ Tree တစ္ခု ဖန္တီးပါမယ္။ Binary Tree နဲ႕ ကြာျခားတာကေတာ့ Tree မွာ children ေတြက တစ္ခု ထက္မက ပါဝင္ပါတယ္။ Binary Tree မွာ left,right အစား child ပဲ ရိွပါေတာ့မယ္။

ကၽြန္ေတာ္တို့ အေနနဲ႕ Binary Tree Class အစား Node class ကို ဖန္တီးပါမယ္။

Node class ထဲမွာေတာ့ child ေတြကို ထည့္ဖို့ list ပါ ပါမယ္။ Node class ထဲမွာေတာ့ အရင္ကလို value ကို တိုက္ရိုက္ မထည့္ေတာ့ပဲ Node class ကိုသာ ထည့္သြင္းပါမယ္။

အထက္ပါ ပံုအတိုင္း code ေလး ေရးၾကည့္ပါမယ္။

class Node: def __init__(self,value): self.value = value self.child = [] def __repr__(self): return "Value is " + self.value def insert_child(self,node): self.child.append(node) def get_child(self): return self.child root = Node("A") b = Node("B") c = Node("C") d = Node("D") root.insert_child(b) root.insert_child(c) root.insert_child(d) e = Node("E") f = Node("F") g = Node("G") b.insert_child(e) b.insert_child(f) b.insert_child(g) h = Node("H") i = Node("I") c.insert_child(h) c.insert_child(i) j = Node("J") d.insert_child(j) print(root.value) print(root.child) print(root.child[0].value) print(root.child[0].child[0].value)

child ေတြ အကုန္လံုးက list ျဖစ္သည့္ အတြက္ root.child[0].value ဆိုျပီး ေခၚႏိုင္ပါတယ္။ list ျဖစ္သည့္အတြက္ child အေရအတြက္ သိခ်င္ရင္ေတာ့ len(root.child) ျဖင့္ အသံုးျပဳႏိုင္ပါတယ္။

အခု BFS ကို အသံုးျပဳၾကည့္ရေအာင္။

class Node: def __init__(self,value): self.value = value self.child = [] def __repr__(self): return "Value is " + self.value def insert_child(self,node): self.child.append(node) def get_child(self): return self.child def bfs(self): thislevel = [self] while thislevel: nextlevel = [] level = [] for n in thislevel: level.append(n.value) if len(n.child) > 0: nextlevel = nextlevel + n.child if len(level) > 0 : print(",".join(level)) thislevel = nextlevel root = Node("A") b = Node("B") c = Node("C") d = Node("D") root.insert_child(b) root.insert_child(c) root.insert_child(d) e = Node("E") f = Node("F") g = Node("G") b.insert_child(e) b.insert_child(f) b.insert_child(g) h = Node("H") i = Node("I") c.insert_child(h) c.insert_child(i) j = Node("J") d.insert_child(j) root.bfs()

Node ေအာက္မွာ child ေတြက array ျဖစ္သည့္ အတြက္ nextlevel array ကို child ႏွင့္ merge လုပ္ဖို့ လိုပါတယ္။

nextlevel = nextlevel + n.child

python မွာ array ၂ ခုကို merge လုပ္ခ်င္ရင္ေတာ့ merge = array + array ဆိုျပီး အသံုးျပဳ ႏိုင္ပါတယ္။ အထက္ပါ BFS ကို တဆင့္ဆီ ကိုယ္တိုင္ trace လုိက္ၾကည့္ဖို့ လိုပါတယ္။

Exercise

၁။ အထက္ပါ Tree ကို DFS ျဖင့္ ေရးသားပါ။ တစ္ခုထက္မက child ေတြ ျဖစ္ႏိုင္သည့္ အတြက္ preoder ႏွင့္ postorder သာ အသံုးျပဳႏိုင္ပါသည္။ ထို့ေၾကာင့္ preoder ႏွင့္ postorder function ေရးသားပါ။

results matching ""

    No results matching ""