Representation of Binary Tree or Binary Search Tree(BST)

There are following two representations of Binary Tree:-  

बाइनरी ट्री के निम्न दो प्रतिनिधित्व होते हैं:-

1. Sequential/ Array Representation (सिक्वेंसीअल/ ऐरे रिप्रजेंटेशन):-

In array representation of binary tree, we use a 1D array to store nodes of tree. The size of array is eual to the number of nodes (depth of tree) exist in full binary tree of same level. Root node of tree stored at first position and if parent node is stored at Kth position then it's left child will be stored at 2Kth position and right child will be stored at (2K+1)th position. This representation doesnt utilize space of computer memory. Suppose a binary tree T is as follows:-

बाइनरी ट्री के ऐरे रिप्रजेंटेशन में ट्री के नोड्स को संग्रहीत करने के लिए 1D ऐरे का प्रयोग किया जाता है। ऐरे का मेमोरी साइज़, उस स्तर के एक फुल बाइनरी ट्री में उपस्थित नोड की संख्या(ट्री की गहराई) के बराबर होता है। ट्री के रूट नोड को 1 पोजीशन पर रखा जाता है एवं यदि पैरेंट नोड Kth पोजीशन पर है तब लेफ्ट चाइल्ड को 2Kth एवं राईट चाइल्ड को (2K+1)th पोजीशन पर रखा जाता है। इस रिप्रजेंटेशन में मेमोरी का प्रभावी उपयोग नहीं हो पाता है। माना कि एक बाइनरी ट्री T निम्न है :-

Array representation of above binary tree is as follows :-

इस बाइनरी ट्री का मेमोरी में ऐरे रिप्रजेंटेशन निम्न हैं:-

    

 

2. Linked list Representation (लिंक्ड लिस्ट  रिप्रजेंटेशन) :-

In linked list representation of binary tree, we use a doubly linked list to store nodes of tree and represent parent-child relationship between them. Each node has three parts pointer to left child, information part and pointer to right child. To point root node of binary tree we use an external pointer variable T. Left and right child pointer of the child node stores NULL value.This representation utilizes space of computer memory.

बाइनरी ट्री के लिंक्ड लिस्ट रिप्रजेंटेशन में, बाइनरी ट्री के नोड्स को मेमोरी में संग्रहीत करने के लिए एक लिंक्ड लिस्ट  का प्रयोग किया जाता है एवं पैरेंट-चाइल्ड रिलेशनशिप को व्यक्त किया जाता है। प्रत्येक नोड में तीन भाग होते हैं: लेफ्ट चाइल्ड का पॉइंटर, इनफार्मेशन पार्ट और राईट चाइल्ड का पॉइंटर. प्रत्येक बाइनरी ट्री में रूट नोड को पॉइंट करने के लिए एक्सटर्नल पॉइंटर वेरिएबल T का प्रयोग किया जाता है। चाइल्ड नोड में लेफ्ट और राईट  पॉइंटर्स की वैल्यू NULL रखी जाती हैं । इस रिप्रजेंटेशन में मेमोरी का प्रभावी उपयोग होता है। 

Linked list representation of above binary tree is as follows :-

इस बाइनरी ट्री का मेमोरी में लिंक्ड लिस्ट रिप्रजेंटेशन निम्न हैं :-