Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम: बाइनरी ट्री में सबसे लंबा पत्ता-से-पत्ता पथ प्रिंट करना

इस ट्यूटोरियल में, हम एक दिए गए बाइनरी ट्री में एक पत्ती नोड से दूसरी पत्ती नोड तक मौजूद सबसे लंबे पथ को प्रिंट करने के प्रोग्राम पर चर्चा करेंगे।

दूसरे शब्दों में, हमें उन सभी नोड्स को प्रिंट करना है जो बाइनरी ट्री के व्यास में दिखाई देते हैं। यहां, किसी विशेष बाइनरी ट्री के लिए व्यास (या चौड़ाई) को एक अंत नोड से दूसरे तक के सबसे लंबे पथ में नोड्स की संख्या के रूप में परिभाषित किया गया है।

इसे हल करने के लिए, हम ऊंचाई फंक्शन का उपयोग करके बाइनरी ट्री का व्यास निकालते हैं। फिर हम बाइनरी ट्री के बाएं हिस्से में सबसे लंबा पथ और दाएं हिस्से में ढूंढते हैं। फिर अंत में व्यास में नोड्स प्रिंट करने के लिए हम बाएं हिस्से के नोड्स, रूट नोड और फिर दाएं हिस्से के नोड्स प्रिंट करते हैं।

उदाहरण

#include <bits/stdc++.h>
using namespace std;

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

struct Node* create_node(int data) {
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

int tree_height(Node* root, int& ans, Node*(&k), int& lh, int& rh, int& f) {
    if (root == NULL)
        return 0;
    int left_tree_height = tree_height(root->left, ans, k, lh, rh, f);
    int right_tree_height = tree_height(root->right, ans, k, lh, rh, f);
    if (ans < 1 + left_tree_height + right_tree_height) {
        ans = 1 + left_tree_height + right_tree_height;
        k = root;
        lh = left_tree_height;
        rh = right_tree_height;
    }
    return 1 + max(left_tree_height, right_tree_height);
}

void print_roottonode(int ints[], int len, int f) {
    int i;
    if (f == 0) {
        for (i = len - 1; i >= 0; i--) {
            printf("%d ", ints[i]);
        }
    } else if (f == 1) {
        for (i = 0; i < len; i++) {
            printf("%d ", ints[i]);
        }
    }
}

void print_pathr(Node* node, int path[], int pathLen, int max, int& f) {
    if (node == NULL)
        return;
    path[pathLen] = node->data;
    pathLen++;
    if (node->left == NULL && node->right == NULL) {
        if (pathLen == max && (f == 0 || f == 1)) {
            print_roottonode(path, pathLen, f);
            f = 2;
        }
    } else {
        print_pathr(node->left, path, pathLen, max, f);
        print_pathr(node->right, path, pathLen, max, f);
    }
}

void calc_diameter(Node* root) {
    if (root == NULL)
        return;
    int ans = INT_MIN, lh = 0, rh = 0;
    int f = 0;
    Node* k;
    int tree_height_of_tree = tree_height(root, ans, k, lh, rh, f);
    int lPath[100], pathlen = 0;
    print_pathr(k->left, lPath, pathlen, lh, f);
    printf("%d ", k->data);
    int rPath[100];
    f = 1;
    print_pathr(k->right, rPath, pathlen, rh, f);
}

int main() {
    struct Node* root = create_node(12);
    root->left = create_node(22);
    root->right = create_node(33);
    root->left->left = create_node(45);
    root->left->right = create_node(57);
    root->left->right->left = create_node(26);
    root->left->right->right = create_node(76);
    root->left->left->right = create_node(84);
    root->left->left->right->left = create_node(97);
    calc_diameter(root);
    return 0;
}

आउटपुट

97 84 45 22 57 26
  1. C++ प्रोग्राम: बाइनरी ट्री के नोड्स को प्रिंट करना जैसे ही वे लीफ नोड बनते हैं C++ प्रोग्राम: बाइनरी ट्री के नोड्स को प्रिंट करना जैसे ही वे लीफ नोड बनते हैं

    एक बाइनरी ट्री दिया गया है, हमें उसके लीफ नोड्स को प्रिंट करना है और फिर उन लीफ नोड्स को हटाना है और फिर तब तक दोहराना है जब तक ट्री में कोई नोड न बचे। उदाहरण तो समस्या का आउटपुट होना चाहिए - 6 7 9 13 14 3 4 2 1 दृष्टिकोण हमने एक ऐसा दृष्टिकोण अपनाया है जहां हम DFS लागू कर रहे हैं। एक अस्थायी म

  1. C++ प्रोग्राम: बाइनरी ट्री में किन्हीं दो नोड्स के बीच पथ प्रिंट करना C++ प्रोग्राम: बाइनरी ट्री में किन्हीं दो नोड्स के बीच पथ प्रिंट करना

    हमें एक बाइनरी ट्री दिया गया है जिसके नोड्स विशिष्ट हैं और उस बाइनरी ट्री के दो नोड्स दिए गए हैं जिनके बीच का पथ हम प्रिंट करना चाहते हैं। उदाहरण के लिए - हम नोड 140 से 211 के बीच का पथ प्रिंट करना चाहते हैं तो इसका आउटपुट होना चाहिए - Output: 140->3->10->211 विचार यह है कि रूट नोड्स से दो

  1. C++ प्रोग्राम: बाइनरी ट्री में पहला सबसे छोटा रूट-टू-लीफ पथ प्रिंट करना C++ प्रोग्राम: बाइनरी ट्री में पहला सबसे छोटा रूट-टू-लीफ पथ प्रिंट करना

    दिए गए बाइनरी ट्री में प्रोग्राम को दिए गए कई पथों में से रूट से लीफ तक का सबसे छोटा पथ ढूंढना होगा। चूंकि हम ट्री को बाएं से दाएं ट्रैवर्स करते हैं, इसलिए यदि रूट से लीफ तक कई सबसे छोटे पथ हैं तो प्रोग्राम ट्री के बाएं तरफ पहले ट्रैवर्स किए गए सबसे छोटे पथ को प्रिंट करेगा। हम एक कतार (queue) का उपय