Екілік ағашты ескере отырып, барлық жартылай түйіндерді қалай алып тастауға болады?


Күрделілік дәрежесі орта
Жиі кіреді Акколит Amazon Microsoft PayU Шапшаң Synopsys 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), алгоритм - бұл рекурсивті алгоритм. Осылайша, кеңістіктің күрделілігі компилятор стегіне тәуелді, ал бұл ағаштың биіктігіне байланысты.