बाइनरी ट्री: संरचना और ट्रैवर्सल

शाखाओं वाली संरचना, क्रमबद्ध करने का नियम नहीं

लिंक्ड लिस्ट के नोड में एक next लिंक था। बाइनरी ट्री (binary tree) के नोड में दो नाम वाले संतान-स्थान होते हैं: बायाँ (left) और दायाँ (right)। इनमें से कोई भी खाली हो सकता है। इनके नाम महत्वपूर्ण हैं: केवल बाईं संतान वाला नोड और केवल दाईं संतान वाला नोड अलग क्रम वाली संरचनाएँ हैं। “बाइनरी” का अर्थ अधिकतम दो संतान है; इससे डेटा के संख्यात्मक क्रम का कोई नियम नहीं बनता।

आप रूट, पत्ती, गहराई और ऊँचाई पहचानेंगे, आकार की सामान्य शर्तों का अंतर समझेंगे और प्रीऑर्डर, इनऑर्डर तथा पोस्टऑर्डर का ट्रेस बनाएँगे। यह पाठ सीमित लिंक्ड लिस्ट निरूपण और पहले पढ़े रिकर्शन को जोड़ता है। पहले “सिंगली लिंक्ड लिस्ट: नोड, लिंक और ट्रैवर्सल” पढ़ें तथा हर रिकर्सिव कॉल के अपने आर्ग्युमेंट, आधार स्थिति और बचे काम पर लौटना याद करें। ऐरे, वैध इंडेक्स, लूप/शर्तें और C फ़ंक्शन भी आने चाहिए। रिकॉर्ड और वैधता-जाँच की ज़रूरी नई बातें नीचे समझाई गई हैं।

यह शुरुआती ट्री पाठ है। BST खोज, हीप क्रियाएँ, संतुलन बनाना, ग्राफ़ ट्रैवर्सल, ट्रैवर्सल से ट्री दोबारा बनाना और पूरा GATE CS पाठ्यक्रम इसके विषय नहीं हैं। अगले BST और हीप पाठ अलग नियम जोड़ेंगे। इस उदाहरण में BST का क्रम जानबूझकर नहीं रखा गया है, ताकि ट्री का आकार और क्रमबद्ध डेटा एक बात न समझे जाएँ।

संरचना की शब्दावली

गैर-खाली रूटेड ट्री का एक रूट (root) होता है, जिसका कोई जनक (parent) नहीं होता। हर दूसरे नोड का ठीक एक parent होता है। संतान-लिंक में चक्र नहीं होता और रूट से हर सदस्य तक पहुँचा जा सकता है। parent और child को जोड़ने वाला एक लिंक एक एज (edge) है। n > 0 नोड वाले ट्री में n - 1 एज हैं: रूट के अलावा हर नोड के पास parent से आने वाली ठीक एक एज है।

• पत्ती (leaf) की कोई संतान नहीं होती। एक या दो संतान वाला नोड आंतरिक नोड (internal node) है।
• किसी नोड पर आधारित सबट्री (subtree) में वह नोड और उसके नीचे पहुँचे सभी नोड शामिल हैं। खाली संतान-स्थान एक खाली सबट्री है।
• किसी नोड की गहराई (depth) रूट से उस तक की एज की संख्या है। रूट की depth 0 है।
• किसी नोड की ऊँचाई (height) उससे नीचे किसी पत्ती तक के सबसे लंबे रास्ते की एज की संख्या है। पत्ती की height 0 है। ट्री की height उसके रूट की height है।
• हम खाली ट्री की height को -1 परिभाषित करते हैं। यह उपयोगी परिपाटी है; किसी वास्तविक रास्ते की लंबाई ऋणात्मक होने का दावा नहीं। कुछ स्रोत एज के बजाय नोड गिनते हैं; उत्तर देने से पहले परिपाटी पहचानें।

यहाँ “स्तर d” का अर्थ depth d है। इसलिए गैर-खाली height-h ट्री में 0 से h तक कुल h + 1 स्तर हैं। depth नोड से ऊपर रूट तक देखती है; height नीचे सबसे दूर पत्ती तक। दोनों एक नहीं हैं। मेमोरी में parent का child के ठीक पहले होना आवश्यक नहीं है। समान डेटा वाले अलग नोड भी हो सकते हैं।

Full, complete और perfect अलग आकार-शर्तें हैं

इस पाठ में गैर-खाली बाइनरी ट्री के लिए ये परिभाषाएँ अपनाएँ:

• Full (proper/strict): हर नोड की शून्य या दो संतान हैं; किसी की ठीक एक संतान नहीं है।
• Complete: आखिरी स्तर को छोड़कर सभी स्तर पूरे भरे हैं; आखिरी स्तर बाएँ से दाएँ बिना अंतराल भरता है।
• Perfect: हर आंतरिक नोड की दो संतान हैं और सभी पत्तियों की depth समान है; यानी हर मौजूद स्तर पूरा भरा है।

जिस रूट की केवल बाईं पत्ती है, वह complete है, लेकिन full या perfect नहीं। जिस रूट की केवल दाईं पत्ती है, वह complete नहीं, क्योंकि बायाँ स्थान खाली छूटा है। दो पत्तियों वाला रूट तीनों शर्तें पूरी करता है। कोई full ट्री असंतुलित होकर complete होने में विफल हो सकता है: उदाहरण के लिए रूट की बाईं संतान पत्ती हो और दाईं संतान की दो पत्तियाँ हों। उसके सबसे गहरे स्तर पर बाईं ओर खाली स्थानों के बाद दाईं ओर नोड हैं।

ये केवल आकार की परिभाषाएँ हैं। डेटा के मान की तुलना करके इनकी जाँच न करें। BST में एक-संतान वाली लंबी शृंखला हो सकती है; बाइनरी हीप को complete आकार चाहिए। आगे की ये संरचनाएँ डेटा-क्रम के अपने नियम जोड़ती हैं।

सीमित इंडेक्स निरूपण

हम C11 के सात आरंभिक मानों वाले रिकॉर्ड का ऐरे इस्तेमाल करेंगे। हर रिकॉर्ड में value, left और right हैं। संतान-लिंक ऐरे का इंडेक्स या END = -1 है। फ़ील्ड तय करता है कि संख्या का क्या अर्थ है: डेटा -1 वैध है, लेकिन संतान-लिंक -1 का अर्थ कोई संतान नहीं। root भी इंडेक्स या END है। इस प्रोग्राम में हीप मेमोरी आवंटन, पॉइंटर वाले नोड का स्वामित्व, नोड हटाना या मेमोरी मुक्त करना नहीं है।

typedef struct { int value; int left; int right; } Node; तीन-फ़ील्ड रिकॉर्ड प्रकार को नाम देता है। nodes[4].left ऐरे रिकॉर्ड 4 का left फ़ील्ड चुनता है। {8, 1, 5} इसी क्रम में तीन फ़ील्ड को आरंभिक मान देता है। enum { CAP = 7, END = -1 }; पूर्णांक स्थिरांकों को नाम देता है।

भंडारण अनुबंध के अनुसार वास्तविक जीवित ऐरे में CAP रिकॉर्ड हों और सभी को आरंभिक मान मिले हों। सक्रिय नोड के इंडेक्स 0 से used - 1 तक हैं, जहाँ 0 <= used <= CAP है। सभी सक्रिय नोड एक ही रूटेड ट्री में होने चाहिए। अनुपयोगी रिकॉर्ड सदस्य नहीं हैं। हर सक्रिय नोड तक ठीक एक बार पहुँचना चाहिए: रूट तक root चर से और बाकी तक संतान-लिंक से। used = 0 होने पर root = END होना चाहिए।

वैधता-जाँच फ़ील्ड के ये नियम, चक्र, साझा संतान और न पहुँच सकने वाले सक्रिय नोड जाँचती है। लेकिन कॉलर ने सच में सात जीवित और आरंभिक मानों वाले रिकॉर्ड दिए हैं या नहीं, वह नहीं खोज सकती; यह कॉलर की ज़िम्मेदारी है। ट्रैवर्सल और height फ़ंक्शन को पहले से जाँच में स्वीकार किया गया ट्री चाहिए, जो उनके चलने के दौरान न बदले। वे मनमाने इंडेक्स के लिए अपने-आप वैधता नहीं जाँचते। सभी कॉल एक के बाद एक चलती हैं।

const Node nodes[] में C का ऐरे-पैरामीटर नियम लागू होता है: वह सभी रिकॉर्ड की कॉपी बनाए बिना मूल ऐरे से जुड़ता है और इस पैरामीटर से लिखने की अनुमति नहीं देता। इसके विपरीत int seen[] कॉलर के देखे-गए नोड के चिह्नों वाले ऐरे में लिखने देता है। पता फिर भी मान के रूप में कॉपी होता है; seen[at] बदलने पर साझा ऐरे का वही तत्व बदलता है। हर रिकर्सिव कॉल में चिह्नों की नई कॉपी नहीं बनती। पूरी वैधता-जाँच शुरू होने पर एक नया, शून्य से आरंभ किया हुआ seen ऐरे बनता है।

हल सहित ट्रेस 1: पहले लिंक पढ़ें, फिर संरचना पहचानें

root = 4 और used = 7 के लिए डेटा के नाम से ट्री बताएँ (यहाँ संयोग से सभी डेटा मान अलग हैं): रूट 8 की बाईं संतान 12 और दाईं 3 है। नोड 12 की संतान 2 और 5 हैं। नोड 5 की केवल बाईं संतान 9 है। नोड 3 की केवल दाईं संतान 7 है। लिंक इंडेक्स बताते हैं, इसलिए इंडेक्स 5 पर डेटा 3 है; डेटा 5 वाले नोड को ऐरे स्लॉट 5 न समझें।

depth 0 पर 8 है; depth 1 पर 12, 3; depth 2 पर 2, 5, 7; depth 3 पर 9 है। पत्तियाँ 2, 9 और 7 हैं। सात नोड और छह एज हैं। सबसे गहरा रास्ता 8 -> 12 -> 5 -> 9 है: तीन एज और चार नोड, इसलिए height = 3 है। दो नोड की एक-एक संतान होने से यह full नहीं है। नोड 3 की बाईं जगह खाली है, जबकि दाईं संतान 7 मौजूद है, इसलिए complete नहीं है। यह perfect भी नहीं है। फिर भी यह वैध बाइनरी ट्री है।

तीन depth-first क्रम

हर गैर-खाली सबट्री में बाएँ सबट्री को दाएँ से पहले रखें। वर्तमान नोड पर जाने का स्थान इन तीन में से चुनें:

• प्रीऑर्डर (preorder): नोड, बायाँ, दायाँ। किसी संतान-सबट्री से पहले वर्तमान नोड पर जाएँ।
• इनऑर्डर (inorder): बायाँ, नोड, दायाँ। दोनों संतान-सबट्री के बीच वर्तमान नोड पर जाएँ।
• पोस्टऑर्डर (postorder): बायाँ, दायाँ, नोड। दोनों संतान-सबट्री के बाद वर्तमान नोड पर जाएँ।

इस प्रोग्राम में नोड पर जाने का अर्थ उसका डेटा छापना है। END मिलने पर कुछ नहीं छपता और कॉल तुरंत लौटती है। ये हर पूरे सबट्री के रिकर्सिव नियम हैं; केवल दो सीधी संतान छापकर आगे बढ़ने के निर्देश नहीं। तीनों क्रम में फ़ंक्शन उस नोड की कॉल में प्रवेश करता है; अंतर यह है कि संतान-कॉल की तुलना में छपना कब होता है।

C11 का पूरा प्रोग्राम

तीनों आउटपुट क्रम का अनुमान लगाएँ। केवल वैध ट्री पर ट्रैवर्सल कॉल चलती हैं।

#include <stdio.h>

enum { CAP = 7, END = -1 };

typedef struct {
    int value;
    int left;
    int right;
} Node;

int check_visit(const Node nodes[], int used, int at, int seen[]) {
    if (at == END) {
        return 0;
    }
    if (at < 0 || at >= used || seen[at]) {
        return -1;
    }
    seen[at] = 1;
    int left_count = check_visit(nodes, used, nodes[at].left, seen);
    if (left_count < 0) {
        return -1;
    }
    int right_count = check_visit(nodes, used, nodes[at].right, seen);
    if (right_count < 0) {
        return -1;
    }
    return 1 + left_count + right_count;
}

int valid_tree(const Node nodes[], int used, int root) {
    if (used < 0 || used > CAP) {
        return 0;
    }
    int seen[CAP] = {0};
    int count = check_visit(nodes, used, root, seen);
    return count >= 0 && count == used;
}

void preorder(const Node nodes[], int at) {
    if (at == END) {
        return;
    }
    printf("%d ", nodes[at].value);
    preorder(nodes, nodes[at].left);
    preorder(nodes, nodes[at].right);
}

void inorder(const Node nodes[], int at) {
    if (at == END) {
        return;
    }
    inorder(nodes, nodes[at].left);
    printf("%d ", nodes[at].value);
    inorder(nodes, nodes[at].right);
}

void postorder(const Node nodes[], int at) {
    if (at == END) {
        return;
    }
    postorder(nodes, nodes[at].left);
    postorder(nodes, nodes[at].right);
    printf("%d ", nodes[at].value);
}

int height(const Node nodes[], int at) {
    if (at == END) {
        return -1;
    }
    int left_height = height(nodes, nodes[at].left);
    int right_height = height(nodes, nodes[at].right);
    if (left_height > right_height) {
        return 1 + left_height;
    }
    return 1 + right_height;
}

int main(void) {
    Node nodes[CAP] = {
        {2, END, END},
        {12, 0, 3},
        {9, END, END},
        {5, 2, END},
        {8, 1, 5},
        {3, END, 6},
        {7, END, END}
    };
    int used = 7;
    int root = 4;
    if (!valid_tree(nodes, used, root)) {
        return 1;
    }
    printf("pre: ");
    preorder(nodes, root);
    printf("\nin: ");
    inorder(nodes, root);
    printf("\npost: ");
    postorder(nodes, root);
    printf("\nheight: %d\n", height(nodes, root));
    return 0;
}

ठीक यही आउटपुट मिलता है (हर छपे नोड के बाद एक स्पेस है):

pre: 8 12 2 5 9 3 7 
in: 2 12 9 5 8 3 7 
post: 2 9 5 12 7 3 8 
height: 3

हल सहित ट्रेस 2: पूरे सबट्री का क्रम निकालें

पहले डेटा 12 वाले नोड का सबट्री देखें। बायाँ सबट्री पत्ती 2 है; दायाँ सबट्री 5 पर है, जिसकी बाईं पत्ती 9 है।

डेटा 8 वाले नोड के इनऑर्डर में पूरा बायाँ सबट्री पहले छपता है: 2, 12, 9, 5। उसके बाद ही 8 छपता है, फिर दाएँ सबट्री के 3, 7। इनऑर्डर हमेशा क्रमबद्ध नहीं होता: यह सामान्य बाइनरी ट्री है, BST नहीं।

डेटा 12 वाले नोड के पोस्टऑर्डर में उसकी कॉल पहले पत्ती 2 और फिर 5 के पूरे सबट्री का इंतज़ार करती है; उसके बाद 12 छपता है। रिकर्शन में बाकी बचे काम का विचार इस क्रम को समझाता है। हर गैर-खाली नोड हर ट्रैवर्सल में ठीक एक बार छपता है। खाली-संतान की कॉल नहीं छापती; “नोड पर जाने की गिनती” कुल फ़ंक्शन-कॉल की गिनती नहीं है। ट्रैवर्सल लिंक नहीं बदलता और रिकॉर्ड की भौतिक जगह नहीं बदलता।

हल सहित ट्रेस 3: वापसी के बाद ऊँचाई निकालें

height फ़ंक्शन खाली सबट्री पर -1 लौटाता है। किसी नोड पर दोनों संतान की height में बड़ी वाली में 1 जोड़ता है। दोनों संतान-कॉल लौटने के बाद ही जोड़ होता है।

नोड 3 की depth 1 और height 1 है; नोड 5 की depth 2 और height 1 है। पत्तियों की depth अलग हो सकती है, जबकि सभी की height 0 है। खाली आधार मान से एक-नोड का परिणाम 1 + max(-1,-1) = 0 आता है। अधिकतम सात नोड के वैध ट्री में height -1 (खाली) से 6 (सात-नोड शृंखला) तक है और सभी जोड़ छोटे दायरे में रहते हैं।

सुरक्षा और साझा चिह्नों से वैधता-जाँच

check_visit, END पर 0, वैध सबट्री पर नोड की संख्या और अमान्य संरचना पर -1 लौटाता है। यहाँ -1 जाँच का परिणाम है, रखे हुए डेटा से अलग। nodes[at] या seen[at] पढ़ने से पहले इंडेक्स जाँचता है। तार्किक OR || में शॉर्ट-सर्किट होता है: at < 0 या at >= used होने पर आगे का seen[at] नहीं पढ़ा जाता। नीचे जाने से पहले चिह्न लगाया जाता है। वही इंडेक्स फिर मिलने पर चक्र या दो parent की साझा संतान अस्वीकार होती है। हर स्वीकार किया गया वास्तविक-नोड प्रवेश किसी नए इंडेक्स पर चिह्न लगाता है; इसलिए समाप्त होने या अस्वीकार करने से पहले ऐसे प्रवेश अधिकतम used हो सकते हैं।

बाईं और दाईं गिनती अलग-अलग कॉल से मिलती हैं; किसी संतान की जाँच विफल हो तो तुरंत लौटते हैं। सफल कुल गिनती सात से अधिक नहीं हो सकती। बाहरी जाँच count == used भी देखती है, इसलिए अलग पड़े सक्रिय नोड चुपचाप अनदेखे नहीं होते। अमान्य root, सीमा के बाहर संतान, दोहराई संतान, खुद को लिंक या अलग पड़ा सक्रिय रिकॉर्ड विफलता देता है। वैध खाली निरूपण में used और लौटाई गिनती दोनों शून्य हैं।

ट्रैवर्सल की आधार स्थितियाँ रिकॉर्ड पढ़ने से पहले END जाँचती हैं। वैध संरचना में चक्र या साझा नोड नहीं हैं, इसलिए हर नोड पर एक बार जाते हैं और रिकर्सिव उतरना समाप्त होता है। पहले वैधता जाँचना अनिवार्य है: unchecked चक्र पर सीधे preorder चलाएँ, तो केवल END की आधार-जाँच सुरक्षा नहीं देगी। यह छोटा सीमित उदाहरण है, मनमाने बड़े ट्री के लिए सुरक्षित रिकर्शन-गहराई की गारंटी नहीं।

void वाले ट्रैवर्सल फ़ंक्शन कोई मान नहीं लौटाते; return; खाली-संतान की कॉल समाप्त करता है। int seen[CAP] = {0} सातों चिह्न शून्य करता है। && तार्किक AND है; ! शून्य की जाँच है। <stdio.h> printf की घोषणा देता है; %d पूर्णांक छापता है और \n नई पंक्ति शुरू करता है। डेटा के मान केवल पढ़े और छापे जाते हैं; न उन्हें जोड़ते हैं, न क्रम तय करने के लिए उनकी तुलना करते हैं।

एक सटीक उपमा

लेबल वाला फ़ोल्डर सोचें, जिसमें बायाँ और दायाँ उपफ़ोल्डर हो सकता है। हर लेबल लिखने के लिए किसी फ़ोल्डर को उसके उपफ़ोल्डर से पहले, बाएँ और दाएँ के बीच या दोनों के बाद लिख सकते हैं। खाली उपफ़ोल्डर-स्थान का कोई लेबल नहीं लिखते। यह तीन रिकर्सिव visit-स्थान समझाता है। उपमा में मानते हैं कि हर उपफ़ोल्डर का एक ही parent है और लिंक से फ़ोल्डर खुद के भीतर नहीं आता; वास्तविक शॉर्टकट या साझा फ़ोल्डर के लिए अलग नियम चाहिए। “बायाँ” और “दायाँ” स्थान हैं, छोटे और बड़े लेबल नहीं।

मुख्य बातें

• बाइनरी ट्री के हर नोड में अधिकतम दो क्रम वाले संतान-स्थान हैं; उसका BST होना आवश्यक नहीं।
• एक रूट, हर दूसरे नोड का एक parent, सभी तक पहुँच और कोई चक्र नहीं: यहाँ रूटेड संरचना के नियम हैं।
• depth और height एज गिनते हैं; root depth और leaf height 0 हैं, खाली ट्री की height -1 परिभाषित है।
• Full, complete और perfect डेटा नहीं, अलग आकार-शर्तें जाँचते हैं।
• Pre/in/post में वर्तमान visit दोनों संतान-ट्रैवर्सल से पहले/बीच/बाद आता है।
• इनऑर्डर डेटा तभी क्रमबद्ध करता है जब उचित BST क्रम-नियम भी लागू हो।
• END का अर्थ खाली लिंक है; इंडेक्स से पढ़ने से पहले रुकें। ट्रैवर्सल से पहले वैधता जाँचें।

पहले स्वयं करें, फिर मिलाएँ

1. रूट A की केवल दाईं संतान B है और B की केवल बाईं संतान C है। तीनों ट्रैवर्सल और height लिखें। उत्तर: प्रीऑर्डर A,B,C; इनऑर्डर A,C,B; पोस्टऑर्डर C,B,A; height 2 एज। आकार full, complete या perfect नहीं है।
2. एक नोड का डेटा -1 है और दोनों संतान-लिंक END हैं। क्या ट्री खाली है? उत्तर: नहीं। तीनों ट्रैवर्सल डेटा -1 एक बार छापते हैं; height 0 है। खाली ट्री में root = END और used = 0 है और कोई नोड नहीं छपता।
3. मुख्य ट्री में इंडेक्स 5 का left लिंक 0 करें, जो पहले ही इंडेक्स 1 की बाईं संतान है। उत्तर: जाँच साझा संतान अस्वीकार करती है; एक नोड के दो parent हो जाएँगे। केवल डेटा का मान दोहराना स्वीकार होता, क्योंकि नोड की पहचान उसका इंडेक्स है, डेटा नहीं।

छह मौलिक अभ्यास प्रश्न

ठीक एक विकल्प चुनें। ये मौलिक बुनियादी अभ्यास हैं, आधिकारिक पिछले वर्ष के प्रश्न, पूरा मॉक या संपूर्ण पाठ्यक्रम कवरेज का दावा नहीं। ऊपर की स्पष्ट परिभाषाएँ इस्तेमाल करें।

1

रूट A की बाईं संतान B और दाईं C है। B की केवल दाईं संतान D है; C और D पत्तियाँ हैं। पोस्टऑर्डर क्रम क्या है?

A. A, B, D, C B. B, D, A, C C. D, C, B, A D. D, B, C, A

2

इस पाठ के एज गिनने वाले नियम में सात नोड की एक शृंखला ट्री है। उसकी height और आखिरी नोड की depth क्या हैं?

A. 7 और 7 B. 6 और 6 C. 6 और 0 D. 0 और 6

3

गैर-खाली बाइनरी ट्री में रूट की केवल एक बाईं संतान है, जो पत्ती है। आकार का सही वर्गीकरण कौन-सा है?

A. Full और perfect, लेकिन complete नहीं B. Full और complete, लेकिन perfect नहीं C. Complete, लेकिन full या perfect नहीं D. Full, complete या perfect में से कोई नहीं

4

मुख्य प्रोग्राम के ट्री में डेटा का पूरा इनऑर्डर क्रम कौन-सा है?

A. 0, 1, 2, 3, 4, 5, 6 B. 2, 12, 9, 5, 8, 3, 7 C. 2, 3, 5, 7, 8, 9, 12 D. 8, 12, 2, 5, 9, 3, 7

5

दो अलग सक्रिय parent एक ही child इंडेक्स को लिंक करते हैं। कोई दिशायुक्त चक्र नहीं है। इस पाठ की वैधता-जाँच क्या करती है?

A. साझा संतान अस्वीकार करती है क्योंकि दूसरी बार उसका seen चिह्न पहले से लगा मिलता है B. स्वीकार करती है क्योंकि केवल चक्र न होना ही ट्री का नियम है C. संतान की अपने-आप कॉपी बनाकर हर parent को अलग प्रति देती है D. दोनों parent का डेटा अलग हो तो ही स्वीकार करती है

6

वैध खाली निरूपण (used=0, root=END) पर जाँच के बाद दिखाए तरीके से बुलाने पर preorder और height क्या करते हैं?

A. preorder, -1 छापता है; height, 0 लौटाता है B. preorder, nodes[-1] पढ़ता है; height, -1 लौटाता है C. preorder कुछ नहीं छापता; height, 0 लौटाता है D. preorder कुछ नहीं छापता; height, -1 लौटाता है

समझाए गए उत्तर

1: D

A गलत है: संतान से पहले नोड वाला क्रम प्रीऑर्डर है।

B गलत है: बायाँ-नोड-दायाँ इस ट्री का इनऑर्डर देता है।

C गलत है: C पर आधारित दाएँ सबट्री से पहले B सहित उसका पूरा सबट्री समाप्त होगा।

D सही है: बायाँ सबट्री D,B देता है; दायाँ C; रूट A सबसे बाद में आता है।

2: B

A गलत है: रास्ते के सात नोड को छह एज जोड़ती हैं।

B सही है: सबसे लंबे रूट-से-पत्ती रास्ते में छह एज हैं, इसलिए दोनों 6 हैं।

C गलत है: आखिरी नोड पत्ती होने से उसकी अपनी height 0 है, रूट से depth नहीं।

D गलत है: पूरे ट्री की height 6 है; केवल पत्ती की height 0 है।

3: C

A गलत है: रूट की ठीक एक संतान है, जो full और perfect दोनों नियम तोड़ती है।

B गलत है: complete सही है, लेकिन full में रूट की एक-संतान अवस्था अनुमत नहीं।

C सही है: आखिरी स्तर सबसे बाईं जगह से बिना अंतराल शुरू होता है; रूट की एक संतान full और perfect होने से रोकती है।

D गलत है: आखिरी स्तर का अकेला नोड सबसे बाएँ होने से यह complete है।

4: B

A गलत है: ये बढ़ते भौतिक इंडेक्स हैं, डेटा का ट्रैवर्सल नहीं।

B सही है: बायाँ सबट्री 2,12,9,5 देता है; फिर रूट 8; फिर दायाँ सबट्री 3,7।

C गलत है: यह क्रमबद्ध डेटा है। सामान्य बाइनरी ट्री में इनऑर्डर के क्रमबद्ध होने की गारंटी नहीं।

D गलत है: सबट्री से पहले रूट छापने पर इस ट्री का प्रीऑर्डर मिलता है।

5: A

A सही है: हर गैर-रूट नोड का एक parent होना चाहिए। साझा seen ऐरे बिना चक्र के भी दोहराया इंडेक्स पकड़ता है।

B गलत है: एक-parent सदस्यता और सभी तक पहुँच भी आवश्यक हैं।

C गलत है: ऐरे पैरामीटर देने से रिकॉर्ड की कॉपी नहीं बनती।

D गलत है: नोड की पहचान उसका इंडेक्स है; parent के डेटा की तुलना कई parent होने की त्रुटि नहीं सुधारती।

6: D

A गलत है: यहाँ END किसी नोड का डेटा नहीं है; खाली height -1 परिभाषित है, 0 नहीं।

B गलत है: दोनों फ़ंक्शन nodes[at] पढ़ने से पहले END जाँचते हैं।

C गलत है: छपने की बात सही है, लेकिन एज नियम में height 0 एक-नोड ट्री की है।

D सही है: आधार स्थितियाँ तुरंत लौटती हैं; न छपना, न नोड पढ़ना, और खाली height -1 है।

अगला कदम और सीमा

आगे ट्री संरचना में BST का क्रम-नियम जोड़ें, फिर बाइनरी min-heap के अलग complete-आकार और parent-क्रम नियम पढ़ें। यह मौलिक C11 बुनियाद किसी मौजूदा परीक्षा-वर्ष को नहीं बदलती और पूरे पाठ्यक्रम कवरेज का दावा नहीं करती। हिंदी व्याख्याएँ सीखने में सहायता हैं।