home

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

Inorder Successor in BST ใน C++

สมมติว่ามี binary search tree และโหนดในมัน เราต้องค้นหา in-order successor ของโหนดนั้นใน BST ตามที่เรารู้ว่า successor ของโหนด p คือโหนดที่มีคีย์น้อยที่สุดที่มากกว่า p.val

เช่น ถ้าอินพุทเป็น root = [2,1,3], p = 1

Inorder Successor in BST ใน C++

ผลลัพธ์จะเป็น 2

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

  • กำหนดเมธอดเรียกซ้ำ inorderSuccessor() รับ root และ p

  • ถ้า root เป็น null แล้ว −

    • คืนค่า null

  • ถ้าค่าของ root <= ค่าของ p แล้ว −

    • คืนค่า inorderSuccessor(right ของ root, p)

  • มิฉะนั้น

    • option := inorderSuccessor(left ของ root, p)

    • คืนค่า (ถ้า option เป็นศูนย์ แล้ว root มิฉะนั้น option)

ตัวอย่าง

ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −

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

อินพุท

{2,1,3},1

เอาต์พุท

2