बीएसटी में सभी नोड्स पर जाने का एक से अधिक तरीका है।

बाइनरी ट्री प्रोग्रामिंग में सबसे अधिक उपयोग की जाने वाली डेटा संरचनाओं में से एक है। एक बाइनरी सर्च ट्री (बीएसटी) नोड्स (पैरेंट नोड और चाइल्ड) के रूप में डेटा के भंडारण की अनुमति देता है नोड) इस प्रकार है कि बायां चाइल्ड नोड मूल नोड से छोटा है और दायां चाइल्ड नोड है अधिक.

बाइनरी सर्च ट्री कुशल ट्रैवर्सल, खोज, विलोपन और सम्मिलन संचालन की अनुमति देते हैं। इस लेख में, आप बाइनरी सर्च ट्री को पार करने के तीन तरीकों के बारे में जानेंगे: प्रीऑर्डर ट्रैवर्सल, इनऑर्डर ट्रैवर्सल और पोस्टऑर्डर ट्रैवर्सल।

इनऑर्डर ट्रैवर्सल

इनऑर्डर ट्रैवर्सल ए के नोड्स को ट्रैवर्स करने की प्रक्रिया है बाइनरी सर्च ट्री बाएँ उप-वृक्ष को पुनरावर्ती रूप से संसाधित करके, फिर रूट नोड को संसाधित करके, और अंत में दाएँ उप-वृक्ष को पुनरावर्ती रूप से संसाधित करके। चूंकि यह आरोही मूल्य क्रम में नोड्स को संसाधित करता है, इसलिए तकनीक को इनऑर्डर ट्रैवर्सल कहा जाता है।

ट्रैवर्सिंग ट्री डेटा संरचना में प्रत्येक नोड पर ठीक एक बार जाने की प्रक्रिया है।

इनऑर्डर ट्रैवर्सल का एल्गोरिदम

BST के सभी नोड्स को पार करने के लिए दोहराएँ:

instagram viewer
  1. बाएँ उपवृक्ष को पुनरावर्ती रूप से पार करें।
  2. रूट नोड पर जाएँ.
  3. दाएँ उपवृक्ष को पुनरावर्ती रूप से पार करें।

इनऑर्डर ट्रैवर्सल का विज़ुअलाइज़ेशन

एक दृश्य उदाहरण बाइनरी सर्च ट्री ट्रैवर्सल को समझाने में मदद कर सकता है। यह आंकड़ा एक उदाहरण बाइनरी सर्च ट्री के इनऑर्डर ट्रैवर्सल को दर्शाता है:

इस बाइनरी सर्च ट्री में, 56 रूट नोड है। सबसे पहले, आपको बाएँ सबट्री 32, फिर रूट नोड 56, और फिर दाएँ सबट्री 62 को पार करना होगा।

उप-वृक्ष 32 के लिए, पहले बाएँ उप-वृक्ष 28 को पार करें। इस उपवृक्ष में कोई संतान नहीं है, इसलिए अगला 32 नोड पार करें। इसके बाद, दाएँ उपवृक्ष, 44 को पार करें, जिसकी कोई संतान नहीं है। इसलिए 32 पर निहित उपवृक्ष के लिए ट्रैवर्सल का क्रम 28 -> 32 -> 44 है।

इसके बाद, रूट नोड, 56 पर जाएँ।

फिर, 62 पर निहित, दाएँ उपवृक्ष को पार करें। 58 पर निहित, इसके बाएँ उपवृक्ष को पार करके प्रारंभ करें। इसकी कोई संतान नहीं है, इसलिए अगले 62 नोड पर जाएँ। अंत में, दाएँ उपवृक्ष, 88 को पार करें, जिसकी कोई संतान नहीं है।

तो एल्गोरिथ्म निम्नलिखित क्रम में पेड़ के नोड्स पर जाता है:

28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88

इनऑर्डर ट्रैवर्सल का अनुप्रयोग

बढ़ते क्रम में नोड तत्वों के मान प्राप्त करने के लिए आप इनऑर्डर ट्रैवर्सल का उपयोग कर सकते हैं। घटते क्रम में मान प्राप्त करने के लिए, बस प्रक्रिया को उल्टा करें: दाएं उपट्री पर जाएं, फिर रूट नोड पर, फिर बाएं उपवृक्ष पर जाएं। आप किसी अभिव्यक्ति वृक्ष की उपसर्ग अभिव्यक्ति को खोजने के लिए एल्गोरिदम का उपयोग कर सकते हैं।

प्रीऑर्डर ट्रैवर्सल

प्रीऑर्डर ट्रैवर्सल इनऑर्डर के समान है, लेकिन यह बाएं उपट्री को पुनरावर्ती रूप से संसाधित करने से पहले रूट नोड को संसाधित करता है, फिर दाएं उपट्री को संसाधित करता है।

प्रीऑर्डर ट्रैवर्सल का एल्गोरिदम

BST के सभी नोड्स को पार करने के लिए दोहराएँ:

  1. रूट नोड पर जाएँ.
  2. बाएँ उपवृक्ष को पुनरावर्ती रूप से पार करें।
  3. दाएँ उपवृक्ष को पुनरावर्ती रूप से पार करें।

प्रीऑर्डर ट्रैवर्सल का विज़ुअलाइज़ेशन

निम्नलिखित आंकड़ा बाइनरी सर्च ट्री के प्रीऑर्डर ट्रैवर्सल को दर्शाता है:

इस बाइनरी सर्च ट्री में, रूट नोड, 56 को संसाधित करके प्रारंभ करें। फिर बाएँ उपवृक्ष, 32 को पार करें, उसके बाद दाएँ उपवृक्ष, 62 को पार करें।

बाएं उपट्री के लिए, रूट नोड पर मान को संसाधित करें, 32। इसके बाद, बाएँ उपवृक्ष, 28, को पार करें, फिर अंत में दाएँ उपवृक्ष, 44 को पार करें। यह 32 पर निहित बाएं उपवृक्ष का ट्रैवर्सल पूरा करता है। ट्रैवर्सल निम्नलिखित क्रम में होता है: 56 -> 32 -> 28 -> 44।

सही सबट्री के लिए, रूट नोड पर मान को संसाधित करें, 62। इसके बाद, बाएँ उपवृक्ष, 58, को पार करें, फिर अंत में दाएँ उपवृक्ष, 88 को पार करें। फिर, किसी भी नोड में कोई संतान नहीं है, इसलिए इस बिंदु पर ट्रैवर्सल पूरा हो गया है।

आपने निम्नलिखित क्रम में पूरे पेड़ को पार कर लिया है:

56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88

प्रीऑर्डर ट्रैवर्सल का अनुप्रयोग

आप सबसे आसानी से पेड़ की एक प्रति बनाने के लिए प्रीऑर्डर ट्रैवर्सल का उपयोग कर सकते हैं।

पोस्टऑर्डर ट्रैवर्सल

पोस्टऑर्डर ट्रैवर्सल एक बाइनरी सर्च ट्री के नोड्स को पुनरावर्ती रूप से ट्रैवर्स करने की प्रक्रिया है बाएं उप-वृक्ष को संसाधित करना, फिर दाएँ उप-वृक्ष को पुनरावर्ती रूप से संसाधित करना, और अंत में प्रसंस्करण करना रूट नोड. चूँकि यह दोनों उपवृक्षों के बाद रूट नोड को संसाधित करता है, इस विधि को पोस्टऑर्डर ट्रैवर्सल कहा जाता है।

पोस्टऑर्डर ट्रैवर्सल का एल्गोरिदम

BST के सभी नोड्स को पार करने के लिए दोहराएँ:

  1. बाएँ उपवृक्ष को पुनरावर्ती रूप से पार करें।
  2. दाएँ उपवृक्ष को पुनरावर्ती रूप से पार करें।
  3. रूट नोड पर जाएँ.

पोस्टऑर्डर ट्रैवर्सल का विज़ुअलाइज़ेशन

निम्नलिखित आंकड़ा बाइनरी सर्च ट्री के पोस्टऑर्डर ट्रैवर्सल को दर्शाता है:

बाएँ उपवृक्ष, 32, फिर दाएँ उपवृक्ष, 62 को पार करके प्रारंभ करें। रूट नोड को संसाधित करके समाप्त करें, 56।

उप-वृक्ष को संसाधित करने के लिए, 32 पर निहित, इसके बाएँ उप-वृक्ष, 28 को पार करें। चूँकि 28 की कोई संतान नहीं है, इसलिए दाएँ उपवृक्ष 44 पर जाएँ। प्रक्रिया 44 चूँकि इसकी भी कोई संतान नहीं है। अंत में, रूट नोड, 32 को प्रोसेस करें। आपने इस उपवृक्ष को 28 -> 44 -> 32 क्रम में पार किया है।

58 -> 88 → 62 क्रम में नोड्स पर जाने के लिए उसी दृष्टिकोण का उपयोग करके सही उपट्री को संसाधित करें।

अंत में, रूट नोड, 56 को संसाधित करें। आप इस क्रम में पूरे पेड़ को पार करेंगे:

28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56

पोस्टऑर्डर ट्रैवर्सल का अनुप्रयोग

आप किसी पेड़ को पत्ती से जड़ तक हटाने के लिए पोस्टऑर्डर ट्रैवर्सल का उपयोग कर सकते हैं। आप इसका उपयोग किसी एक्सप्रेशन ट्री के पोस्टफ़िक्स एक्सप्रेशन को खोजने के लिए भी कर सकते हैं।

नोड पर जाने से पहले किसी निश्चित नोड के सभी लीफ नोड्स पर जाने के लिए, आप पोस्टऑर्डर ट्रैवर्सल तकनीक का उपयोग कर सकते हैं।

बाइनरी सर्च ट्री ट्रैवर्सल की समय और स्थान जटिलता

तीनों ट्रैवर्सल तकनीकों की समय जटिलता है पर), कहाँ एन का आकार है द्विआधारी वृक्ष. सभी ट्रैवर्सल तकनीकों की स्थानिक जटिलता है ओह), कहाँ एच बाइनरी ट्री की ऊंचाई है.

बाइनरी ट्री का आकार उस ट्री में नोड्स की संख्या के बराबर होता है। बाइनरी ट्री की ऊंचाई पेड़ की जड़ नोड और उसके सबसे दूर पत्ती नोड के बीच किनारों की संख्या है।

बाइनरी सर्च ट्री ट्रैवर्सल के लिए पायथन कोड

नीचे सभी तीन बाइनरी सर्च ट्री ट्रैवर्सल करने के लिए एक पायथन प्रोग्राम है:

# Node class is used to create individual nodes
# of the Binary Search Tree (BST)
classNode:
def__init__(self, element):
self.left = None
self.right = None
self.value = element
# Function to perform the inorder tree traversal
definorder(root):
 if root:
# Traverse left subtree
inorder(root.left)


# Traverse root
print(str(root.value) + ", ", end='')


# Traverse right subtree
inorder(root.right)


# Function to perform the postorder tree traversal
defpostorder(root):
 if root:
# Traverse left subtree
postorder(root.left)


# Traverse right subtree
postorder(root.right)


# Traverse root
print(str(root.value) + ", ", end='')


# Function to perform the preorder tree traversal
defpreorder(root):
 if root:
# Traverse root
print(str(root.value) + ", ", end='')


# Traverse left subtree
preorder(root.left)


# Traverse right subtree
preorder(root.right)
# Creating nodes of the tree
root = Node(56)
root.left = Node(32)
root.right = Node(62)
root.left.left = Node(28)
root.left.right = Node(44)
root.right.left = Node(58)
root.right.right = Node(88)
print("Inorder Traversal of BST: ")
inorder(root)
print()
print("Preorder Traversal of BST: ")
preorder(root)
print()
print("Postorder Traversal of BST: ")
postorder(root)

इस प्रोग्राम को निम्नलिखित आउटपुट उत्पन्न करना चाहिए:

प्रोग्रामर्स के लिए एल्गोरिदम अवश्य जानना चाहिए

एल्गोरिदम प्रत्येक प्रोग्रामर की यात्रा का एक अनिवार्य हिस्सा हैं। एक प्रोग्रामर के लिए एल्गोरिदम में पारंगत होना महत्वपूर्ण है। आपको कुछ एल्गोरिदम से परिचित होना चाहिए जैसे मर्ज सॉर्ट, क्विक सॉर्ट, बाइनरी सर्च, लीनियर सर्च, डेप्थ फर्स्ट सर्च इत्यादि।