Preorder Successor ของโหนดในต้นไม้ไบนารีใน C++

ในปัญหานี้ เราได้รับต้นไม้ไบนารีและค่าโหนด งานของเราคือพิมพ์ preorder successor ของโหนด

Binary Tree เป็นประเภทต้นไม้พิเศษที่โหนดรากแต่ละตัวสามารถมีโหนดลูกได้สูงสุด 2 ตัว

Preorder Traversal เป็นวิธีการเดินทางโหนดของต้นไม้ ในนี้เราจะเดินทางโหนดรากก่อน แล้วลูกซ้าย และจากนั้นลูกขวา

Preorder successor node คือโหนดที่มาถัดจากโหนดใน preorder traversal ของโหนด

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหา

Input: 9 Output 0
Explanation: the preorder traversal of the tree is: 5 9 0 1 2 5. So the preorder successor of 9 is 0.

ในการแก้ปัญหานี้ วิธี navie จะเป็นการหา preorder traversal ของ binary tree แล้วพิมพ์องค์ประกอบที่มาหลังจากตัวเลขที่กำหนด

วิธีแก้ปัญหาที่มีประสิทธิภาพมากกว่าจะเกี่ยวข้องกับการตรวจสอบตำแหน่งของตัวเลขที่กำหนดและจากนั้นค้นหา successor ตามตำแหน่ง ดังนั้น ถ้าตำแหน่งมีลูกซ้าย preorder successor คือลูกซ้าย ถ้าเป็น leaf node แต่เป็นลูกซ้าย น้องชายของมันคือ preorder successor ถ้าเป็น leaf node และไม่ใช่ลูกซ้าย เราต้องเคลื่อนขึ้นไปยัง ancestor nodes ที่โหนดลูกของพวกเขาจะเป็น preorder successor

โปรแกรมจะทำให้วิธีแก้ปัญหาชัดเจนขึ้น

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

struct Node {
    struct Node *left, *right, *parent;
    int key;
};

Node* insertNode(int key){
    Node* temp = new Node;
    temp->left = temp->right = temp->parent = NULL;
    temp->key = key;
    return temp;
}

Node* preOrderSuccessorNode(Node* root, Node* n){
    if (n->left)
        return n->left;
    Node *curr = n, *parent = curr->parent;
    while (parent != NULL && parent->right == curr) {
        curr = curr->parent;
        parent = parent->parent;
    }
    if (parent == NULL)
        return NULL;
    return parent->right;
}

int main(){
    Node* root = insertNode(99);
    root->parent = NULL;
    root->left = insertNode(4);
    root->left->parent = root;
    root->left->left = insertNode(18);
    root->left->left->parent = root->left;
    root->left->right = insertNode(50);
    root->left->right->parent = root->left;
    root->right = insertNode(26);
    root->right->parent = root;
    root->right->left = insertNode(5);
    root->right->left->parent = root->right;
    root->right->right = insertNode(10);
    root->right->right->parent = root->right;
    Node* preOrder = preOrderSuccessorNode(root, root->left->right);
    if (preOrder) {
        cout<<"Preorder successor of "<<root->left->right->key<<" is "<<preOrder->key;
    } else {
        cout<<"Preorder successor of "<<root->left->right->key<<" is NULL";
    }
    return 0;
}

ผลลัพธ์

Preorder successor of 50 is 26