Inorder Вориси гиреҳ дар Tree Binary  


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Amazon Expedia Morgan Stanley Хонаҳои OYO Snapchat
Дарахти ҷустуҷӯи бинарӣ Дарахт

Изҳороти мушкилот  

Мушкилот дархост мекунад, ки "Ворисони гиреҳи дарахти дуӣ" пайдо карда шавад. Вориси иноридерии гиреҳ гиреҳи дарахти дуӣ мебошад, ки пас аз гиреҳи додашуда дар гардиши иноридории дарахти дуӣ дода мешавад.

мисол  

  

Inorder successor of 6 is 4

Шарҳ

Гузариши инордерии дарахт 9 7 1 6 4 5 3. Ҳамин тариқ, вориси инордерии 1 6 аст.

усул  

Умуман, ба мо гуфта мешавад, ки гиреҳи навбатии гардиши inorder -ро пайдо кунем дарахти ҷустуҷӯи бинарӣ. Аммо ин аз дарахти дуӣ фарқ мекунад. Пас, як чизро мо бояд қайд кунем, ки убур кардани дарахти умумии дуӣ бо тартиби афзоиш нест. Акнун биёед ба пеш ҳаракат кунем. Пас, агар мо гиреҳ дошта бошем, пас 3 ҳолат мавҷуданд, ки мо бояд онҳоро дида бароем.

3 ҳолате, ки мо бояд қайд кунем, ба фарзанди рости он марбут аст ё агар гиреҳи кунунӣ фарзанди росттарин бошад. Пас, агар гиреҳ фарзанди дуруст дошта бошад. Пас вориси inorder танҳо кӯдаки чапдаст дар зери дарахти рости он мебошад. Аммо агар он фарзанди мувофиқ надошта бошад. Пас ниёгони пасти гиреҳи додашударо ёбед, то гиреҳи додашуда дар зердарахти чапи ниёгон бошад. Барои ин, гиреҳро рекурсивӣ ёбед ва вақте ки мо аз мағозаи рекурсионӣ бармегардем, волидайне, ки мо самти чапро интихоб кардем.

ҳамчунин нигаред
Наздиктарин рақами Палиндромро ёбед

Ҳоло ҳолати охирин агар гиреҳ фарзанди росттарин бошад. Агар ин ҳолат рӯй диҳад, ягон вориси inorder барои гиреҳ вуҷуд надорад.

рамз  

Коди 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), зеро мо рекурсияро истифода кардем. Ҳамин тариқ, агар фосилаеро, ки стеки компилятор гирифтааст, баррасӣ кунем. Мураккабии фазо аз баландии дарахт вобаста аст.