algorithm
पेड़

टिप्पणियों

परिचय

पेड़ अधिक सामान्य नोड-एज ग्राफ डेटा संरचना के एक उप-प्रकार हैं।

एक पेड़ होने के लिए, एक ग्राफ को दो आवश्यकताओं को पूरा करना चाहिए:

• यह एसाइक्लिक है। इसमें कोई चक्र नहीं है (या "लूप्स")।
• यह जुड़ा हुआ है। ग्राफ में दिए गए किसी भी नोड के लिए, प्रत्येक नोड उपलब्ध है। सभी नोड्स ग्राफ़ में एक पथ के माध्यम से उपलब्ध हैं।

कंप्यूटर साइंस में ट्री डेटा स्ट्रक्चर काफी सामान्य है। पेड़ों का उपयोग कई अलग-अलग एल्गोरिदम डेटा संरचनाओं को मॉडल करने के लिए किया जाता है, जैसे साधारण बाइनरी पेड़, लाल-काले पेड़, बी-पेड़, एबी-पेड़, 23-पेड़, हीप, और कोशिश करता है।

एक पेड़ को एक Rooted Tree रूप में संदर्भित करना आम है:

choosing 1 cell to be called `Root`
painting the `Root` at the top
creating lower layer for each cell in the graph depending on their distance from the root -the bigger the distance, the lower the cells (example above)

पेड़ों के लिए सामान्य प्रतीक: T

विशिष्ट अनेरी ट्री प्रतिनिधित्व

आमतौर पर हम एक अनेरी ट्री (प्रति नोड में संभावित असीमित बच्चों के साथ एक) को बाइनरी ट्री के रूप में दर्शाते हैं, (एक नोड के प्रति दो बच्चों के साथ)। "अगले" बच्चे को एक भाई के रूप में माना जाता है। ध्यान दें कि यदि एक पेड़ द्विआधारी है, तो यह प्रतिनिधित्व अतिरिक्त नोड बनाता है।

फिर हम भाई-बहनों पर पुनरावृत्ति करते हैं और बच्चों को वापस बुलाते हैं। जैसा कि अधिकांश पेड़ अपेक्षाकृत उथले होते हैं - बहुत सारे बच्चे लेकिन पदानुक्रम के कुछ ही स्तर, यह कुशल कोड को जन्म देता है। नोट मानव वंशावली एक अपवाद है (पूर्वजों के बहुत से स्तर, प्रति स्तर केवल कुछ बच्चे)।

यदि आवश्यक बैक पॉइंट को रखा जा सकता है तो पेड़ को चढ़ने की अनुमति दी जा सकती है। इन्हें बनाए रखना अधिक कठिन होता है।

ध्यान दें कि जड़ पर कॉल करने के लिए एक फ़ंक्शन और अतिरिक्त मापदंडों के साथ एक पुनरावर्ती कार्य करना आवश्यक है, इस मामले में पेड़ की गहराई।

  struct node
  {
     struct node *next;
     struct node *child;
     std::string data;
  }

  void printtree_r(struct node *node, int depth)
  {
     int i;

     while(node)
     {
         if(node->child)
         {
            for(i=0;i<depth*3;i++)
                printf(" ");
            printf("{\n"):
            printtree_r(node->child, depth +1);
            for(i=0;i<depth*3;i++)
                printf(" ");
            printf("{\n"):
    
            for(i=0;i<depth*3;i++)
               printf(" ");
             printf("%s\n", node->data.c_str());

             node = node->next;
          }
      }
  }

  void printtree(node *root)
  {
     printree_r(root, 0);
  }

यह जांचने के लिए कि दो बाइनरी पेड़ समान हैं या नहीं

1. उदाहरण के लिए यदि इनपुट हैं:

उदाहरण 1

ए)

ख)

आउटपुट सही होना चाहिए।

उदाहरण: 2

यदि इनपुट हैं:

ए)

ख)

आउटपुट झूठा होना चाहिए।

उसी के लिए छद्म कोड:

boolean sameTree(node root1, node root2){

if(root1 == NULL && root2 == NULL)
return true;

if(root1 == NULL || root2 == NULL)
return false;

if(root1->data == root2->data 
     && sameTree(root1->left,root2->left)
        && sameTree(root1->right, root2->right))
return true;

}