একটি বাইনারি গাছ দেওয়া, আপনি কিভাবে অর্ধেক নোড মুছে ফেলবেন?


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় সমষ্টি মর্দানী স্ত্রীলোক মাইক্রোসফট Payu Snapdeal সংক্ষেপ নরপশু
গাছ

সমস্যা "একটি বাইনারি গাছ দেওয়া, আপনি কীভাবে সমস্ত অর্ধেকটি নোড সরিয়ে ফেলবেন?" আপনাকে একটি বাইনারি গাছ দেওয়া হয়েছে বলে উল্লেখ করা হয়েছে। এখন আপনাকে অর্ধেকটি নোড সরিয়ে ফেলতে হবে। একটি অর্ধ নোড গাছের নোড হিসাবে সংজ্ঞায়িত হয় যার কেবলমাত্র একক শিশু রয়েছে। হয় তা বাম বা ডান সন্তান।

উদাহরণ

একটি বাইনারি গাছ দেওয়া, আপনি কিভাবে অর্ধেক নোড মুছে ফেলবেন?

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

ব্যাখ্যা

মান 4 এর নোডের একক বাম সন্তান রয়েছে has সুতরাং এটি বাইনারি গাছ থেকে সরানো হয়েছে এবং এর বাম শিশু গাছটিতে সরে গেছে। কারণ সেখানে কেবলমাত্র দেড় নোড। এটি অপসারণের পরে, আমরা একটি গাছের সাথে বাকী আছি যার আন্ডার ট্রভারসাল আউটপুট হিসাবে মুদ্রিত হয়েছে।

অভিগমন

সমস্যাটি একটি দিয়েছে বাইনারি গাছ, আপনি কিভাবে অর্ধেক নোড মুছে ফেলবেন? সমাধানে সরাসরি জাম্প করার আগে। আমাদের প্রথমে জানা উচিত অর্ধ নোড কী? একটি অর্ধ নোড বাইনারি গাছের একটি নোড যার একক শিশু রয়েছে। সুতরাং কোনও শিশু বা দুটি সন্তানের একটি নোডকে অর্ধ নোড হিসাবে বিবেচনা করা হয় না। এখন থেকে আমরা জানি হাফ নোড কী। আমাদের সমস্যার সমাধান নিয়ে এগিয়ে যাওয়া উচিত। সমাধান সহজ। আমরা কেবল গাছটি অতিক্রম করি এবং যখনই আমরা একটি অর্ধ নোড পাই আমরা এটির সন্তানের সাথে প্রতিস্থাপন করি। বাম সন্তানের উপস্থিতি এবং ডান শিশুটি শূন্য কিনা তা আমরা পরীক্ষা করি। তারপরে আমরা তার বাম সন্তানের সাথে পিতামাতার (বা অর্ধ নোড) প্রতিস্থাপন করব। একইভাবে, সঠিক শিশু যদি একমাত্র সন্তান হয়। ডান সন্তান পিতামাতার নোড প্রতিস্থাপন করে।

কোড

অর্ধেকটি নোড সরানোর জন্য সি ++ কোড

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু), কারণ আমরা বাইনারি গাছের সমস্ত নোড পেরিয়েছি। সময় জটিলতা রৈখিক।

স্পেস জটিলতা ity

উহু), অ্যালগরিদম একটি পুনরাবৃত্ত আলগোরিদিম। এইভাবে স্পেস জটিলতা সংকলক স্ট্যাকের উপর নির্ভরশীল যা ঘরের গাছের উচ্চতার উপর নির্ভরশীল।