DATA STRUCTURE IN HINDI, BINARY TREE, LINKED LIST,TRAVERSAL,ALGORITHM

Binary Tree

Binary tree :-

Binary ट्री को नोड को finite set के रूप में define किया जाता है इसमें एक नोड में चाइल्ड की संख्या अधिकतम दो हो सकती है | means कोई ऐसा नोड नही होगा जिसकी डिगरी दो से jyada हो | इसके साथ ही binary ट्री में नोड को children sequence में होता है नोड के लेफ्ट के नोड को left नोड तथा right को राईट नोड कहा जाता है word binary एक नोड से two way (left or right ) बताता है one way ( right or left ) हो सकता है | इस लिए हम लेफ्ट sub ट्री और right sub ट्री के मध्य अंतर बना कर रखते है |

binary ट्री को निम्न नुसार भी define कर सकता है
1. एक empty ट्री binary tree होता है
2. binary ट्री रूट नोड left sub tree और right sub ट्री का finite sub ट्री होता है जो पुनः binary ट्री है
3. कोई बी non empty binary ट्री भी एक ट्री होता है|

properties of binary ट्री ⇒

binary ट्री के importent usefule properties निम्न लिखित है
1. ट्री में कोई भी दो नोड्स सिर्फे एक path से जुड़े होते है|
2. "k" नोड्स वाले एक ट्री में (k-1) edges व ब्रान्चेस होती है |
3. एक ट्री में प्रत्येक नोड को रूट नोड छोड़ कर एक parent होता है |
4. एक binary ट्री में लेवल "k" पर नोड की अधिकतम संक्या 2 की घाट k-1 , k >=1 होती है | means यदि k =4 है तब लेवल 2 की घात 4-1 बराबर 8 होगा |
5. depth /hight के binary ट्री में नोड की संख्या अधिकतम संख्या 2 की घात i-1 , i >=1 होती है यदि i=4 हो तो अधिकतम 4 उचाई के binary ट्री में नोड की अधिकतम संख्या 2^4-1 =8 होगा |
6. किसी भी non empty binary ट्री के लिए यदि "n0 " तेर्मिनोल नोड की संख्या है और "n 2 "डिग्री 2 के नोड की संख्या है t ताब निम्न लिखित equation सही होगा n =n0 -1
7. "k" internal नोड वाले binary ट्री में (k +1 ) external nodes होते है |

Representatin of binary tree :-

computer की memory में binary ट्री को दो तरह से represent किया जा सकता है

1. array /linear रिप्रजेंटेशन
2. linked list रिप्रजेंटेशन

array रिप्रजेंटेशन : माना एक t binary ट्री है जो की सम्पूण या लगभग में रखना t का sequence रिप्रजेंटेशन कहलाता है| binary ट्री t के नोड्स को एक एक one dimentional array या सिंगल linear array ट्री में निम्न लिखित प्रकार से स्टोर किया जाता है |
1. ट्री का रूट ट्री [1] पर स्टोर करते है |
2. यदि एक नोड n ट्री [k] स्थान पर हैं तब इसका left child ट्री [2*k] स्थान पर तथा इसका राईट child ट्री [2*k+1] स्थान पर होता है |
3. null को use subtree को empty दर्शाने के लिए किया जाता है tree [1 ] =null ट्री की empty नेस को show करता है | और दिया गया digram sequentical represent की प्रदर्शित करता है |

* linked list represetation ;- binary की अधिकतर linked list द्वारा प्रदर्शित करते है इस के प्रत्येक नोड के तीन प्राइमरी फिल्ड होते है data जिसमे नोड्स से रिलेटेड informetion या डाटा होता है लेफ्ट तथा राईट sub tree के लिए pointer होते है ट्री t को प्रत्येक नोड n लोकेशन k को सापेक्ष इस प्रकार होता है
1. info [k ] को डाटा को नोड n पर रखता है
2. नोड n के लेफ्ट child की location right [k] रखता है
3. following digram linked list represent show करता है

conversion of general trees to binary tree :- हम किसी भी greneral tree "t" को binary tree "T b " में में निम्न tarah से परवर्ती कर सकते हैं
1. binary tree "T b " में नोड का self general tree "t" में avaibale नोड को सामान होना चाहिए
2. binary ट्री "Tb " का root node के सामान होगे
3. यदि "x " binary ट्री "Tb " में कोई arbitrary नोड है तब "Tb"में "x " नोड का लेफ्ट child general ट्री "t" में नोड "x " का first child होता है और binary ट्री "Tb"में नोड "x" में नोड "x" का राईट child general ट्री "T" में "x" का अगला सिबलिंग होगा
following digram में general ट्री को show किया गया following digram binary ट्री को reprtresent करती है जैसा हमने observed किया है \की gemeneral ट्री के अनुरूप binary ट्री के लिए "T b" का नोड और special "T b" का रूट के समान होगा \ इसके अतरिक्त यदि "x " binary ट्री "Tb " का नोड है तब उसका लेफ्ट child "T" में "x" का next sibling होता है \

Algorithm :-
PRE_ORDER (PTR )
[PTR is a pointer conter contains
        the address of not  nod ]


IF   PTR<>NULL then ;
write  [PTR->INPO
PRE_OREDER(PTR -> LEFT)
PRE_ORDER(PTR->RIGHT)
[end of if]
exit

In Order Traversal :- Binary Tree का In order traversal निम्न तरह से define होता है
1. inorder में लेफ्ट sub ट्री ट्रेवर्स कीजिये (L)
2. root नोड को विजिट करे (R )
3. Inoder के righ sub ट्री को trevers करे
in ओर order travers में , पहले हम left sutree को travars करेंगें \ फिर root को और last में right नोड को treversal का करते है | यदि ट्री का कोई subtree नहीं है तो trevals को treversal का कार्य बिना कुछ किये जाते है अतः null subtree को पूडतः travers माना जाता है | following digram का inorder traversal

Binary Tree Traversal :-

Binary Tree में Travers मुख्यतः तीन प्रकार के होते है ⇒
1. Preorder travarsal
2. inorder travarsal
3. post order traversal

Pre Order Traversal :- Binary Tree में Pre Order Traverls निम्नानुसार होता है
1. root node का visit करे (R )
2. pre order में right sub tree को traversal करे (L )
3. pre order में राईट sub tree को traversal करें (R )
following digrem का pre order traversal -,*, AB/CD/EF pre oreder travarsal की condition में सबसे पहले हम root नोड को लेते है एवं उसके बाद left dubtree लेते है left subtree के सभी नोड्स पर कार्य करने के पश्चात right subtree पर कार्य उसी प्रकार शुरू करते है \ जैसा left sub tree में हुआ है यदि tree को पास subtree नहीं है तब travrasal कुछ करने से भी हो जाता है means null subtree को पूडतः travers माना जाता है जब उसका मूल्यांकन किया जाता है \ algorithm

IN_ORDER (PTR )
[PTR is pointer contains 
the address of root node]
if PTR<>NULL than
IN_ORDER(PTR->LEFT)
write:PTR->info
IN_ORDER(PTR->RIGHT)
[END OF IF]
EXIT

POST 'ORDER TRAVERSAL : binary tree को post ट्री order traversal को निम्न तरह से define करते है | Post order में लेफ्ट sub ट्री को travers करे L Post order में राईट sub ट्री को travers कीजिये | Root नोड पर कार्य करें | Post-order traversal में रूट नोड को लास्ट में execute किया जाता है | first left sub ट्री पर कार्य होता है | First left subtree पर कार्य होता है | फिर राईट sub ट्री पर और लास्ट में रूट नोड पर | following diagram का post order traversal AB * CD /-EF / + है|

Threaded Binary Tree ⇒

Binary Tree के linked रिप्रजेंटेशन में pointer फील्ड के लेफ्ट तथा राईट लगभग आधी एंट्रीज़ में नल एलेमेंट्स रहते है | in नल एंट्रीज़ को special pointer से replace किया जाता है | तथा in पॉइंटर्स को thread कहते है | और ऐसे pointer को binary ट्री की थ्रेडेड binary ट्री भी कहा जाता है | थ्रेडेड binary tree बनाने के लिए binary ट्री में किसी भी एक traversal मेथड के अनुरूप थ्रेडेड लिंक विभिन्न नोड के मध्य जोड़े जाते है | thread लिंकज थो टाइप के होते है|
1. Left Thread binary Tree
2. Right Thread binary Tree
यदि किसी नोड का लेफ्ट लिंक बिना यूज किया हुआ है तब इसे लेफ्ट थ्रेडेड binary से चेंज उस नोड के predecessor नोड से किसी traversal sequence के अनुरूप जोड़ा जाता है | इसी प्रकार यदि किसी नोड का राईट लिंक empty लिंक है तब use राईट thread लिंक से बदलकर उस नोड के सुच्सस्सर नोड से किसी traversal order के अनुरूप जोड़ा जाता है | किसी भी binary ट्री को inorder ,preorder या पोस्टआर्डर में से किसी एक traversal मेथड के अनुरूप ही थ्रेडेड बनाई जाती है |

Binary Search Tree :-

Binary Serch Tree Binary Tree की एक प्रमुख sub class बनता है एक general ट्री में एलिमेंट्स को किसी भी तरीके से order नहीं किया जाता है बलकी बहुत से applicatimons में data order किया जाता है binary सर्च tree में informetion को नोड्स में किसी एक sequance में manage किया जाता है सामान्यतः binary सर्च tree को nodes कुछ रिकॉर्डर को प्रदर्शित करते हैं और ये रेकॉर्डे ओर्देरेड होते है ordered होता है इस लिए यह किया जाता है|