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

C++ में बाइनरी ट्री का संक्षिप्त एन्कोडिंग

समस्या विवरण

मान लीजिए हमारे पास एक बाइनरी ट्री है। जैसा कि हम जानते हैं, बाइनरी ट्री का संक्षिप्त एन्कोडिंग न्यूनतम संभव स्थान के करीब प्रदर्शन करता है। n-वां कैटलन संख्या n अलग-अलग नोड्स वाले संरचनात्मक रूप से अलग बाइनरी ट्री की संख्या को दर्शाती है। यदि n बड़ा है, तो यह लगभग 4^n है; इस प्रकार, इसे एन्कोड करने के लिए हमें न्यूनतम log2(4^n) = 2n बिट्स की आवश्यकता होती है। एक संक्षिप्त बाइनरी ट्री इसलिए 2n + O(n) बिट्स का उपभोग करेगा।

उदाहरण

C++ में बाइनरी ट्री का संक्षिप्त एन्कोडिंग

आउटपुट होगा:

एन्कोडेड -

स्ट्रक्चर लिस्ट 1 1 1 0 0 1 0 0 1 0 1 0 0

डेटा लिस्ट 10 20 40 50 30 70

डिकोडेड - ऊपर दिखाए गए ट्री के समान।

एल्गोरिदम चरण

  • फ़ंक्शन Encode(root, struc, data) परिभाषित करें:
    • यदि root NULL है, तो struc में 0 डालें और वापस लौटें
    • struc में 1 डालें
    • root के मान को data में डालें
    • Encode(left, struc, data)
    • Encode(right, struc, data)
  • फ़ंक्शन Decode(struc, data) परिभाषित करें:
    • यदि struc का आकार <= 0, तो NULL वापस करें
    • b := struc का पहला तत्व
    • struc से पहला तत्व हटाएं
    • यदि b == 1:
      • key := data का पहला तत्व
      • data से पहला तत्व हटाएं
      • key के साथ नया नोड बनाएं
      • left := Decode(struc, data)
      • right := Decode(struc, data)
      • root वापस करें
    • NULL वापस करें

C++ कार्यान्वयन

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = NULL;
        right = NULL;
    }
};

void Encode(TreeNode *root, list<bool>& struc, list<int>& data){
    if(root == NULL){
        struc.push_back(0);
        return;
    }
    struc.push_back(1);
    data.push_back(root->val);
    Encode(root->left, struc, data);
    Encode(root->right, struc, data);
}

TreeNode *Decode(list<bool>& struc, list<int>& data){
    if(struc.size() <= 0)
        return NULL;
    bool b = struc.front();
    struc.pop_front();
    if(b == 1){
        int key = data.front();
        data.pop_front();
        TreeNode *root = new TreeNode(key);
        root->left = Decode(struc, data);
        root->right = Decode(struc, data);
        return root;
    }
    return NULL;
}

void preorder_trav(TreeNode* root){
    if(root){
        cout << "key: "<< root->val;
        if(root->left)
            cout << " | left child: "<< root->left->val;
        if(root->right)
            cout << " | right child: "<< root->right->val;
        cout << endl;
        preorder_trav(root->left);
        preorder_trav(root->right);
    }
}

int main() {
    TreeNode *root = new TreeNode(10);
    root->left = new TreeNode(20);
    root->right = new TreeNode(30);
    root->left->left = new TreeNode(40);
    root->left->right = new TreeNode(50);
    root->right->right = new TreeNode(70);
    cout << "The Tree\n";
    preorder_trav(root);
    list<bool> struc;
    list<int> data;
    Encode(root, struc, data);
    cout << "\nEncoded Tree\n";
    cout << "Structure List\n";
    for(auto si = struc.begin(); si != struc.end(); ++si)
        cout << *si << " ";
    cout << "\nData List\n";
    for(auto di = data.begin(); di != data.end(); ++di)
        cout << *di << " ";
    TreeNode *newroot = Decode(struc, data);
    cout << "\n\nPreorder traversal of decoded tree\n";
    preorder_trav(newroot);
}

इनपुट

root->left = new TreeNode(20); root->right = new TreeNode(30); root->left->left = new TreeNode(40); root->left->right = new TreeNode(50); root->right->right = new TreeNode(70);

आउटपुट

The Tree
key: 10 | left child: 20 | right child: 30
key: 20 | left child: 40 | right child: 50
key: 40
key: 50
key: 30 | right child: 70
key: 70
Encoded Tree
Structure List
1 1 1 0 0 1 0 0 1 0 1 0 0
Data List
10 20 40 50 30 70
Preorder traversal of decoded tree
key: 10 | left child: 20 | right child: 30
key: 20 | left child: 40 | right child: 50
key: 40
key: 50
key: 30 | right child: 70
key: 70
  1. C++ में बाइनरी ट्री प्रूनिंग C++ में बाइनरी ट्री प्रूनिंग

    मान लीजिए हमारे पास एक बाइनरी ट्री का हेड नोड root है, जहाँ प्रत्येक नोड का मान या तो 0 या 1 है। हमें वही ट्री लौटाना है जहाँ हर वह सबट्री हटा दी गई हो जिसमें 1 नहीं है। उदाहरण: इनपुट ट्री [1,1,0,1,1,0,1,0] के लिए, आउटपुट ट्री में केवल वही नोड्स रहेंगे जिनके सबट्री में कम से कम एक 1 है। पोस्ट-ऑर्

  1. C++ में अधिकतम बाइनरी ट्री निर्माण C++ में अधिकतम बाइनरी ट्री निर्माण

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

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

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