पूरा बाइनरी ट्री

इस ट्यूटोरियल में, आप एक पूर्ण बाइनरी ट्री और इसके विभिन्न प्रकारों के बारे में जानेंगे। साथ ही, आपको C, C ++, जावा और पायथन में एक पूर्ण बाइनरी ट्री के काम करने के उदाहरण मिलेंगे।

एक पूर्ण बाइनरी ट्री एक बाइनरी ट्री है, जिसमें संभवतः सभी स्तर पूरी तरह से भरे हुए हैं, संभवत: सबसे निचले हिस्से को छोड़कर, जो बाईं ओर से भरा हुआ है।

एक पूर्ण बाइनरी ट्री एक पूर्ण बाइनरी ट्री की तरह है, लेकिन दो प्रमुख अंतरों के साथ

  1. सभी पत्ती तत्वों को बाईं ओर झुकना चाहिए।
  2. अंतिम पत्ती तत्व में एक सही भाई नहीं हो सकता है अर्थात एक पूर्ण बाइनरी ट्री के पास एक पूर्ण बाइनरी ट्री नहीं होना चाहिए।
पूरा बाइनरी ट्री

पूर्ण बाइनरी ट्री बनाम पूर्ण बाइनरी ट्री

पूर्ण बाइनरी ट्री और पूर्ण बाइनरी ट्री के बीच तुलना। पूर्ण बाइनरी ट्री और पूर्ण बाइनरी ट्री के बीच तुलना

पूर्ण बाइनरी ट्री कैसे बनाया जाता है?

  1. रूट नोड होने के लिए सूची के पहले तत्व का चयन करें। (स्तर I पर तत्वों की संख्या नहीं: 1) मूल के रूप में पहला तत्व चुनें
  2. दूसरा तत्व रूट नोड के बाएं बच्चे के रूप में और तीसरा तत्व सही बच्चे के रूप में रखें। (स्तर- II पर तत्वों की संख्या 2: 2) एक बाएं बच्चे के रूप में 12 और एक सही बच्चे के रूप में 9
  3. अगले दो तत्वों को दूसरे स्तर के बाएं नोड के बच्चों के रूप में रखें। फिर, अगले दो तत्वों को दूसरे स्तर के सही नोड के बच्चों के रूप में डालें (स्तर- III पर तत्वों के नहीं: 4) तत्व)।
  4. आखिरी तत्व तक पहुंचने तक दोहराते रहें। 5 एक बाएं बच्चे के रूप में और 6 एक सही बच्चे के रूप में

पायथन, जावा और सी / सी ++ उदाहरण

पायथन जावा सी सी ++ 
 # Checking if a binary tree is a complete binary tree in C class Node: def __init__(self, item): self.item = item self.left = None self.right = None # Count the number of nodes def count_nodes(root): if root is None: return 0 return (1 + count_nodes(root.left) + count_nodes(root.right)) # Check if the tree is complete binary tree def is_complete(root, index, numberNodes): # Check if the tree is empty if root is None: return True if index>= numberNodes: return False return (is_complete(root.left, 2 * index + 1, numberNodes) and is_complete(root.right, 2 * index + 2, numberNodes)) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) node_count = count_nodes(root) index = 0 if is_complete(root, index, node_count): print("The tree is a complete binary tree") else: print("The tree is not a complete binary tree") 
 // Checking if a binary tree is a complete binary tree in Java // Node creation class Node ( int data; Node left, right; Node(int item) ( data = item; left = right = null; ) ) class BinaryTree ( Node root; // Count the number of nodes int countNumNodes(Node root) ( if (root == null) return (0); return (1 + countNumNodes(root.left) + countNumNodes(root.right)); ) // Check for complete binary tree boolean checkComplete(Node root, int index, int numberNodes) ( // Check if the tree is empty if (root == null) return true; if (index>= numberNodes) return false; return (checkComplete(root.left, 2 * index + 1, numberNodes) && checkComplete(root.right, 2 * index + 2, numberNodes)); ) public static void main(String args()) ( BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.right = new Node(5); tree.root.left.left = new Node(4); tree.root.right.left = new Node(6); int node_count = tree.countNumNodes(tree.root); int index = 0; if (tree.checkComplete(tree.root, index, node_count)) System.out.println("The tree is a complete binary tree"); else System.out.println("The tree is not a complete binary tree"); ) )
 // Checking if a binary tree is a complete binary tree in C #include #include #include struct Node ( int key; struct Node *left, *right; ); // Node creation struct Node *newNode(char k) ( struct Node *node = (struct Node *)malloc(sizeof(struct Node)); node->key = k; node->right = node->left = NULL; return node; ) // Count the number of nodes int countNumNodes(struct Node *root) ( if (root == NULL) return (0); return (1 + countNumNodes(root->left) + countNumNodes(root->right)); ) // Check if the tree is a complete binary tree bool checkComplete(struct Node *root, int index, int numberNodes) ( // Check if the tree is complete if (root == NULL) return true; if (index>= numberNodes) return false; return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes)); ) int main() ( struct Node *root = NULL; root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); int node_count = countNumNodes(root); int index = 0; if (checkComplete(root, index, node_count)) printf("The tree is a complete binary tree"); else printf("The tree is not a complete binary tree"); )
 // Checking if a binary tree is a complete binary tree in C++ #include using namespace std; struct Node ( int key; struct Node *left, *right; ); // Create node struct Node *newNode(char k) ( struct Node *node = (struct Node *)malloc(sizeof(struct Node)); node->key = k; node->right = node->left = NULL; return node; ) // Count the number of nodes int countNumNodes(struct Node *root) ( if (root == NULL) return (0); return (1 + countNumNodes(root->left) + countNumNodes(root->right)); ) // Check if the tree is a complete binary tree bool checkComplete(struct Node *root, int index, int numberNodes) ( // Check if the tree is empty if (root == NULL) return true; if (index>= numberNodes) return false; return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes)); ) int main() ( struct Node *root = NULL; root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); int node_count = countNumNodes(root); int index = 0; if (checkComplete(root, index, node_count)) cout << "The tree is a complete binary tree"; else cout << "The tree is not a complete binary tree"; )

सरणी अनुक्रमित और वृक्ष तत्व के बीच संबंध

एक पूर्ण बाइनरी ट्री में एक दिलचस्प संपत्ति है जिसका उपयोग हम किसी भी नोड के बच्चों और माता-पिता को खोजने के लिए कर सकते हैं।

यदि एरे में किसी तत्व का इंडेक्स i है, तो इंडेक्स 2i+1का तत्व लेफ्ट चाइल्ड बन जाएगा और 2i+2इंडेक्स में एलिमेंट सही बच्चा बन जाएगा। इसके अलावा, सूचकांक I पर किसी भी तत्व का मूल निम्न के द्वारा दिया गया है (i-1)/2।

आइए इसका परीक्षण करें,

 बाएं बच्चे का 1 (सूचकांक 0) = तत्व (2 * 0 + 1) सूचकांक = तत्व 1 सूचकांक में = 12 सही बच्चे का 1 = तत्व में (2 * 0 + 2) सूचकांक = तत्व 2 सूचकांक = 9 में इसी प्रकार 12 के बाएं बच्चे (इंडेक्स 1) = एलीमेंट इन (2 * 1 + 1) इंडेक्स = 3 इंडेक्स में तत्व = 5 12 का सही बच्चा = तत्व (2 * 1 + 2) इंडेक्स = तत्व 4 इंडेक्स = 6 में

आइए हम यह भी पुष्टि करें कि नियम किसी भी नोड के माता-पिता को खोजने के लिए हैं

 9 (स्थिति 2) का जनक = (2-1) / 2 = 0.5 = 0.5 ~ 0 सूचकांक = 1 12 का अभिभावक (स्थिति 1) = (1-1) / 2 = 0 सूचकांक = 1

ट्री पोजिशन में एरे इंडेक्स की इस मैपिंग को समझना यह समझने के लिए महत्वपूर्ण है कि हीप डेटा स्ट्रक्चर कैसे काम करता है और इसका उपयोग हीप सॉर्ट को लागू करने के लिए कैसे किया जाता है।

पूरा बाइनरी ट्री एप्लीकेशन

  • ढेर-आधारित डेटा संरचनाएं
  • ढेर बनाएं और छांटें

दिलचस्प लेख...