ਬਾਈਨਰੀ ਟਰੀ ਵਿਚ ਇਕ ਨੋਡ ਦਾ ਅੰਦਰੂਨੀ ਸਫਲ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਇਕਸਪੀਡੀਆ ਮੋਰਗਨ ਸਟੈਨਲੇ ਓਏ ਕਮਰੇ Snapchat
ਬਾਈਨਰੀ ਖੋਜ ਲੜੀ ਟ੍ਰੀ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਮੱਸਿਆ ਨੂੰ "ਬਾਈਨਰੀ ਟ੍ਰੀ ਵਿਚ ਇਕ ਨੋਡ ਦਾ ਅੰਦਰੂਨੀ ਉਤਰਾਧਿਕਾਰੀ" ਲੱਭਣ ਲਈ ਪੁੱਛਦਾ ਹੈ. ਨੋਡ ਦਾ ਇੱਕ ਅੰਦਰੂਨੀ ਉੱਤਰਾਧਿਕਾਰੀ ਬਾਈਨਰੀ ਟਰੀ ਵਿੱਚ ਇੱਕ ਨੋਡ ਹੁੰਦਾ ਹੈ ਜੋ ਦਿੱਤੇ ਗਏ ਬਾਈਨਰੀ ਟਰੀ ਦੇ ਅੰਦਰੂਨੀ ਟ੍ਰਾਵਰਸਲ ਵਿੱਚ ਦਿੱਤੇ ਨੋਡ ਤੋਂ ਬਾਅਦ ਆਉਂਦਾ ਹੈ.

ਉਦਾਹਰਨ

Inorder successor of 6 is 4

ਕਥਾ

ਦਰੱਖਤ ਦਾ ਅੰਦਰੂਨੀ ਟ੍ਰਾਵਰਸਾਲ 9 7 1 6 4 5 ਹੈ. ਇਸ ਤਰ੍ਹਾਂ 3 ਦਾ ਅੰਦਰੂਨੀ ਉਤਰਾਧਿਕਾਰੀ 1 ਹੈ.

ਪਹੁੰਚ

ਆਮ ਤੌਰ 'ਤੇ, ਸਾਨੂੰ ਏ ਦੇ ਅੰਦਰੂਨੀ ਟ੍ਰਾਵਰਸੈਲ ਵਿਚ ਅਗਲਾ ਨੋਡ ਲੱਭਣ ਲਈ ਕਿਹਾ ਜਾਂਦਾ ਹੈ ਬਾਈਨਰੀ ਖੋਜ ਟਰੀ. ਪਰ ਇਹ ਇਕ ਬਾਈਨਰੀ ਰੁੱਖ ਨਾਲੋਂ ਵੱਖਰਾ ਹੈ. ਇਸ ਲਈ ਇਕ ਚੀਜ ਜਿਸ ਬਾਰੇ ਸਾਨੂੰ ਧਿਆਨ ਦੇਣਾ ਚਾਹੀਦਾ ਹੈ ਉਹ ਇਹ ਹੈ ਕਿ ਇਕ ਆਮ ਬਾਈਨਰੀ ਰੁੱਖ ਦਾ ਅੰਦਰੂਨੀ ਟ੍ਰਾਂਸਸਲ ਆਮ ਚੜ੍ਹਨ ਵਾਲੇ ਕ੍ਰਮ ਵਿਚ ਨਹੀਂ ਹੁੰਦਾ. ਆਓ ਅੱਗੇ ਵਧੀਏ. ਇਸ ਲਈ ਜੇ ਸਾਡੇ ਕੋਲ ਨੋਡ ਹੈ ਤਾਂ ਇੱਥੇ 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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਸਭ ਤੋਂ ਮਾੜੇ ਮਾਮਲਿਆਂ ਵਿੱਚ ਸਾਨੂੰ ਸਾਰੇ ਨੋਡਾਂ ਤੋਂ ਪਾਰ ਲੰਘਣਾ ਪੈ ਸਕਦਾ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਚ), ਕਿਉਂਕਿ ਅਸੀਂ ਦੁਬਾਰਾ ਵਰਤੇ ਹਾਂ. ਇਸ ਤਰ੍ਹਾਂ ਜੇ ਅਸੀਂ ਕੰਪਾਈਲਰ ਸਟੈਕ ਦੁਆਰਾ ਲਈ ਗਈ ਥਾਂ ਤੇ ਵਿਚਾਰ ਕਰੀਏ. ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ ਦਰੱਖਤ ਦੀ ਉਚਾਈ 'ਤੇ ਨਿਰਭਰ ਕਰਦੀ ਹੈ.