การหา Postorder Successor ของโหนดใน Binary Tree ด้วย C++

ในปัญหานี้ เราได้รับ Binary Tree และโหนดหนึ่งโหนด งานคือหา Postorder Successor ของโหนดนั้น (โหนดที่มาเลยในลำดับ Postorder Traversal)

ความรู้พื้นฐาน

Binary Tree คือ โครงสร้างข้อมูลต้นไม้ที่แต่ละโหนดมีลูกได้สูงสุด 2 โหนด

Postorder Traversal คือ วิธีเดินทางต้นไม้โดย: เดินซ้าย → เดินขวา → ไปที่ราก

Postorder traversal ของต้นไม้ตัวอย่าง: 8 4 2 7 9 6

ตัวอย่าง

Input − Binary Tree ตามตัวอย่าง, node = 7

Output − 9

คำอธิบาย − จากลำดับ Postorder: 8, 4, 2, 7, 9, 6 โหนดถัดจาก 7 คือ 9

วิธีแก้ที่มีประสิทธิภาพ (O(h) โดย h = ความสูงต้นไม้)

แทนที่จะหา Postorder ทั้งหมด ให้ใช้สังเกตเหล่านี้:

• ถ้าโหนดเป็นราก (Root) → ไม่มี Successor (NULL)
• ถ้าโหนดเป็นลูกขวา (Right Child) → Parent คือ Successor
• ถ้าโหนดเป็นลูกซ้าย (Left Child):
  • ถ้าไม่มีพี่ขวา (Right Sibling) → Parent คือ Successor
  • ถ้ามีพี่ขวา → Successor คือพี่ขวานั้น หรือ ลูกซ้ายสุดของพี่ขวา

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

#include <iostream>
using namespace std;

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

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

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

int main() {
    struct Node* root = insertNode(6);
    root->parent = NULL;
    root->left = insertNode(2);
    root->left->parent = root;
    root->left->left = insertNode(8);
    root->left->left->parent = root->left;
    root->left->right = insertNode(4);
    root->left->right->parent = root->left;
    root->right = insertNode(9);
    root->right->parent = root;
    root->right->left = insertNode(7);
    root->right->left->parent = root->right;
    root->left->right->left = insertNode(14);
    
    struct Node* successorNode = findPostorderSuccessor(root, root->left->right);
    if (successorNode)
        cout << "Postorder successor of " << root->left->right->value 
             << " is " << successorNode->value;
    else
        cout << "Postorder successor of " << root->left->right->value 
             << " is NULL";
    return 0;
}

ผลลัพธ์

Postorder successor of 4 is 2