የሁለትዮሽ ዛፍ ከተሰጠ ሁሉንም ግማሽ አንጓዎች እንዴት ያስወግዳሉ?


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ የተከማቸ አማዞን የ Microsoft PayU Snapdeal 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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ ምክንያቱም በሁለትዮሽ ዛፍ ውስጥ ያሉትን ሁሉንም አንጓዎች ተሻግረናል ፡፡ የጊዜ ውስብስብነቱ መስመራዊ ነው ፡፡

የቦታ ውስብስብነት

ኦ (ኤች) ፣ ስልተ ቀመር መልሶ የማጠናቀር ስልተ ቀመር ነው። ስለዚህ የቦታ ውስብስብነት በአቀነባባሪው ቁራጭ ላይ የተመሠረተ ነው ፣ እሱም በተራው በዛፉ ቁመት ላይ ጥገኛ ነው።