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

C++ में बाइनरी ट्री के स्तरों का औसत


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

इसलिए, यदि इनपुट जैसा है:

C++ में बाइनरी ट्री के स्तरों का औसत

तो आउटपुट [3, 14.5, 11] होगा।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

  • एक सरणी result परिभाषित करें
  • एक कतार q परिभाषित करें
  • root को q में डालें
  • q खाली नहीं होने तक लूप चलाएं:
    • n := q का आकार
    • एक सरणी temp परिभाषित करें
    • n शून्येतर होने तक लूप चलाएं:
      • t := q का पहला तत्व
      • t का मान temp में डालें
      • q से तत्व हटाएं
      • यदि t का बायां null नहीं है, तो:
        • t के बाएं को q में डालें
      • यदि t का दायां null नहीं है, तो:
        • t के दाएं को q में डालें
      • n को 1 से घटाएं
    • यदि temp का आकार == 1, तो:
      • temp[0] को result के अंत में डालें
    • अन्यथा यदि temp का आकार > 1, तो:
      • sum := 0
      • i := 0 से temp का आकार - 1 तक लूप चलाएं:
        • sum := sum + temp[i]
      • (sum / temp का आकार) को result के अंत में डालें
  • result वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <bits/stdc++.h> 
using namespace std; 
void print_vector(vector<auto> v){ 
    cout << "["; 
    for(int i = 0; i<v.size(); i++){ 
        cout << v[i] << ", "; 
    } 
    cout << "]"<<endl; 
} 
class TreeNode{ 
public: 
    int val; 
    TreeNode *left, *right; 
    TreeNode(int data){ 
        val = data; 
        left = NULL; 
        right = NULL; 
    } 
}; 
void insert(TreeNode **root, int val){ 
    queue<TreeNode*> q; 
    q.push(*root); 
    while(q.size()){ 
        TreeNode *temp = q.front(); 
        q.pop(); 
        if(!temp->left){ 
            if(val != NULL) 
                temp->left = new TreeNode(val); 
            else 
                temp->left = new TreeNode(0); 
            return; 
        } 
        else{ 
            q.push(temp->left); 
        } 
        if(!temp->right){ 
            if(val != NULL) 
                temp->right = new TreeNode(val); 
            else 
                temp->right = new TreeNode(0); 
            return; 
        } 
        else{ 
            q.push(temp->right); 
        } 
    } 
} 
TreeNode *make_tree(vector<int> v){ 
    TreeNode *root = new TreeNode(v[0]); 
    for(int i = 1; i<v.size(); i++){ 
        insert(&root, v[i]); 
    } 
    return root; 
} 
class Solution{ 
public: 
    vector<float> averageOfLevels(TreeNode *root){ 
        vector<float> result; 
        queue<TreeNode*> q; 
        q.push(root); 
        while (!q.empty()) { 
            int n = q.size(); 
            vector<float> temp; 
            while (n) { 
                TreeNode* t = q.front(); 
                temp.push_back(t->val); 
                q.pop(); 
                if (t->left && t->left->val != 0) 
                    q.push(t->left); 
                if (t->right && t->right->val != 0) 
                    q.push(t->right); 
                n--; 
            } 
            if (temp.size() == 1) 
                result.push_back(temp[0]); 
            else if (temp.size() > 1) { 
                double sum = 0; 
                for (int i = 0; i < temp.size(); i++) { 
                    sum += temp[i]; 
                } 
                result.push_back(sum / temp.size()); 
            } 
        } 
        return result; 
    } 
}; 
int main(){ 
    Solution ob; 
    vector<int> v = {3,9,20,NULL,NULL,15,7}; 
    TreeNode *root = make_tree(v); 
    print_vector(ob.averageOfLevels(root)); 
}

इनपुट

{3,9,20,NULL,NULL,15,7}

आउटपुट

[3, 14.5, 11, ]
  1. C++ में अधिकतम बाइनरी ट्री निर्माण C++ में अधिकतम बाइनरी ट्री निर्माण

    मान लीजिए हमारे पास एक पूर्णांक सरणी है जिसके सभी तत्व अद्वितीय हैं। एक अधिकतम बाइनरी ट्री निम्न नियमों से बनता है: रूट सरणी का अधिकतम तत्व होता है। बायाँ सबट्री अधिकतम तत्व के बाएँ भाग से बने सबसरणी का अधिकतम ट्री होता है। दायाँ सबट्री अधिकतम तत्व के दाएँ भाग से बने सबसरणी का अधिकतम ट्री होता है।

  1. C++ में बाइनरी ट्री के स्तरों को सॉर्ट क्रम में प्रिंट करें C++ में बाइनरी ट्री के स्तरों को सॉर्ट क्रम में प्रिंट करें

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है और हमें प्रत्येक स्तर पर सभी नोड्स को उनके मानों के सॉर्ट क्रम में प्रिंट करना है। आइए एक उदाहरण लेकर अवधारणा को बेहतर ढंग से समझते हैं, इनपुट - आउटपुट - 20 6 15 2 17 32 78 इस समस्या को हल करने के लिए, हमें ट्री के प्रत्येक स्तर का सॉर्ट क्रम प्रिंट कर

  1. C++ में बाइनरी ट्री को बाइनरी सर्च ट्री में रूपांतरण C++ में बाइनरी ट्री को बाइनरी सर्च ट्री में रूपांतरण

    एक बाइनरी ट्री एक विशेष प्रकार का ट्री है जिसमें ट्री का प्रत्येक नोड अधिकतम दो चाइल्ड नोड रख सकता है। इन चाइल्ड नोड्स को राइट चाइल्ड और लेफ्ट चाइल्ड के नाम से जाना जाता है। एक साधारण बाइनरी ट्री है - बाइनरी सर्च ट्री (BST) एक विशेष प्रकार का ट्री है जो निम्नलिखित नियमों का पालन करता है - बाएं चाइ