Екілік ағаштағы түйіннің мұрагері


Күрделілік дәрежесі қиын
Жиі кіреді Amazon Expedia Морган Стэнли OYO бөлмелері Snapchat
Екілік іздеу ағашы ағаш

Проблемалық мәлімдеме

Мәселе «Екілік ағаштағы түйіннің инераторлық ізбасарын» табуды сұрайды. Түйіннің инераторлы мұрагері - бұл берілген екілік ағаштың инерциялық травералында берілген түйіннен кейін келетін екілік ағаштағы түйін.

мысал

Inorder successor of 6 is 4

Түсіндіру

Ағаштың көлденең жүрісі 9 7 1 6 4 5 3. Сонымен, 1-нің инордерлік мұрагері 6-ға тең.

жақындау

Әдетте, бізге а-ны инерберальды кесіп өтудің келесі түйінін табу керек дейді екілік іздеу ағашы. Бірақ бұл екілік ағаштан өзгеше. Бір ескеретін жайт, жалпы екілік ағаштың инерциялық өтпесі өсу ретімен емес. Енді алға қарай жүрейік. Егер бізде түйін болса, онда біз 3 жағдайды қарастыруымыз керек.

Біз ескеретін үш жағдай оның оң баласына қатысты немесе егер ағымдағы түйін өзі оң жақтағы бала болса. Егер түйіннің дұрыс баласы болса. Сонда инордер мұрагері жай оң жақтағы кіші сол жақтағы бала болып табылады. Бірақ егер оның дұрыс баласы болмаса. Содан кейін берілген түйін ата-баба сол жақ ағашында жататындай етіп, ең төменгі атаны табыңыз. Ол үшін түйінді рекурсивті түрде табыңыз, ал біз рекурсиялық дүкеннен оралғанда ата-ананы сол бағытты таңдаған жерден аламыз.

Енді соңғы жағдай егер түйін оң жақтағы бала болса. Егер бұл орын алса, түйін үшін ешқандай ізбасар мұрагері болмайды.

код

Екілік ағаштағы түйіннің инераторлық ізбасарын табуға арналған 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* 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

Екілік ағаштағы түйіннің инераторлық ізбасарын табуға арналған 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 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

Күрделілікті талдау

Уақыттың күрделілігі

O (N), өйткені ең нашар жағдайда біз барлық түйіндерді айналып өтуіміз керек.

Ғарыштың күрделілігі

O (H), өйткені біз рекурсия қолдандық. Сонымен компилятор стегі алатын кеңістікті қарастырсақ. Кеңістіктің күрделілігі ағаштың биіктігіне байланысты.