Инордер наследник чвора у бинарном стаблу


Ниво тешкоће Тежак
Често питани у амазонка Екпедиа Морган Стенли ОИО собе Снапцхат
Бинарно стабло претраживања Дрво

Изјава о проблему

Проблем тражи да се пронађе „Уордер наследник чвора у бинарном стаблу“. Инордер насљедник чвора је чвор у бинарном стаблу који долази након датог чвора у инордер обласку датог бинарног стабла.

Пример

Inorder successor of 6 is 4

Објашњење

Унутарњи прелазак дрвета је 9 7 1 6 4 5 3. Тако је узастопни наследник 1 6.

Приступ

Генерално, речено нам је да пронађемо следећи чвор у унутрашњем обилажењу а бинарно стабло претраге. Али то се разликује од бинарног стабла. Дакле, једна ствар коју бисмо требали приметити је да унутрашњи обилазак општег бинарног стабла није у растућем редоследу. Сада идемо напред. Дакле, ако имамо чвор, постоје 3 случаја на која бисмо требали обратити пажњу.

3 случаја која бисмо требали приметити повезани су са његовим правим дететом или је тренутни чвор сам крајње дете. Дакле, ако чвор има право дете. Тада је инордер наследник једноставно крајње лево дете у свом десном подстаблу. Али ако нема право дете. Затим пронађите најнижег претка датог чвора тако да дати чвор лежи у левом подстаблу претка. Да бисте то урадили, рекурзивно пронађите чвор, а када се вратимо из рекурзије, родитељ чувамо одакле смо изабрали леви смер.

Сада је последњи случај да ли је чвор најдесније дете. Ако се то догоди, не постоји ниједан инордер наследник чвора.

код

Ц ++ код за проналажење Инордер наследника чвора у Бинарном стаблу

#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* findLeftMostNode(node* root){
  while(root && root->left) root = root->left;
  return root;
}

node* findRightMostNode(node* root){
  while(root && root->right) root = root->right;
  return root;
}

node* findAncestorSuccessor(node* root, node* given)
{
  if(root){
    if(root == given)
      return root;
    node* tmp = findAncestorSuccessor(root->left, given);
    if(tmp){
      if(root->left == tmp){
        cout<<"Inorder Successor of "<<given->data<<" is "<<root->data;
        return NULL;
      }
      return root;
    }
    tmp = findAncestorSuccessor(root->right, given);
    if(tmp){
      if(root->left == tmp){
        cout<<"Inorder Successor of "<<given->data<<" is "<<root->data;
        return NULL;
      }
      return root;
    }
  }
    return NULL;
}

void findInorderSuccesor(node* root, node* given)
{
    // if right child exists
    if(given->right)
    {
    	node* leftmost = findLeftMostNode(given);
    	cout<<"Inorder Succesor of "<<given->data<<" is "<<leftmost->data;
    	return;
    }
    // if right child does not exists
    if(given->right == NULL)
    {
        node* rightmost = findRightMostNode(root);
        if(rightmost == given)
            cout<<"Inorder Successor does not exists";
        else
        	findAncestorSuccessor(root, given);
    }
}

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);
  root->left->right->right = create(4);
  findInorderSuccesor(root, root->left->right->left);
}
Inorder Successor of 1 is 6

Јава код за проналажење Инордер наследника чвора у Бинарном стаблу

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 findLeftMostNode(node root){
    while(root != null && root.left != null) root = root.left;
    return root;
  }

  static node findRightMostNode(node root){
    while(root != null && root.right != null) root = root.right;
    return root;
  }

  static node findAncestorSuccessor(node root, node given)
  {
    if(root != null){
      if(root == given)
        return root;
      node tmp = findAncestorSuccessor(root.left, given);
      if(tmp != null){
        if(root.left == tmp){
          System.out.print("Inorder Successor of "+given.data+" is "+root.data);
          return null;
        }
        return root;
      }
      tmp = findAncestorSuccessor(root.right, given);
      if(tmp != null){
        if(root.left == tmp){
          System.out.print("Inorder Successor of "+given.data+" is "+root.data);
          return null;
        }
        return root;
      }
    }
      return null;
  }

  static void findInorderSuccesor(node root, node given)
  {
      // if right child exists
      if(given.right != null)
      {
      	node leftmost = findLeftMostNode(given);
      	System.out.print("Inorder Successor of "+given.data+" is "+leftmost.data);
      	return;
      }
      // if right child does not exists
      else
      {
          node rightmost = findRightMostNode(root);
          if(rightmost == given)
              System.out.print("Inorder Successor does not exists");
          else
          	findAncestorSuccessor(root, given);
      }
  }

  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);
    root.left.right.right = create(4);
    findInorderSuccesor(root, root.left.right.left);
  }
}
Inorder Successor of 1 is 6

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

Сложеност времена

О (Н), јер ћемо у најгорим случајевима можда морати да пређемо преко свих чворова.

Сложеност простора

О (Х), пошто смо користили рекурзију. Стога, ако узмемо у обзир простор који заузима стек компајлера. Сложеност простора зависи од висине стабла.