แปลง BST เป็น Binary Tree โดยบวกผลรวมคีย์ที่มากกว่าเข้าไปในทุกคีย์ใน C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมแปลง Binary Search Tree (BST) ให้กลายเป็น Binary Tree โดยที่ผลรวมของคีย์ที่มากกว่าทั้งหมดจะถูกบวกเข้าไปในคีย์ปัจจุบัน

เราจะได้รับ BST มา 1 ต้น งานของเราคือแปลงต้นไม้นั้นให้กลายเป็น Binary Tree โดยที่แต่ละโหนดจะมีค่าเท่ากับค่าเดิมบวกกับผลรวมของคีย์ที่มากกว่ามันทั้งหมด การทำงานนี้จะทำได้โดยการท่องต้นไม้แบบ Inorder ย้อนกลับ (Reverse Inorder) พร้อมกับเก็บผลรวมขององค์ประกอบที่ผ่านมาแล้ว และบวกเข้าไปในองค์ประกอบปัจจุบัน

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

#include <bits/stdc++.h>
using namespace std;

// โครงสร้างโหนดของ BST
struct node {
    int key;
    struct node* left;
    struct node* right;
};

// สร้างโหนดใหม่ที่ไม่มีลูก
struct node* newNode(int key) {
    struct node* node = (struct node*)malloc(sizeof(struct node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    return (node);
}

// ท่อง BST แบบ Reverse Inorder และบวกผลรวม
void reverse_BST(struct node* root, int* sum_ptr) {
    if (root == NULL)
        return;
    reverse_BST(root->right, sum_ptr);
    // บวกองค์ประกอบตามลำดับ
    *sum_ptr = *sum_ptr + root->key;
    root->key = *sum_ptr;
    reverse_BST(root->left, sum_ptr);
}

// ใช้ผลรวมและอัปเดตค่า
void change_greater(struct node* root) {
    int sum = 0;
    reverse_BST(root, &sum);
}

// พิมพ์การท่อง Inorder
void printInorder(struct node* node) {
    if (node == NULL)
        return;
    printInorder(node->left);
    cout << node->key << " ";
    printInorder(node->right);
}

int main() {
    node* root = newNode(5);
    root->left = newNode(2);
    root->right = newNode(13);
    cout << "Given Tree : " << endl;
    printInorder(root);
    change_greater(root);
    cout << endl;
    cout << "Modified Tree : " << endl;
    printInorder(root);
    return 0;
}

ผลลัพธ์

Given Tree : 2 5 13
Modified Tree : 20 18 13