सबसे पहले उस स्ट्रक्चर को परिभाषित करते हैं जो एक ट्री नोड को दर्शाता है जिसमें डेटा और इसके बाएं और दाएं चाइल्ड नोड होते हैं। यदि यह पहला नोड है जिसे बनाया जा रहा है तो यह रूट नोड है अन्यथा चाइल्ड नोड।
struct Node { int data; struct Node *leftChild, *rightChild; }; इसके बाद हम newNode(int data) फ़ंक्शन बनाते हैं जो एक int मान लेता है और इसे नोड के डेटा सदस्य को निर्दिष्ट करता है। फ़ंक्शन बने हुए स्ट्रक्चर Node का पॉइंटर लौटाता है। साथ ही, नए बने नोड के बाएं और दाएं चाइल्ड को NULL पर सेट किया जाता है।
struct Node* newNode(int data){ struct Node* newNode = new Node; newNode->data = data; newNode->leftChild = newNode->rightChild = NULL; return (newNode); } अब हम deleteNode(Node* root, int x) फ़ंक्शन बनाते हैं जो रूट नोड और हटाए जाने वाले नोड का डेटा मान लेता है। यदि दिया गया नोड एक पैरेंट नोड है तो यह इसके बाएं और दाएं चाइल्ड को भी हटा देता है। फ़ंक्शन दिए गए नोड के विलोपन के बाद संशोधित रूट नोड लौटाता है।
Node* deleteLeafNode(Node* root, int x){ if (root == NULL) return nullptr; root->leftChild = deleteLeafNode(root->leftChild, x); root->rightChild = deleteLeafNode(root->rightChild, x); if (root->data == x && root->leftChild == NULL && root->rightChild == NULL) return nullptr; return root; } अंत में विलोपन के बाद ट्री को प्रदर्शित करने के लिए हमारे पास inorder(Node* root) फ़ंक्शन है जो ट्री को इनऑर्डर में ट्रैवर्स करता है।
void inorder(Node* root){ if (root != NULL){ inorder(root->leftChild); inorder(root->rightChild); cout << root->data << " "; } } उदाहरण
आइए मान x के बराबर वाले लीफ नोड्स को हटाने का निम्नलिखित कार्यान्वयन देखें।
#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* deleteNode(Node* root, int x){ if (root == NULL) return nullptr; root->leftChild = deleteNode(root->leftChild, x); root->rightChild = deleteNode(root->rightChild, x); if (root->data == x && 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(4); root->leftChild = newNode(2); root->rightChild = newNode(12); root->leftChild->leftChild = newNode(3); root->leftChild->rightChild = newNode(5); root->rightChild->rightChild = newNode(9); deleteNode(root, 3); cout << "Inorder traversal after deletion : "; inorder(root); return 0; } आउटपुट
उपरोक्त कोड निम्नलिखित आउटपुट देगा:
Inorder traversal after deletion : 5 2 9 12 4
