У порядку наступник вузла в двійковому дереві


Рівень складності Жорсткий
Часто запитують у Амазонка Expedia Morgan Stanley Номери OYO Snapchat
Бінарне дерево пошуку Дерево

Постановка проблеми

Проблема вимагає знайти “Inorder naslednik вузла в двійковому дереві”. Наступним послідовником вузла є вузол у двійковому дереві, який постає після даного вузла в обхідному переході даного двійкового дерева.

Приклад

Inorder successor of 6 is 4

Пояснення

Обхід навколо дерева 9 7 1 6 4 5 3. Таким чином, наступник 1 за порядком 6 дорівнює XNUMX.

Підхід

Як правило, нам пропонують знайти наступний вузол в порядку обходу a двійкове дерево пошуку. Але це відрізняється від бінарного дерева. Отже, одне, на що слід звернути увагу, - це те, що обхід загального бінарного дерева відбувається не за зростанням. Тепер давайте рухатись вперед. Отже, якщо у нас є вузол, то є 3 випадки, на які слід звернути увагу.

3 випадки, на які слід звернути увагу, пов’язані з його правою дочірньою організацією або з тим, що поточний вузол сам є правою дочірньою організацією. Отже, якщо вузол має правильну дочірню організацію. Тоді наслідувач inorder - це просто крайня ліва дитина у правому піддереві. Але якщо у нього немає правильної дитини. Тоді знайдіть найнижчого предка даного вузла таким, щоб даний вузол лежав у лівому піддереві предка. Для цього рекурсивно знайдіть вузол, а коли ми повернемося з рекурсії, збережемо батьківський звідки ми вибрали лівий напрямок.

Тепер останній випадок - якщо вузол є найправішою дочірньою організацією. Якщо це трапиться, не існує жодного наступного наступника для вузла.

код

Код С ++ для пошуку наступника Inorder вузла в двійковому дереві

#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 для пошуку наступника Inorder вузла в двійковому дереві

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), оскільки ми використовували рекурсію. Таким чином, якщо врахувати простір, який займає стек компілятора. Складність простору залежить від висоти дерева.