ट्री और ग्राफ

ट्री और ग्राफ़ पदानुक्रमित और नेटवर्क-आधारित डेटा को दर्शाने के लिए उपयोग की जाने वाली गैर-रैखिक डेटा संरचनाएँ हैं।

इस पाठ में आप सीखेंगे:

• ट्री और ग्राफ़ की संरचना कैसी होती है।
• C में बाइनरी ट्री कैसे लागू करें।
• सन्निकटता सूचियों और मैट्रिसों का उपयोग करके ग्राफ़ को कैसे दर्शाएँ।

ट्री एक पदानुक्रमित डेटा संरचना है, जिसमें Node होते हैं।

मुख्य शब्द:

• रूट - सबसे ऊपर का Node।
• पैरेंट और चाइल्ड - सीधे जुड़े हुए Node।
• लीफ़ - ऐसा Node जिसका कोई चाइल्ड नहीं होता।

C में, बाइनरी ट्री के Node को बाएँ और दाएँ चाइल्ड पॉइंटर वाले struct का उपयोग करके परिभाषित किया जाता है।

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
    struct Node *root = createNode(10);
    return 0;
}

ट्रैवर्सल की विधियाँ:

• Inorder (LNR) - बायाँ, Node, दायाँ।
• Preorder (NLR) - Node, बायाँ, दायाँ।
• Postorder (LRN) - बायाँ, दायाँ, Node।

यह प्रोग्राम बाइनरी ट्री का Inorder ट्रैवर्सल करता है।

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

void inorder(struct Node *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node *root = malloc(sizeof(struct Node));
    root->data = 10;
    root->left = NULL;
    root->right = NULL;
    inorder(root);
    return 0;
}

ग्राफ Node (शीर्षों) का एक समूह है, जो किनारों से जुड़े होते हैं।

ग्राफ इस प्रकार के हो सकते हैं:

• दिशात्मक - किनारों की दिशा होती है।
• अदिशात्मक - किनारों की कोई दिशा नहीं होती।

ग्राफ का निरूपण इनका उपयोग करके किया जा सकता है:

• आसन्नता मैट्रिक्स - कनेक्शन दर्शाने वाली 2D ऐरे।
• आसन्नता सूची - ऐसी सूची जिसमें प्रत्येक Node अपने पड़ोसी Node की ओर संकेत करता है।

सामान्य ट्रैवर्सल विधियाँ:

• चौड़ाई-प्रथम खोज (BFS) - अधिक गहराई में जाने से पहले सभी पड़ोसी Node पर जाता है।
• गहराई-प्रथम खोज (DFS) - पीछे लौटने से पहले जितना संभव हो उतनी गहराई तक खोज करता है।

इस पाठ में आपने सीखा:

• ट्री और ग्राफ की संरचना कैसी होती है।
• ट्री का ट्रैवर्सल कैसे किया जाता है।
• ग्राफ का निरूपण और ट्रैवर्सल कैसे किया जाता है।

इसके साथ C में डेटा संरचनाएँ अनुभाग पूरा होता है!