Երկուական ծառի հանգույցի անկարգորդ


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Amazon Expedia Morgan Stanley OYO սենյակներ Snapchat
Երկուական որոնման ծառ ծառ

Խնդիրի հայտարարություն

Խնդիրը պահանջում է գտնել «Երկուական ծառի հանգույցի անշեղ հաջորդող»: Հանգույցի անընդմեջ ժառանգորդը երկուական ծառի այն հանգույցն է, որը գալիս է տվյալ երկուական ծառի անկարգությունների անցման տվյալ հանգույցից հետո:

Օրինակ

Inorder successor of 6 is 4

բացատրություն

Treeառի անշեղ շրջանցումը 9 7 1 6 4 5 3. Այսպիսով, 1-ի հետևորդի հաջորդը 6 է:

Մոտեցում

Ընդհանրապես, մեզ ասում են, որ հաջորդ հանգույցը գտնենք a- ի անկարգության անցման մեջ երկուական որոնման ծառ, Բայց դա տարբերվում է երկուական ծառից: Այսպիսով, մի բան, որը մենք պետք է նկատենք, այն է, որ ընդհանուր երկուական ծառի անշեղ շրջանցումը աճման կարգով չէ: Հիմա եկեք առաջ շարժվենք: Այսպիսով, եթե մենք ունենք հանգույց, ապա կա 3 դեպք, որոնք մենք պետք է դիտենք:

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (N), քանի որ ամենավատ դեպքերում կարող է ստիպված լինել անցնել բոլոր հանգույցները:

Տիեզերական բարդություն

O (H), քանի որ մենք օգտագործել ենք ռեկուրսիա: Այսպիսով, եթե հաշվի առնենք, որ տարածությունը վերցված է կազմողի բուրգով: Տիեզերական բարդությունը կախված է ծառի բարձրությունից: