Inorder جانشین گره در Binary Tree


سطح دشواری سخت
اغلب در آمازون Expedia مورگان استنلی اتاق های OYO Snapchat
درخت جستجوی دودویی درخت

بیان مسأله

این مشکل می خواهد "Inorder جانشین یک گره در Binary Tree" را پیدا کند. جانشین inorder یک گره گره ای در درخت باینری است که بعد از گره داده شده در مسیریابی inorder درخت باینری داده می شود.

مثال

Inorder successor of 6 is 4

توضیح

پیمایش عددی درخت 9 7 1 6 4 5 3 است. بنابراین جانشین عدد 1 6 است.

روش

به طور کلی ، به ما گفته می شود که گره بعدی را در مسیریابی معکوس a پیدا کنیم درخت جستجوی دودویی. اما این با درخت باینری متفاوت است. بنابراین یک نکته که باید توجه داشته باشیم این است که عبور بی مقدار یک درخت باینری به ترتیب صعودی نیست. حالا بیایید جلوتر برویم. بنابراین اگر گره داشته باشیم ، 3 مورد وجود دارد که باید آنها را بررسی کنیم.

3 موردی که باید توجه داشته باشیم مربوط به فرزند مناسب آن است یا اگر گره فعلی خودش یک کودک صحیح باشد. بنابراین اگر گره فرزند مناسبی داشته باشد. پس جانشین inorder به سادگی چپ ترین فرزند در زیر درخت راست آن است. اما اگر فرزند مناسبی نداشته باشد. سپس پایین ترین جد گره داده شده را پیدا کنید به طوری که گره داده شده در زیرشاخه سمت چپ جد قرار گیرد. برای انجام این کار ، گره را به صورت بازگشتی پیدا کنید ، و هنگامی که از بازگشت به عقب برمی گردیم ، والد را از جایی که جهت چپ را انتخاب کرده ایم ذخیره کنید.

حال آخرین مورد این است که اگر گره بهترین فرزند باشد. اگر چنین اتفاقی بیفتد هیچ جانشینی غیرمستقیم برای گره وجود ندارد.

رمز

کد C ++ برای یافتن Inorder جانشین گره در Binary Tree

#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

کد جاوا برای یافتن Inorder جانشین گره در Binary Tree

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) ، از آنجا که ما از بازگشت استفاده کرده ایم. بنابراین اگر فضای گرفته شده توسط پشته کامپایلر را در نظر بگیریم. پیچیدگی فضا به ارتفاع درخت بستگی دارد.