ഒരു ബൈനറി ട്രീ നൽകിയാൽ, എല്ലാ അർദ്ധ നോഡുകളും എങ്ങനെ നീക്കംചെയ്യും?


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അക്കോലൈറ്റ് ആമസോൺ മൈക്രോസോഫ്റ്റ് പേ സ്നാപ്ഡേൽ സമന്വയിപ്പിക്കുക യാഹൂ
വൃക്ഷം

പ്രശ്നം “ഒരു ബൈനറി ട്രീ നൽകിയാൽ, പകുതി നോഡുകളും എങ്ങനെ നീക്കംചെയ്യും?” നിങ്ങൾക്ക് ഒരു ബൈനറി ട്രീ നൽകിയിട്ടുണ്ടെന്ന് പ്രസ്താവിക്കുന്നു. ഇപ്പോൾ നിങ്ങൾ പകുതി നോഡുകൾ നീക്കംചെയ്യേണ്ടതുണ്ട്. ഒരൊറ്റ കുട്ടി മാത്രമുള്ള വൃക്ഷത്തിലെ ഒരു നോഡായി ഒരു പകുതി നോഡിനെ നിർവചിച്ചിരിക്കുന്നു. ഒന്നുകിൽ അത് ഇടത് കുട്ടിയോ വലത് കുട്ടിയോ ആണ്.

ഉദാഹരണം

ഒരു ബൈനറി ട്രീ നൽകിയാൽ, എല്ലാ അർദ്ധ നോഡുകളും എങ്ങനെ നീക്കംചെയ്യും?

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

വിശദീകരണം

മൂല്യം 4 ഉള്ള നോഡിന് ഒരു ഇടത് കുട്ടിയുണ്ട്. അങ്ങനെ ഇത് ബൈനറി ട്രീയിൽ നിന്ന് നീക്കംചെയ്യുകയും അതിന്റെ ഇടത് കുട്ടി വൃക്ഷത്തിന്റെ മുകളിലേക്ക് നീങ്ങുകയും ചെയ്തു. കാരണം ഒന്നര നോഡ് മാത്രമേയുള്ളൂ. ഇത് നീക്കം ചെയ്തതിനുശേഷം, ഒരു വൃക്ഷം അവശേഷിക്കുന്നു, അതിന്റെ ഇൻ‌ഓർ‌ഡർ‌ ട്രാവെർ‌സൽ‌ as ട്ട്‌പുട്ടായി അച്ചടിക്കുന്നു.

സമീപനം

പ്രശ്നം ഒരു നൽകിയിട്ടുണ്ട് ബൈനറി ട്രീ, എല്ലാ അർദ്ധ നോഡുകളും എങ്ങനെ നീക്കംചെയ്യും? ശരിയായ പരിഹാരത്തിലേക്ക് ചാടുന്നതിന് മുമ്പ്. അർദ്ധ നോഡ് എന്താണെന്ന് ആദ്യം നമ്മൾ അറിയണം? ഒരൊറ്റ കുട്ടി ഉള്ള ബൈനറി ട്രീയിലെ ഒരു നോഡാണ് അർദ്ധ നോഡ്. അതിനാൽ കുട്ടികളോ രണ്ട് കുട്ടികളോ ഇല്ലാത്ത ഒരു നോഡിനെ അർദ്ധ നോഡായി കണക്കാക്കില്ല. പകുതി നോഡ് എന്താണെന്ന് ഇപ്പോൾ മുതൽ നമുക്കറിയാം. പ്രശ്‌നത്തിനുള്ള പരിഹാരവുമായി നാം മുന്നോട്ട് പോകണം. പരിഹാരം ലളിതമാണ്. ഞങ്ങൾ വൃക്ഷത്തിലൂടെ സഞ്ചരിക്കുന്നു, ഒരു പകുതി നോഡ് കണ്ടെത്തുമ്പോഴെല്ലാം ഞങ്ങൾ അത് അതിന്റെ കുട്ടിയുമായി മാറ്റിസ്ഥാപിക്കുന്നു. ഇടത് കുട്ടി ഉണ്ടെന്നും വലത് കുട്ടി ശൂന്യമാണോ എന്നും ഞങ്ങൾ പരിശോധിക്കുന്നു. അതിനുശേഷം ഞങ്ങൾ രക്ഷകർത്താവിനെ (അല്ലെങ്കിൽ പകുതി നോഡ്) അതിന്റെ ഇടത് കുട്ടിയുമായി മാറ്റിസ്ഥാപിക്കുന്നു. അതുപോലെ, ശരിയായ കുട്ടി മാത്രമാണെങ്കിൽ. ശരിയായ കുട്ടി രക്ഷാകർതൃ നോഡിന് പകരം വയ്ക്കുന്നു.

കോഡ്

എല്ലാ അർദ്ധ നോഡുകളും നീക്കംചെയ്യുന്നതിന് സി ++ കോഡ്

#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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), കാരണം ഞങ്ങൾ ബൈനറി ട്രീയിലെ എല്ലാ നോഡുകളിലൂടെയും സഞ്ചരിച്ചു. സമയ സങ്കീർണ്ണത രേഖീയമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (H), അൽ‌ഗോരിതം ഒരു ആവർത്തന അൽ‌ഗോരിതം ആണ്. അങ്ങനെ സ്ഥല സങ്കീർണ്ണത കംപൈലർ സ്റ്റാക്കിനെ ആശ്രയിച്ചിരിക്കുന്നു, അത് വൃക്ഷത്തിന്റെ ഉയരത്തെ ആശ്രയിച്ചിരിക്കുന്നു.