एक बाइनरी ट्री को देखते हुए, आप सभी आधे नोड्स को कैसे हटाते हैं?


कठिनाई स्तर मध्यम
में अक्सर पूछा एकोलाइट वीरांगना माइक्रोसॉफ्ट PayU स्नैपडील Synopsys याहू
पेड़

समस्या "बाइनरी ट्री को देखते हुए, आप सभी आधे नोड्स को कैसे हटाते हैं?" बताता है कि आपको बाइनरी ट्री दिया गया है। अब आपको आधे नोड्स को हटाने की आवश्यकता है। आधे नोड को पेड़ में एक नोड के रूप में परिभाषित किया गया है जिसमें केवल एक ही बच्चा है। या तो यह बायां बच्चा है या दायां बच्चा है।

उदाहरण

एक बाइनरी ट्री को देखते हुए, आप सभी आधे नोड्स को कैसे हटाते हैं?

Inorder Traversal of tree after half nodes removal: 5 3 6 2 7

व्याख्या

4 के मान वाले नोड में एक अकेला बच्चा है। इस प्रकार इसे बाइनरी ट्री से हटा दिया गया है और इसका बायाँ बच्चा पेड़ से ऊपर चला गया है। क्योंकि केवल एक-आधा नोड है। इसके हटाने के बाद, हमें एक पेड़ के साथ छोड़ दिया जाता है जिसका इनवर्टर ट्रैवर्सल आउटपुट के रूप में मुद्रित किया गया है।

दृष्टिकोण

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

कोड

सभी आधे नोड को निकालने के लिए C ++ कोड

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

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

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

node* removeHalfNode(node* &root){
    if(!root)
        return NULL;
    if(root->left == NULL && root->right != NULL)
        root = removeHalfNode(root->right);
    else if(root->left != NULL && root->right == NULL)
        root = removeHalfNode(root->left);
    else {
        removeHalfNode(root->left);
        removeHalfNode(root->right);
    }
    return root;
}

void inorder(node* root){
    if(root){
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);

  cout<<"Inorder traversal before removing the half nodes"<<endl;
  inorder(root);
  cout<<endl<<"Inorder traversal after removing the half nodes"<<endl;
  root = removeHalfNode(root);
  inorder(root);
}
Inorder traversal before removing the half nodes
9 7 1 6 5 3
Inorder traversal after removing the half nodes
9 7 1 5 3

सभी आधे नोड्स को हटाने के लिए जावा कोड

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  static node removeHalfNode(node root){
      if(root == null)
          return null;
      root.left = removeHalfNode(root.left); 
        root.right = removeHalfNode(root.right); 
   
        if(root.left == null && root.right == null) 
            return root;
        if(root.left == null){ 
            node Node = root.right;
            return Node;
        }
        if(root.right == null){ 
            node Node = root.left;
            return Node;
        } 
        return root;
  }

  static void inorder(node root){
      if(root != null){
          inorder(root.left);
          System.out.print(root.data+" ");
          inorder(root.right);
      }
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);

    System.out.println("Inorder traversal before removing the half nodes");
    inorder(root);
    System.out.println("\nInorder traversal after removing the half nodes");
    root = removeHalfNode(root);
    inorder(root);
  }
}
Inorder traversal before removing the half nodes
9 7 1 6 5 3 
Inorder traversal after removing the half nodes
9 7 1 5 3

जटिलता विश्लेषण

समय जटिलता

पर), क्योंकि हमने बाइनरी ट्री में सभी नोड्स पर निशान लगाया है। समय जटिलता रैखिक है।

अंतरिक्ष जटिलता

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