Chương trình tìm Inorder Kế thừa cây tìm kiếm nhị phân trong C ++

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

Vì vậy, nếu đầu vào giống như

Và p =1, thì đầu ra sẽ là 2,

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

• Định nghĩa phương thức đệ quy inorderSuccessor (), phương thức này sẽ có gốc và p
• nếu root null, thì:
  • trả về null
• if val of root <=val of p, then:
  • return inorderSuccessor (bên phải của thư mục gốc, p)
• Mặt khác
  • option:=inorderSuccessor (bên trái của thư mục gốc, p)
  • return (nếu tùy chọn bằng 0 thì hãy root, nếu không tùy chọn)

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
class Solution {
   public:
   TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
      if(!root) return NULL;
         if(root->val <= p->val){
            return inorderSuccessor(root->right, p);
         }else{
            TreeNode* option = inorderSuccessor(root->left, p);
            return !option ? root : option;
      }
   }
};
main(){
   TreeNode *root = new TreeNode(2);
   root->left = new TreeNode(1);
   root->right = new TreeNode(3);
   TreeNode *p = root->left;
   Solution ob;
   cout << (ob.inorderSuccessor(root, p))->val;
}

Đầu vào

TreeNode *root = new TreeNode(2);
root->left = new TreeNode(1);
root->right = new TreeNode(3);
1

Đầu ra

2