Inorder Successor ของโหนดใน Binary Tree


ระดับความยาก ยาก
ถามบ่อยใน อเมซอน Expedia สแตนลี่ย์มอร์แกน ห้องโอโย Snapchat
ต้นไม้ค้นหาแบบไบนารี ต้นไม้

คำชี้แจงปัญหา

ปัญหาขอให้ค้นหา“ Inorder Successor ของโหนดใน Binary Tree” ลำดับตัวตายตัวแทนของโหนดคือโหนดในต้นไม้ไบนารีที่มาหลังจากโหนดที่กำหนดในการข้ามผ่านตามลำดับของต้นไม้ไบนารีที่กำหนด

ตัวอย่าง

Inorder successor of 6 is 4

คำอธิบาย

การเคลื่อนที่ตามลำดับของต้นไม้คือ 9 7 1 6 4 5 3 ดังนั้นลำดับต่อจาก 1 จึงเป็น 6

เข้าใกล้

โดยทั่วไปเราได้รับคำสั่งให้ค้นหาโหนดถัดไปในลำดับการข้ามผ่านของไฟล์ ต้นไม้ค้นหาไบนารี. แต่แตกต่างจากต้นไม้ไบนารี ดังนั้นสิ่งหนึ่งที่เราควรทราบก็คือการข้ามผ่านตามลำดับของต้นไม้ไบนารีทั่วไปไม่ได้เรียงลำดับจากน้อยไปมาก ตอนนี้เรามาดูกันดีกว่า ดังนั้นหากเรามีโหนดมี 3 กรณีที่เราควรพิจารณา

3 กรณีที่เราควรทราบเกี่ยวข้องกับลูกที่ถูกต้องหรือถ้าโหนดปัจจุบันเป็นลูกขวาสุด ดังนั้นถ้าโหนดมีลูกที่ถูกต้อง จากนั้นผู้สืบทอดลำดับคือลูกซ้ายสุดในแผนผังย่อยด้านขวา แต่ถ้าไม่มีลูกที่เหมาะสม จากนั้นค้นหาบรรพบุรุษที่ต่ำที่สุดของโหนดที่กำหนดเพื่อให้โหนดที่ระบุอยู่ในทรีย่อยด้านซ้ายของบรรพบุรุษ ในการทำเช่นนี้ให้ค้นหาโหนดแบบวนซ้ำและเมื่อเราย้ายกลับจากการเรียกซ้ำจะจัดเก็บพาเรนต์จากที่ที่เราเลือกทิศทางซ้าย

ตอนนี้กรณีสุดท้ายคือถ้าโหนดเป็นลูกขวาสุด หากสิ่งนี้เกิดขึ้นไม่มีตัวต่อลำดับใด ๆ สำหรับโหนด

รหัส

รหัส C ++ เพื่อค้นหา Inorder Successor ของโหนดใน 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

โค้ด Java เพื่อค้นหา Inorder Successor ของโหนดใน 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) เนื่องจากเราใช้การเรียกซ้ำ ดังนั้นหากเราพิจารณาพื้นที่ที่คอมไพเลอร์สแตก ความซับซ้อนของพื้นที่ขึ้นอยู่กับความสูงของต้นไม้