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

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

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

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

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

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

Input: 1 Output: 9

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

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

โปรแกรมแสดงการนำวิธีแก้ปัญหาไปใช้

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

#include <iostream>
using namespace std;

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

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

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

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* preOrderPredecessor = preOrderPredecessorNode(root, root->left->right);
    if (preOrderPredecessor)
        cout<<"Preorder Predecessor of "<<root->left->right->key<<" is "<<preOrderPredecessor->key;
    else
        cout<<"Preorder Predecessor of "<<root->left->right->key<<" is NULL";
    return 0;
}

ผลลัพธ์

Preorder Predecessor of 50 is 18