home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Inorder Successor ใน BST II ใน C ++

สมมติว่าเรามีโหนดในแผนผังการค้นหาแบบไบนารี เราต้องหาตัวต่อตามลำดับของโหนดนั้นใน BST หากไม่มีผู้สืบทอดตามลำดับ ให้คืนค่า null ดังที่เราทราบดีว่าผู้สืบทอดของโหนดคือโหนดที่มีคีย์ที่เล็กที่สุดซึ่งมากกว่าค่าของโหนด

เราจะเข้าถึงโหนดได้โดยตรง แต่จะเข้าถึงรากของต้นไม้ไม่ได้ ที่นี่แต่ละโหนดจะมีการอ้างอิงถึงโหนดหลัก ด้านล่างนี้คือคำจำกัดความของโหนด -

class Node {
   public int val;
   public Node left;
   public Node right;
   public Node parent;
}

หากอินพุตเป็นแบบ −

Inorder Successor ใน BST II ใน C ++

และโหนดคือ 2 จากนั้นเอาต์พุตจะเป็น 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • หากสิทธิ์ของโหนดไม่เป็นโมฆะ −

    • โหนด :=ด้านขวาของโหนด

    • ขณะที่โหนดด้านซ้ายไม่เป็นโมฆะ ให้ทำ -

      • โหนด :=ด้านซ้ายของโหนด

    • โหนดกลับ

  • ในขณะที่ (พาเรนต์ของโหนดไม่เป็นโมฆะและโหนดไม่เท่ากับด้านซ้ายของพาเรนต์ของโหนด) ทำ -

    • โหนด :=พาเรนต์ของโหนด

  • พาเรนต์ของโหนดส่งคืน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
   int val;
   Node* left;
   Node* right;
   Node* parent;
   Node(int v, Node* par = NULL){
      val = v;
      left = NULL;
      right = NULL;
      parent = par;
   }
};
class Solution {
public:
   Node* inorderSuccessor(Node* node) {
      if (node->right) {
         node = node->right;
         while (node->left)
         node = node->left;
         return node;
      }
      while (node->parent && node != node->parent->left) {
         node = node->parent;
      }
      return node->parent;
   }
};
main(){
   Solution ob;
   Node *root = new Node(5);
   root->left = new Node(3, root);
   root->right = new Node(6, root);
   root->left->left = new Node(2, root->left);
   root->left->right = new Node(4, root->left);
   root->left->left->left = new Node(1, root->left->left);
   cout << (ob.inorderSuccessor(root->left->left))->val;
}

อินพุต

Node *root = new Node(5);
root->left = new Node(3, root);
root->right = new Node(6, root);
root->left->left = new Node(2, root->left);
root->left->right = new Node(4, root->left);
root->left->left->left = new Node(1, root->left->left);
(ob.inorderSuccessor(root->left->left))->val

ผลลัพธ์

3