Người kế vị Inorder trong BST II bằng C ++

Giả sử chúng ta có một nút trong cây tìm kiếm nhị phân, chúng ta phải tìm nút kế thừa theo thứ tự của nút đó trong BST. Nếu không có người kế nhiệm theo thứ tự, trả về null. Như chúng ta biết rằng nút kế nhiệm là nút có khóa nhỏ nhất lớn hơn giá trị của nút.

Chúng tôi sẽ có quyền truy cập trực tiếp vào nút nhưng không truy cập vào gốc của cây. Ở đây mỗi nút sẽ có một tham chiếu đến nút cha của nó. Dưới đây là định nghĩa cho Node -

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

Nếu đầu vào giống như -

và nút là 2, thì đầu ra sẽ là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu bên phải của nút không rỗng, thì -

  • node:=right of node

  • trong khi bên trái của nút không rỗng, do -

    • node:=left of node

  • nút trả lại

• while (cha của nút không phải là null và nút không bằng bên trái của cha của nút), do -

  • node:=cha của node

• cha của nút trả lại

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

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

Đầu ra

3