Data Structures in Hindi : Binary Tree Traversal

Binary Tree Traversal 

  • Introduction to binary tree traversal in Hindi
  • Different types of binary tree traversal in Hindi

Introduction to Binary Tree Traversal

Binary tree की सभी nodes को कोई operation perform करने के लिए एक साथ visit करना traversal कहलाता है। एक binary tree को traverse करते समय उसकी हर node को सिर्फ एक बार access किया जाता है और उसके साथ कुछ operation perform किया जाता है।

उदाहरण के लिए आप binary tree को traverse करके उसकी सभी nodes का data print कर सकते है। इसके अलावा binary tree को traverse करके node में available data को increase या decrease किया जा सकता है।

एक binary tree को 3 प्रकार से traverse किया जा सकता है।

  • Inorder Traversal
  • Preorder Traversal 
  • Postorder Traversal 
इन सभी प्रकार की traversal techniques के बारे में आगे detail से बताया जा रहा है।

Binary Tree In-order Traversal 

जब binary tree को in-order में traverse किया जाता है तो traversal left child -> data -> right child के order में होता है। इस order को L-D-R (Left, Data, Right) भी कहा जाता है।

In-order traversal में सबसे पहले किसी भी node के left child को access किया जाता है। यानी की सबसे पहले root node के left sub tree को traverse किया जाएगा। Left sub tree में भी सबसे पहले left child को access किया जायेगा।

Left child को access करने के बाद node के data को access किया जाएगा। Data को access करने के बाद उस node के right child को access किया जाता है।

जिस node के left और right child नहीं होते है, उनका data directly access किया जाता है। जिस node के left child नहीं होता है उसका सबसे पहले data और फिर right child access किया जाता है। जिस node के right child नहीं होता है उसका सबसे पहले left child और फिर data access किया जाता है।


उदाहरण के लिए निचे दिए गए binary tree को देखिये। 




ऊपर दिए गए binary tree को जब in-order में traverse किया जाएगा तो सबसे पहले root node के left child B को access किया जाएगा। Node B की left child node D है इसलिए इसके बाद node D को access किया जायेगा। क्योंकि node D के left या right child नहीं है इसलिए data को यानी node D की value को access किया जाएगा।

क्योंकि inorder traversal में left child के बाद parent node का data show किया जाता है इसलिए D की value को access करने के बाद node B की value को access किया जायेगा। इसके बाद node E कि value को access किया जायेगा। Node E के left या right child नहीं है इसलिए मुख्य node यानि root node का data access किया जाएगा।

इसी प्रकार root node के right sub tree को traverse किया जायेगा और पहले F node की value उसके बाद C node की value और आखिर में G node की value access की जायेगी।

ऊपर दिए गए binary tree का in-order traversal D, B, E, A, F, C, G order में होगा।

In-order traversal का simple recursive function निचे दिया जा रहा है।

void inorder(struct Node * root)
{
   if(root!=NULL)
   {
       preorder(root->left);
       printf("%d\n",root->data);
       preorder(root->right);
   }
}


Binary Tree Pre-order Traversal 

जब binary tree को pre-order में traverse किया जाता है तो traversal data -> left child -> right child के order में होता है। इस order को D-L-R (Data, Left, Right) order कहा जाता है।

जब pre-order traversal किया जाता है तो सबसे पहले किसी भी node का data access किया जाता है। यानी की यदि root node से traversal की शुरआत होगी तो सबसे पहले root node को ही access किया जायेगा।

Data को access करने के बाद उस node के left child को access किया जायेगा। Left child को access करने के बाद node के right child को access किया जायेगा।

जिस node के left child नहीं होता है उसका पहले data और फिर right child access किया जाता है। जिस node के right child नहीं होता है उस node का पहले data और फिर left child access किया जाता है। जिस node के left और right दोनों ही child नहीं होते है उस node का सिर्फ data ही access किया जाता है।

यदि पहले ऊपर दिए गए binary tree का pre order traversal किया जाए तो वह A, B, D, E, C, F, G के order में होगा।

Binary tree pre-order traversal के लिए recursive function निचे दिया जा रहा है।

void preorder(struct Node * root)
{
     if(root!=NULL)
     {
         printf("%d\n",root->data);
         preorder(root->left);
         preorder(root->right);
    }
}


Binary Tree Post-order Traversal

जब binary tree को post-order में traverse किया जाता है तो traversal left-child -> right-child -> data के order में होता है। इसे L-R-D (Left, Right, Data) order भी कहा जाता है। 

Post-order traversal में सबसे पहले किसी भी node के left child को access किया जाता है। Left child के बाद उस node के right child को access किया जाता है। सबसे आखिर में node के data को access किया जाता है। 

जिस node के left child नहीं हो उसका पहले right child और फिर data access किया जायेगा। जिस node के right child न हो उसका पहले left child और फिर data access किया जायेगा। जिस node के left और right दोनों ही child ना हो उसका data access किया जाता है। 

पहले ऊपर दिए गए binary tree को यदि post-order में traverse किया जाये तो वह D, E, B, F, G, C, A के order में होगा। 

Binary tree post-order traversal के लिए recursive function निचे दिया जा रहा है। 

void postorder(struct Node * root)
{
    if(root!=NULL)
    {
        postorder(root->left);
        postorder(root->left);
        printf("%d\n",root->data);
    }
}


      DMCA.com Protection Status

 Leave a comment