কিউ ব্যবহার করে ব্রেডথ-ফার্সট সার্চ (BFS) ট্রাভার্সাল ইমপ্লিমেন্ট করা হয়, যা লেভেল বাই লেভেল নোড ভিজিট করে।
উদাহরণ
class TreeNode:
def __init__(self, data):
self.key = data
self.children = []
def add_child(self, node):
self.children.append(node)
def find_node(self, key):
if self.key == key:
return self
for child in self.children:
found = child.find_node(key)
if found:
return found
return None
def bfs(self):
queue = [self]
while queue:
node = queue.pop(0)
print(node.key, end=" ")
for child in node.children:
queue.append(child)
# ইন্টারেক্টিভ ডেমো
root = None
while True:
cmd = input("কমান্ড (add/bfs/quit): ").split()
if not cmd: continue
if cmd[0] == 'add':
data = int(cmd[1])
node = TreeNode(data)
if cmd[2] == 'at':
root = node
elif cmd[2] == 'below':
parent_key = int(cmd[3])
parent = root.find_node(parent_key) if root else None
if parent:
parent.add_child(node)
elif cmd[0] == 'bfs':
if root:
print("BFS ট্রাভার্সাল:", end=" ")
root.bfs()
print()
elif cmd[0] == 'quit':
break
আউটপুট
কমান্ড (add/bfs/quit): add 6 at root কমান্ড (add/bfs/quit): add 4 below 6 কমান্ড (add/bfs/quit): add 9 below 4 কমান্ড (add/bfs/quit): bfs BFS ট্রাভার্সাল: 6 4 9 কমান্ড (add/bfs/quit): quit
ব্যাখ্যা
কিউতে রুট দিয়ে শুরু।
পপ করে নোড প্রসেস, চাইল্ডদের কিউতে পুশ।
FIFO অর্ডার নিশ্চিত করে লেভেল বাই লেভেল ভিজিট।
collections.dequeব্যবহার করলে O(1) পপ/অ্যাপেন্ড।
