Threaded Binary Tree (थ्रेडेड बाइनरी ट्री):-
When we represent a binary tree with linked list representation then generally some parent node's and all child node's left and right pointers may store NULL values. We can store addresses of higher level nodes in place of these null values to perform faster inorder traversal of binary tree. This pointer is called a thread and this type of binary tree is called threaded binary tree.
जब किसी बाइनरी ट्री को लिंक्ड लिस्ट रिप्रजेंटेशन में दर्शाया जाता है तब सामान्यतः कुछ पैरेंट नोड एवं सभी चाइल्ड नोड के लेफ्ट या राइट पॉइंटर नल वैल्यू रखते है। इन नल वैल्यूस के स्थान पर नोड द्वारा, अपने हायर लेवल नोड का एड्रेस रखा जा सकता है इसे थ्रेड कहा जाता है तथा इस प्रकार के ट्री को थ्रेडेड बाइनरी ट्री कहा जाता है। यह इनआर्डर ट्रेवेर्सल को तीव्र गति से पूर्ण करने का एक तरीका है।
It is of following two types:-
थ्रेडेड बाइनरी ट्री निम्न दो प्रकार के होते है:-
1.) One Way Threading (वन वे थ्रेडिंग):- In which a NULL right pointers is made to point to the inorder successor (if successor exists).It is also called right threaded binary tree. or In which a NULL left pointers is made to point to the inorder predecessor (if predecessor exists). It is also called left threaded binary tree.
इसमें नोड के राइट नल पॉइंटर को केवल उस नोड से जोड़े देते है। जो इनआर्डर ट्रेवर्सल मे उसके बाद में आती है। इसे राइट थ्रेडेड बाइनरी ट्री भी कहा जाता है। याइसमें नोड के लेफ्ट नल पॉइंटर को केवल उस नोड से जोड़े देते है। जो इनआर्डर ट्रेवर्सल मे उसके पहले आती है। इसे लेफ्ट थ्रेडेड बाइनरी ट्री भी कहा जाता है।
2.)Two way Threading(टू वे थ्रेडिंग):- In which both left and right NULL pointers are made to point to inorder predecessor and inorder successor respectively. It is also called full threaded binary tree.
इसमें नोड के लेफ्ट एवं राइट नल पॉइंटर को उन दोनों नोड से जोड़े देते है। जो इनआर्डर ट्रेवर्सल मे क्रमशः उसके पहले एवं बाद में आती है। इसे फुल थ्रेडेड बाइनरी ट्री भी कहा जाता है।
No comments:
Post a Comment