पायथन - ट्री ट्रैवर्सल एल्गोरिदम
ट्रावर्सल एक पेड़ के सभी नोड्स का दौरा करने की एक प्रक्रिया है और उनके मूल्यों को भी मुद्रित कर सकता है। क्योंकि, सभी नोड्स किनारों (लिंक) के माध्यम से जुड़े होते हैं, हम हमेशा रूट (हेड) नोड से शुरू करते हैं। यही है, हम एक पेड़ में एक नोड को बेतरतीब ढंग से एक्सेस नहीं कर सकते हैं। एक पेड़ को पार करने के लिए तीन तरीके हैं -
- इन-ऑर्डर ट्रैवर्सल
- ट्रैवर्सल को प्री-ऑर्डर करें
- पोस्ट-ऑर्डर ट्रैवर्सल
इन-ऑर्डर ट्रैवर्सल
इस त्रैमासिक विधि में, बाएं उपप्रकार का दौरा पहले किया जाता है, फिर मूल और बाद में दाएं उप-पेड़। हमें हमेशा याद रखना चाहिए कि प्रत्येक नोड एक उपप्रकार का प्रतिनिधित्व कर सकता है।
नीचे दिए गए अजगर कार्यक्रम में, हम नोड नोड के लिए रूट नोड के साथ-साथ बाएं और दाएं नोड्स बनाने के लिए नोड क्लास का उपयोग करते हैं। फिर हम पेड़ में डेटा जोड़ने के लिए एक सम्मिलित फ़ंक्शन बनाते हैं। अंत में एक खाली सूची बनाकर और बाईं ओर पहले नोड या मूल नोड को जोड़कर इनवर्टर ट्रैवर्सल लॉजिक लागू किया जाता है। अंत में इनवर्टर ट्रैवर्सल को पूरा करने के लिए बाएं नोड को जोड़ा जाता है। कृपया ध्यान दें कि यह प्रक्रिया प्रत्येक उप-वृक्ष के लिए दोहराई जाती है जब तक कि सभी नोड्स का पता नहीं लगाया जाता है।
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Inorder traversal
# Left -> Root -> Right
def inorderTraversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left)
res.append(root.data)
res = res + self.inorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))
जब उपरोक्त कोड निष्पादित किया जाता है, तो यह निम्नलिखित परिणाम उत्पन्न करता है -
[10, 14, 19, 27, 31, 35, 42]
ट्रैवर्सल को प्री-ऑर्डर करें
इस ट्रैवर्सल विधि में, रूट नोड का दौरा पहले किया जाता है, फिर बाएं सबट्री और अंत में राइट सबट्री।
नीचे दिए गए अजगर कार्यक्रम में, हम नोड नोड के लिए रूट नोड के साथ-साथ बाएं और दाएं नोड्स बनाने के लिए नोड क्लास का उपयोग करते हैं। फिर हम पेड़ में डेटा जोड़ने के लिए एक सम्मिलित फ़ंक्शन बनाते हैं। अंत में प्री-ऑर्डर ट्रैवर्सल लॉजिक एक खाली सूची बनाकर और रूट नोड को पहले बाएं नोड द्वारा जोड़कर लागू किया जाता है। अंत में प्री-ऑर्डर ट्रैवर्सल को पूरा करने के लिए दायां नोड जोड़ा जाता है। कृपया ध्यान दें कि यह प्रक्रिया प्रत्येक उप-वृक्ष के लिए दोहराई जाती है जब तक कि सभी नोड्स का पता नहीं लगाया जाता है।
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Preorder traversal
# Root -> Left ->Right
def PreorderTraversal(self, root):
res = []
if root:
res.append(root.data)
res = res + self.PreorderTraversal(root.left)
res = res + self.PreorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))
जब उपरोक्त कोड निष्पादित किया जाता है, तो यह निम्नलिखित परिणाम उत्पन्न करता है -
[27, 14, 10, 19, 35, 31, 42]
पोस्ट-ऑर्डर ट्रैवर्सल
इस ट्रैवर्सल विधि में, रूट नोड को अंतिम बार देखा जाता है, इसलिए नाम। पहले हम बाएं सबट्री को फंसाते हैं, फिर राइट सबट्री और आखिर में रूट नोड को।
नीचे दिए गए अजगर कार्यक्रम में, हम नोड नोड के लिए रूट नोड के साथ-साथ बाएं और दाएं नोड्स बनाने के लिए नोड क्लास का उपयोग करते हैं। फिर हम पेड़ में डेटा जोड़ने के लिए एक सम्मिलित फ़ंक्शन बनाते हैं। अंत में पोस्ट-ऑर्डर ट्रैवर्सल तर्क को एक खाली सूची बनाकर और बाएं नोड को जोड़कर पहले दाएं नोड द्वारा लागू किया जाता है। आखिर में पोस्ट-ऑर्डर ट्रैवर्सल को पूरा करने के लिए रूट या पैरेंट नोड जोड़ा जाता है। कृपया ध्यान दें कि यह प्रक्रिया प्रत्येक उप-वृक्ष के लिए दोहराई जाती है जब तक कि सभी नोड्स का पता नहीं लगाया जाता है।
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal(self, root):
res = []
if root:
res = self.PostorderTraversal(root.left)
res = res + self.PostorderTraversal(root.right)
res.append(root.data)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))
जब उपरोक्त कोड निष्पादित किया जाता है, तो यह निम्नलिखित परिणाम उत्पन्न करता है -
[10, 19, 14, 31, 42, 35, 27]