Со оглед на бинарно дрво, како ги отстранувате сите полу-јазли?


Ниво на тешкотија Медиум
Често прашувано во Аколит Амазон Мајкрософт 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

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

Анализа на сложеност

Временска комплексност

НА), затоа што поминавме низ сите јазли во бинарното дрво. Временската сложеност е линеарна.

Комплексноста на просторот

О (H), алгоритмот е рекурзивен алгоритам. Така, комплексноста на просторот зависи од магацинот на компајлерот, што пак зависи од висината на дрвото.