بالنظر إلى الشجرة الثنائية ، كيف يمكنك إزالة جميع العقد النصفية؟  


مستوى الصعوبة متوسط
كثيرا ما يطلب في Accolite أمازون Microsoft PayU Snapdeal سينوبسيس ياهو
شجرة

المشكلة "بالنظر إلى الشجرة الثنائية ، كيف يمكنك إزالة جميع العقد النصفية؟" تنص على أنك حصلت على شجرة ثنائية. أنت الآن بحاجة إلى إزالة العقد النصفية. تُعرَّف العقدة النصفية بأنها عقدة في الشجرة لها طفل واحد فقط. إما أن يكون الطفل الأيسر أو الطفل الأيمن.

مثال  

بالنظر إلى الشجرة الثنائية ، كيف يمكنك إزالة جميع العقد النصفية؟

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

تحليل التعقيد  

تعقيد الوقت

O (N) لأننا اجتزنا جميع العقد في الشجرة الثنائية. التعقيد الزمني خطي.

انظر أيضا
صفيف متجاور

تعقيد الفضاء

أوه)، الخوارزمية هي خوارزمية متكررة. وبالتالي ، فإن تعقيد الفضاء يعتمد على مكدس المترجم الذي يعتمد بدوره على ارتفاع الشجرة.