বাইনারি ট্রিতে রিকার্সিভ DFS (প্রি-অর্ডার স্টাইল: রুট -> লেফট -> রাইট) ইমপ্লিমেন্ট করা হয়।
উদাহরণ
class BinaryTreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert_left(self, node):
self.left = node
def insert_right(self, node):
self.right = node
def find(self, key):
if self.key == key:
return self
for child in (self.left, self.right):
if child:
found = child.find(key)
if found:
return found
return None
def dfs(self):
"""প্রি-অর্ডার DFS: রুট -> লেফট -> রাইট"""
print(f"entering {self.key}...")
if self.left:
self.left.dfs()
print(f"at {self.key}...")
if self.right:
self.right.dfs()
print(f"leaving {self.key}...")
# ইন্টারেক্টিভ ডেমো
root = None
while True:
cmd = input("কমান্ড (insert/dfs/quit): ").split()
if not cmd: continue
if cmd[0] == 'insert':
data = int(cmd[1])
node = BinaryTreeNode(data)
if cmd[2] == 'at':
root = node
elif cmd[2] == 'left':
parent = root.find(int(cmd[4])) if root else None
if parent: parent.insert_left(node)
elif cmd[2] == 'right':
parent = root.find(int(cmd[4])) if root else None
if parent: parent.insert_right(node)
elif cmd[0] == 'dfs':
if root:
print("DFS ট্রাভার্সাল:")
root.dfs()
elif cmd[0] == 'quit':
break
আউটপুট
কমান্ড (insert/dfs/quit): insert 5 at root কমান্ড (insert/dfs/quit): insert 6 left of 5 কমান্ড (insert/dfs/quit): insert 8 right of 5 কমান্ড (insert/dfs/quit): dfs DFS ট্রাভার্সাল: entering 5... entering 6... at 6... leaving 6... at 5... entering 8... at 8... leaving 8... leaving 5... কমান্ড (insert/dfs/quit): quit
ব্যাখ্যা
প্রি-অর্ডার স্টাইল: এন্টার -> লেফট -> অ্যাট (মিডিল) -> রাইট -> লিভিং।
রিকার্সিভ কল স্ট্যাক কল স্ট্যাক হিসেবে কাজ করে।
এন্টার/অ্যাট/লিভিং প্রিন্ট দিয়ে ট্রাভার্সাল ফ্লো ভিজ্যুয়ালাইজ।
ইন-অর্ডার/পোস্ট-অর্ডার এর জন্য প্রিন্ট স্টেটমেন্টের অর্ডার বদলান।
