Tree हेर्ने तरिका: pre, in र post order
सातवटा सङ्ख्याको binary search tree बनाएर यसलाई चार तरिकाले हिँडाउनुहोस्: in-order, pre-order, post-order र तहैपिच्छे। उही सङ्ख्याका चारवटा फरक क्रम, in-order किन मिलेर आउँछ, र queue ले tree लाई लहरै-लहर कसरी हिँडाउँछ, हेर्नुहोस्।
मूल अवधारणा
Traversal ले tree को हरेक node एक पटक हेर्छ; pre-order ले node लाई यसका छोराछोरीअघि, in-order ले बायाँ र दायाँ छोराछोरीबीच, post-order ले तिनपछि, र level order ले queue सँग लहरै-लहर हेर्छ
पाठ: Data structure
Tree लाई print वा copy गर्न प्रोग्रामले हरेक node एक पटक हेर्नुपर्छ, र त्यसका एकभन्दा बढी तरिका छन्। हरेक तरिका एउटा सानो recursive नियम हो। Pre-order ले पहिले node, त्यसपछि बायाँ भाग, अनि दायाँ भाग हेर्छ: root पहिले आउँछ, जुन tree copy गर्ने क्रम हो। In-order ले पहिले बायाँ भाग, त्यसपछि node, अनि दायाँ भाग हेर्छ: Binary: 0 र 1 दुई अङ्क मात्र प्रयोग गरेर गन्ने तरिका। कम्प्युटरले सबै कुरा यसरी राख्छ। सबै मुख्य शब्द search tree मा यसले सङ्ख्या सानोदेखि ठूलोसम्म print गर्छ। Post-order ले बायाँ भाग, दायाँ भाग, अनि अन्त्यमा node हेर्छ: छोराछोरी सधैँ अभिभावकअघि आउँछन्, जुन tree सुरक्षित रूपमा मेटाउने क्रम हो। Level order फरक छ: यसले queue प्रयोग गरेर tree लाई root बाट तलतिर, बायाँबाट दायाँ, लहरै-लहर हेर्छ।
के सिक्नुहुनेछ
- Binary tree लाई pre-order, in-order र post-order मा हिँडाउनुहोस्।
- Binary search tree को in-order किन मिलेर आउँछ, व्याख्या गर्नुहोस्।
- Queue प्रयोग गरेर tree लाई तहैपिच्छे हिँडाउनुहोस्।
- चलाउनुअघि हिँडाइको क्रम अनुमान गर्नुहोस्।
सुरु गर्नुअघि
- Binary search tree भनेको के हो (साना सङ्ख्या बायाँ, ठूला दायाँ) थाहा हुनुपर्छ।
सामग्री
- Tree कोर्न र हेराइको क्रम लेख्न कागज
उपकरण
- केही पनि चाहिँदैन
विधि
- In-order हिँडाइ चलाएर output पढ्नुहोस्।
- उही tree को pre-order र post-order चलाउनुहोस्।
- Level-order चलाएर queue हेर्नुहोस्।
- अभ्यासका challenge हरूको उत्तर दिनुहोस्।