Хоёртын мод өгвөл бүх хагас зангилаагаа хэрхэн яаж устгах вэ?


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Accolite Амазоны Microsoft- PayU Snapdeal Синопсис Yahoo
Мод

Асуудал "Хоёртын мод өгөгдсөн тохиолдолд та бүх хагас зангилаагаа хэрхэн яаж устгах вэ?" танд хоёртын мод өгдөг гэж заасан байдаг. Одоо та хагас зангилаагаа арилгах хэрэгтэй. Хагас зангилаа гэдэг нь ганц хүүхэдтэй модны зангилааг хэлнэ. Энэ нь зүүн эсвэл баруун хүүхэд юм.

Жишээ нь

Хоёртын мод өгвөл бүх хагас зангилаагаа хэрхэн яаж устгах вэ?

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

Бүх хагас зангилааг арилгах Java код

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), алгоритм бол рекурсив алгоритм юм. Тиймээс орон зайн нарийн төвөгтэй байдал нь хөрвүүлэгчийн стекээс хамаардаг бөгөөд энэ нь модны өндрөөс хамаарна.