জেনারেল ট্রিতে পোস্ট-অর্ডার (চাইল্ডর először, তারপর রুট) DFS ট্রাভার্সাল ইমপ্লিমেন্ট করা হয়।
উদাহরণ
class TreeNode:
def __init__(self, key):
self.key = key
self.children = []
def add_child(self, node):
self.children.append(node)
def find(self, key):
if self.key == key:
return self
for child in self.children:
found = child.find(key)
if found:
return found
return None
def postorder(self):
for child in self.children:
child.postorder()
print(self.key, end=" ")
# ইন্টারেক্টিভ ডেমো
root = None
while True:
cmd = input("কমান্ড (add/dfs/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 = root.find(int(cmd[3])) if root else None
if parent:
parent.add_child(node)
elif cmd[0] == 'dfs':
if root:
print("পোস্ট-অর্ডার:", end=" ")
root.postorder()
print()
elif cmd[0] == 'quit':
break
আউটপুট
কমান্ড (add/dfs/quit): add 5 at root কমান্ড (add/dfs/quit): add 9 below 5 কমান্ড (add/dfs/quit): add 2 below 9 কমান্ড (add/dfs/quit): dfs পোস্ট-অর্ডার: 2 9 5 কমান্ড (add/dfs/quit): quit
ব্যাখ্যা
পোস্ট-অর্ডার: সব চাইল্ড প্রসেস -> তারপর নিজের নোড।
রিকার্সিভই সবচেয়ে সহজ পোস্ট-অর্ডার ইমপ্লিমেন্টেশন।
এক্সপ্রেশন ট্রি ইভ্যালুয়েশন, ডিলিশন ইত্যাদিতে পোস্ট-অর্ডার লাগে।
ইটারেটিভ ভার্সনে দুটি স্ট্যাক বা ভিজিটেড ফ্ল্যাগ দরকার।
