home

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

โปรแกรมหา Inorder Successor ของ binary search tree ใน C++

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

เช่น ถ้าอินพุทเป็นแบบ

โปรแกรมหา Inorder Successor ของ binary search tree ใน C++

และ p = 1 ผลลัพธ์จะเป็น 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; }

อินพุท

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

เอาต์พุท

2