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

C++ में मान k के साथ लीफ नोड्स हटाएं?

आइए पहले उस संरचना को परिभाषित करें जो एक ट्री नोड का प्रतिनिधित्व करेगी जिसमें डेटा और उसके बाएँ और दाएँ नोड बच्चे शामिल हैं। यदि यह बनाया जाने वाला पहला नोड है तो यह एक रूट नोड है अन्यथा एक चाइल्ड नोड है।

struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};

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

struct Node* newNode(int data) {
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->leftChild = newNode->rightChild = NULL;
   return (newNode);
}

अब हम अपना डिलीट नोड (नोड * रूट, इंट के) फंक्शन बनाते हैं जो रूट नोड और नोड के डेटा वैल्यू को डिलीट करने के लिए लेता है। यदि दिया गया नोड पैरेंट नोड है तो यह अपने बाएँ और दाएँ बच्चे को भी हटा देता है। फ़ंक्शन दिए गए नोड को हटाने के बाद संशोधित रूट नोड लौटाता है।

Node* deleteLeafNode(Node* root, int k) {
   if (root == NULL)
      return nullptr;
   root->leftChild = deleteLeafNode(root->leftChild, k);
   root->rightChild = deleteLeafNode(root->rightChild, k);
   if (root->data == k && root->leftChild == NULL &&
      root->rightChild == NULL)
      return nullptr;
   return root;
}

अंत में हटाने के बाद पेड़ को हटाने के लिए हमारे पास एक फ़ंक्शन इनऑर्डर (नोड * रूट) है जो पेड़ को इनऑर्डर फ़ंक्शन में पार करता है।

void inorder(Node* root){
   if (root != NULL){
      inorder(root->leftChild);
      inorder(root->rightChild);
      cout << root->data << " ";
   }
}

उदाहरण

आइए हम k मान वाले लीफ नोड्स को हटाने के निम्नलिखित कार्यान्वयन को देखें।

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};
struct Node* newNode(int data){
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->leftChild = newNode->rightChild = NULL;
   return (newNode);
}
Node* deleteLeafNode(Node* root, int k){
   if (root == NULL)
      return nullptr;
   root->leftChild = deleteLeafNode(root->leftChild, k);
   root->rightChild = deleteLeafNode(root->rightChild, k);
   if (root->data == k && root->leftChild == NULL &&
   root->rightChild == NULL)
      return nullptr;
   return root;
}
void inorder(Node* root){
   if (root != NULL){
      inorder(root->leftChild);
      inorder(root->rightChild);
      cout << root->data << " ";
   }
}
int main(void){
   struct Node* root = newNode(6);
   root->leftChild = newNode(7);
   root->rightChild = newNode(7);
   root->leftChild->leftChild = newNode(5);
   root->leftChild->rightChild = newNode(3);
   root->rightChild->rightChild = newNode(7);
   deleteLeafNode(root, 7);
   cout << "Inorder traversal after deleting given leaf node: ";
   inorder(root);
   return 0;
}

आउटपुट

उपरोक्त कोड निम्न आउटपुट उत्पन्न करेगा -

Inorder traversal after deleting given leaf node: 5 3 7 6

  1. C++ में लीफ नोड से k दूरी पर मौजूद सभी नोड्स को प्रिंट करें

    इस समस्या में, हमें एक बाइनरी ट्री और एक नंबर K दिया जाता है। हमें ट्री के सभी नोड्स को प्रिंट करना होता है जो लीफ नोड से k दूरी पर होते हैं। बाइनरी ट्री एक विशेष पेड़ है जिसके प्रत्येक नोड में अधिकतम दो नोड (एक/दो/कोई नहीं) होते हैं। लीफ नोड बाइनरी ट्री का नोड ट्री के अंत में होता है। इस समस्या

  1. C++ में बाइनरी सर्च ट्री में न्यूनतम मान वाला नोड खोजें

    मान लीजिए कि हमारे पास एक बाइनरी सर्च ट्री है। हमें बाइनरी सर्च ट्री में न्यूनतम तत्व खोजना है। तो अगर बीएसटी नीचे जैसा है - न्यूनतम तत्व 1 होगा। जैसा कि हम जानते हैं कि लेफ्ट सबट्री में हमेशा छोटे तत्व होते हैं। इसलिए यदि हम बाएं सबट्री को बार-बार पार करते हैं जब तक कि बाईं ओर शून्य न हो, हम सब

  1. उस नोड का पता लगाएं जिसका एक्स के साथ पूर्ण अंतर सी ++ में अधिकतम मूल्य देता है

    मान लीजिए कि हमारे पास एक पेड़ है, और सभी नोड्स का वजन और एक पूर्णांक x है। हमें नोड i को खोजना है, जैसे |वेट[i] - x| न्यूनतम है। यदि ग्राफ नीचे जैसा है, और x =15 आउटपुट 3 होगा। अब विभिन्न नोड्स के लिए, यह नीचे जैसा होगा नोड 1, |5 - 15| =10 नोड 2, |10 - 15| =5 नोड 3, |11 - 15| =4 नोड 4, |8 -