कितने traversals एक BST के निर्माण के लिए जाना जाने की जरूरत है

Question

मैं किसी भी एक ट्रेवर्सल (pre, post या in-order), या इनमें से किसी दो के संयोजन से एक Binary Search Tree निर्माण के बारे में विभिन्न स्थलों पर लेख की एक संख्या से बहुत उलझन में हूँ । उदाहरण के लिए, this पृष्ठ पर, यह कहता है कि pre, post या level ऑर्डर ट्रैवर्सल in-order ट्रैवर्सल के साथ, कोई BST बना सकता है। लेकिन here और there, वे हमें को pre-order से अकेले बनाने के लिए दिखाते हैं। इसके अलावा, here वे हमें pre और post-order ट्रैवर्सल से BST बनाने का तरीका दिखाते हैं। किसी अन्य साइट पर, मुझे post-order ट्रैवर्सल से BST बनाने के लिए एक समाधान मिला।

अब मुझे पता है कि inorder और pre-order ट्रैवर्सल दिया गया है, यह BST विशिष्ट रूप से संभव है। के रूप में, पहले लिंक मैं प्रदान की संबंध है, हालांकि वे कहते हैं कि हम pre-order और post-order से BST निर्माण कर सकते हैं नहीं, मैं सिर्फ post-order सरणी क्रमबद्ध नहीं कर सकते अपनी inorder ट्रेवर्सल प्राप्त करने के लिए, और उसके बाद का उपयोग करें कि और pre-order सरणी के लिए फार्म BST? क्या यह 4 वें लिंक में समाधान के समान होगा, या अलग? और pre-order केवल दिए गए, मैं इसे in-order प्राप्त करने के लिए सॉर्ट कर सकता हूं, फिर BST प्राप्त करने के लिए उस और pre-order का उपयोग करें। फिर, क्या लिंक 2 और 3 पर समाधान से अलग होना चाहिए?

विशेष रूप से, BST विशिष्ट रूप से उत्पन्न करने के लिए पर्याप्त क्या है? यदि शिक्चर की आवश्यकता नहीं है, तो मैं इसे आसानी से in-order ट्रैवर्सल प्राप्त करने के लिए सॉर्ट कर सकता हूं, और इसे संभवतः एन से संभव BST एस में से एक का निर्माण कर सकता हूं।

Answer 1

बीएसटी बनाने के लिए आपको केवल एक (इन-ऑर्डर नहीं) ट्रैवर्सल की आवश्यकता है।

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

तो, यह जानकारी कि पेड़ बीएसटी है, इसमें तत्वों के साथ (यहां तक ​​कि अनियंत्रित) एक इन-ऑर्डर ट्रैवर्सल के बराबर है।

बोनस: एक सामान्य पेड़ के लिए एक ट्रैवर्सल पर्याप्त क्यों नहीं है, (जानकारी के बिना यह बीएसटी है)?
उत्तर: मान लीजिए कि हमारे पास n विशिष्ट तत्व हैं। n! इन n तत्वों के लिए संभावित सूचियां हैं, हालांकि - पेड़ों की संभावित संख्या बहुत बड़ी है (एन * तत्वों के लिए संभावित पेड़ सभी क्षय वाले पेड़ हैं, जैसे node.right = null प्रत्येक नोड में, इस प्रकार पेड़ वास्तव में एक सूची है दाईं ओर। n! ऐसे पेड़ हैं, और एक अन्य एन पेड़ जहां हमेशा node.left = null) इस प्रकार, कबूतर छेद सिद्धांत से - कम से कम एक सूची है जो 2 पेड़ उत्पन्न करती है, इस प्रकार हम पेड़ को एक ही ट्रैवर्सल से पुनर्निर्माण नहीं कर सकते हैं। (QED)

Answer 2

यदि बीएसटी के नोड्स के मान दिए गए हैं तो केवल एक ट्रैवर्सल पर्याप्त है क्योंकि शेष डेटा नोड्स के मानों द्वारा प्रदान किया जाता है।लेकिन यदि मूल्य अज्ञात हैं, तो मेरी समझ के अनुसार, एक ट्रैवर्सल से एक अद्वितीय बीएसटी बनाना संभव नहीं है। हालांकि, मैं सुझावों के लिए खुला हूं।