Tree (ट्री ):-
Tree is a non linear data structure. Tree is also called distinct or group wise collection of nodes. In Tree , nodes are represented in hierarchical structure. there is no descending or ascending order between nodes of tree.tree is used to represent parent- child relationship between nodes.Tree has a special node / first node which doesn't have any parent node is called a root node. Every tree starts with the root node.
Tree एक नॉन-लीनियर डाटा स्ट्रक्चर है जिसमें एक या अधिक पृथक या सम्मिलित नोड्स के समूह होते हैं Tree में नोड्स को वंश वृक्ष (Hierarchical Structure) के रूप में दर्शाया जाता हैं। Tree के नोड्स के मध्य कोई आरोही या अवरोही क्रम नहीं होता है। Tree के मध्य पैरेंट-चाइल्ड रिलेशनशिप को व्यक्त किया जाता है। एक सामान्य tree में, एक नोड के कई चाइल्ड नोड्स हो सकते है, लेकिन इन सभी चाइल्ड का केवल एक ही पैरेंट नोड हो सकता हैं। Tree के प्रथम नोड को रुट नोड कहा जाता है इसका कोई पैरेंट नोड नहीं होता है। प्रत्येक ट्री का प्रारम्भ रुट नोड से ही होता है।
In below diagram we represent a tree-T
निम्न चित्र में एक ट्री-T को दर्शाया गया है।
In above tree T, A is root node, B,C,E,F,I are parent nodes and D,G,H,J,K,L are child nodes.
उपरोक्त ट्री में A रुट नोड है, B,C,E,F,I पैरेंट नोड है एवं D,G,H,J,K,L चाइल्ड नोड है।
Root Node (रूट नोड ):–
Root node is a special/first node of a tree, every tree starts with root node.In other words "Root node is a node which doesn't have any parent node." In above tree, A is root node.
रुट नोड किसी ट्री का एक विशेष/प्रथम नोड होता है, प्रत्येक ट्री का प्रारंभ रुट नोड से ही होता है । दूसरे शब्दों में "रुट नोड वह नोड है जिसका कोई पैरेंट नोड नहीं होता है।" उपरोक्त ट्री T में A रुट नोड है।
Parent Node (पैरेंट नोड) :–
A node of tree which has one or more child nodes is called parent node. It is also called internal node or ancestor node. In above tree B,C,E,F,I are parent nodes.
ट्री का वह नोड, जिसके एक या अधिक चाइल्ड नोड होते है पैरेंट नोड कहलाता है। पैरेंट नोड को इंटरनल नोड या अनसेस्टर नोड भी कहा जाता है। उपरोक्त ट्री T में B,C,E,F,I पैरेंट नोड है।
Leaf Node (लीफ़ नोड) :–
A node of tree which doesn't have any child node is called Leaf node. It presents at last level of the tree. It is also called external node or child node. In above tree D,G,H,J,K,L are leaf nodes.
ट्री का वह नोड, जिसका कोई चाइल्ड नोड नहीं होता है, लीफ नोड कहलाता है। लीफ नोड, ट्री के सबसे नीचले स्तर का नोड होता है। लीफ नोड को चाइल्ड नोड या एक्सटर्नल नोड भी कहा जाता है। उपरोक्त ट्री T में D,G,H,J,K,L लीफ नोड है।
Binary Tree (बाइनरी ट्री ):-
It is a special type of tree data structure. In which every parent node have maximum 2 children. It is a finite set of nodes. It may be an empty tree.In other words we can say that "a binary tree contains a left binary sub tree and a right binary sub tree and these sub-trees are again a binary tree." First node of binary tree is called a root node.
यह ट्री डाटा स्ट्रक्चर का एक विशेष प्रकार है जिसमे प्रत्येक पैरेंट नोड के अधिकतम २ चाइल्ड नोड होते है। यह नोड्स का परिमित समुच्चय है। यह एम्प्टी ट्री (रिक्त ) भी हो सकता है। दूसरे शब्दों में हम कह सकते है कि "एक बाइनरी ट्री के द्वारा एक लेफ्ट बाइनरी सब ट्री एवं एक राइट बाइनरी सब ट्री को रखा जाता है जो पुनः बाइनरी ट्री होते है।" बाइनरी ट्री के प्रथम नोड को रुट नोड कहा जाता है।
In below diagram we represent a binary tree-T
निम्न चित्र में एक बाइनरी ट्री-T को दर्शाया गया है।
Node (नोड):-
A node is a special structure which stores information related with node. In addition, it also stores pointer to left and right child node or Null value. In above binary tree, A,B,C,E,F,I, D,G,H,J are nodes of tree.
यह एक विशेष प्रकार का स्ट्रक्चर है जो नोड से सम्बंधित जानकारी रखता है साथ ही लेफ्ट एवं राइट चाइल्ड नोड को पॉइंट करने हेतु पॉइंटर रखता है या नल वैल्यू रखता है। उपरोक्त बाइनरी ट्री T में A,B,C,E,F,I, D,G,H,J नोड है।
struct node{
struct node *lchild;
int info;
struct node *rchild;
};
Edge (एज):-
A direct line which combines any two adjacent nodes is called an edge for example there is an edge between node A and B.
किन्ही दो नज़दीकी नोड को जोड़ने वाली प्रत्यक्ष रेखा, एज कहलाती है जैसे नोड A से B के बीच एक एज है।
Path (पथ ):–
An alternative order of node and edge from source node to destination node is called Path. In above tree, a path between node A and E is A - B - E.
प्रारंभिक नोड से अंतिम नोड के मध्य, नोड एवं एज के एकान्तर क्रम को Path (पथ) कहा जाता है। उपरोक्त ट्री T में, A से E तक का पथ A - B - E है।
Length of a Path (पाथ की लम्बाई):-
Number of edges exist between source node to destination node is called Length of path. In above tree, a length of path between node A and E is 2.
प्रारंभिक नोड से अंतिम नोड के मध्य उपस्थित एज की संख्या को को पाथ की लम्बाई कहा जाता है। उपरोक्त ट्री T में, A से E तक पाथ की लम्बाई 2 है।
The sum of the path lengths of a tree's internal nodes is called the internal path length and the sum of the path lengths of a tree's external nodes is called the external path length.
ट्री के आतंरिक नोड्स के पाथ के कुल योग को ट्री की इंटरनल पाथ लेंथ एवं बाह्य नोड्स के पाथ के कुल योग को ट्री की एक्सटर्नल पाथ लेंथ कहा जाता है।
Degree of a node (नोड की डिग्री):-
Maximum number of children having by a specific node is called degree of that node. In binary tree, A parent node has degree 1 or 2 and A leaf node has degree zero. In above tree T, degree of nodes A,B,F are 2, C,E,I are 1 and D,G,H,J are 0.
किसी विशेष नोड के द्वारा रखे जाने वाले अधिकतम चिल्ड्रेन की संख्या उस नोड की डिग्री कहलाती है। बाइनरी ट्री में पैरेंट नोड की डिग्री 1 या 2 तथा चाइल्ड नोड की डिग्री 0 होती है। उपरोक्त ट्री T में नोड्स A,B,F की डिग्री 2, C,E,I की डिग्री 1 एवं D,G,H,J की डिग्री 0 है।
Degree of tree (ट्री की डिग्री):-
In a tree, the maximum degree of a specific node is called degree of tree. In above tree T, degree of tree is 2 because degree of specific node A,B or F is 2 which is maximum.
अधिकतम चिल्ड्रेन की संख्या रखने वाले किसी विशेष नोड की डिग्री ही उस ट्री की डिग्री कहलाती है। उपरोक्त ट्री T की डिग्री 2 है क्योंकि विशेष नोड A,B या F की अधिकतम डिग्री 2 है।
Depth of a node (नोड की गहराई):-
The depth of a node in a binary tree is the length of the path from the root of the tree to that node. In above tree T, depth of node J is 4.
बाइनरी ट्री के किसी नोड की गहराई, ट्री के रूट नोड से उस नोड तक पहुचने वाले पाथ की लम्बाई होती है। उपरोक्त ट्री T में नोड J की गहराई 4 है।
Height of a node(नोड की उचाई ):-
The height of a node in a binary tree is the length of path from the node to the deepest leaf. In above tree T, height of node B is 2.
बाइनरी ट्री के किसी नोड की उचाई, उस नोड से सबसे गहरी लीफ़ नोड तक पहुचने वाले पाथ की लम्बाई होती है।उपरोक्त ट्री T में नोड B की उचाई 2 है।
Siblings (सीब्लिंग्स):-
In a tree data structure, nodes which belong to same Parent are called as Siblings for example In above binary tree T, B & C are siblings.
ट्री डाटा स्ट्रक्चर में, एक ही पैरेंट के समस्त चिल्ड्रेन को आपस में सीब्लिंग्स कहा जाता है।उदहारण के लिए उपरोक्त बाइनरी ट्री T में B और C सिब्लिंग्स है।
Free Tree (फ्री ट्री):-
A tree is said to be a free tree if we cant recognize root node of that tree. It means A tree without any designated root is called a free tree.
एक ट्री , फ्री ट्री कहा जाता है यदि हम उसके रूट नोड की पहचान नहीं कर सकते है अर्थात एक ट्री जिसमे कोई प्रत्यक्ष रूट नोड नहीं होता है फ्री ट्री कहलाता है।
Forest(फ़ॉरेस्ट):-
If we remove the root node from tree then we will get set of different sub-trees which are collectively called forest. In other words,Forest is a collection of disjoint trees, we can also say that forest is a collection of an a-cyclic graph which is not connected. for example if we remove node A from above binary tree T then we get two sub-trees which are collectively called forest.
यदि हम किसी ट्री में से रूट नोड को हटा देते है तब हमे कई सब ट्री प्राप्त होते है, जिन्हें सम्मिलित रूप से फ़ॉरेस्ट कहा जाता है। दुसरे शब्दों में , फ़ॉरेस्ट अलग अलग ट्री का समूह होता है इसे ए-साइक्लिक का समूह भी कहा जाता है जो आपस में जुड़े हुए ना हो। उदहारण के लिए यदि हम उपरोक्त ट्री T से रूट नोड a को हटा दे तब हमे 2 सब ट्री प्राप्त होंगे। जिन्हें सम्मिलित रूप से फ़ॉरेस्टकहा जायेगा।
Full binary tree(फुल बाइनरी ट्री):-
A full binary tree is a binary tree in which all nodes except leaf nodes have two children. A full binary tree is also called proper binary tree or 2-tree.
एक फुल बाइनरी ट्री एक बाइनरी ट्री होता है जिसमे सभी नोड्स (लीफ़ नोड को छोड़कर) के 2 children होते है। फुल बाइनरी ट्री को प्रॉपर बाइनरी ट्री या 2-ट्री के नाम से भी जाना जाता है।
A complete binary tree is a binary tree in which every level, except possibly the last level, is completely filled.
एक कम्पलीट बाइनरी ट्री एक बाइनरी ट्री होता है जिसमे अंतिम स्टार को छोड़कर अन्य सभी स्तरों पर नोड्स की संख्या अधिकतम होती है।
Strictly binary tree (स्ट्रिक्टली बाइनरी ट्री):-
A Strictly binary tree is a binary tree in which every node except the leaf nodes have two children or only have a root node.
एक स्ट्रिक्टली बाइनरी ट्री एक बाइनरी ट्री होता है जिसमे सभी नोड्स (लीफ़ नोड को छोड़कर) के 2 children होते है या केवल रूट नोड होता है।
A skewed binary tree is a type of binary tree in which all the nodes have only either one child or no child.
एक स्किवड बाइनरी ट्री एक विशेष प्रकार का बाइनरी ट्री होता है जिसमे या तो सभी नोड्स का केवल एक चाइल्ड होता है या चाइल्ड नहीं होता है।
There are 2 types of skewed binary tree:-
यह निम्न 2 प्रकार का होता है:-
1. Left Skewed Binary Tree(लेफ्ट स्किवड बाइनरी ट्री):-
A skewed binary tree in which all the nodes are having a left child or no child at all is called left skewed binary tree.
एक स्किवड बाइनरी ट्री जिसमे सभी नोड्स के या तो केवल लेफ्ट चाइल्ड होते है या कोई चाइल्ड नहीं होते है लेफ्ट स्किवड बाइनरी ट्री कहलाता है।
2. Right Skewed Binary Tree(राईट स्किवड बाइनरी ट्री):-
A skewed binary tree in which all the nodes are having a right child or no child at all is called right skewed binary tree.
एक स्किवड बाइनरी ट्री जिसमे सभी नोड्स के या तो केवल राईट चाइल्ड होते है या कोई चाइल्ड नहीं होते है राईट स्किवड बाइनरी ट्री कहलाता है।
No comments:
Post a Comment