สร้าง Special Binary Tree จาก Inorder Traversal ใน C++

โจทย์: ให้ Inorder traversal ของต้นไม้ ต้องการสร้าง Special Binary Tree โดยที่โหนดแม่มีค่ามากกว่าลูกซ้ายและลูกขวาเสมอ (Max-Heap property บน Inorder sequence)

แนวคิด

เลือกค่าสูงสุดในช่วง array เป็นราก แล้วสร้างซ้ายและขวาแบบเวียนเกิด (Recursive) จากส่วนซ้ายและขวาของค่าสูงสุด

ฟังก์ชันสำคัญ

// หาดัชนีของค่าสูงสุดในช่วง [first, last]
int total(int arr[], int first, int last) {
    int highest = arr[first];
    int lowest = first;
    for (int i = first + 1; i <= last; i++) {
        if (arr[i] > highest) {
            highest = arr[i];
            lowest = i;
        }
    }
    return lowest;
}

// สร้างต้นไม้แบบเวียนเกิด
tree_node* create_tree(int arr[], int first, int last) {
    if (first > last) return NULL;
    
    int temp = total(arr, first, last);  // ดัชนีค่าสูงสุด
    tree_node* parent = new_node(arr[temp]);
    
    if (first == last) return parent;  // ใบ
    
    parent->left = create_tree(arr, first, temp - 1);
    parent->right = create_tree(arr, temp + 1, last);
    return parent;
}

ตัวอย่างเต็ม

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

class tree_node {
public:
    int data;
    tree_node* left;
    tree_node* right;
};

tree_node* new_node(int data) {
    tree_node* newNode = new tree_node();
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int total(int arr[], int first, int last) {
    int highest = arr[first];
    int lowest = first;
    for (int i = first + 1; i <= last; i++) {
        if (arr[i] > highest) {
            highest = arr[i];
            lowest = i;
        }
    }
    return lowest;
}

tree_node* create_tree(int arr[], int first, int last) {
    if (first > last) return NULL;
    int temp = total(arr, first, last);
    tree_node* parent = new_node(arr[temp]);
    if (first == last) return parent;
    parent->left = create_tree(arr, first, temp - 1);
    parent->right = create_tree(arr, temp + 1, last);
    return parent;
}

void Inorder_traversal(tree_node* node) {
    if (node == NULL) return;
    Inorder_traversal(node->left);
    cout << node->data << " ";
    Inorder_traversal(node->right);
}

int main() {
    int arr[] = {10, 20, 28, 40, 32, 31, 30};
    int size = sizeof(arr)/sizeof(arr[0]);
    tree_node* root = create_tree(arr, 0, size - 1);
    cout << "Inorder traversal of constructed tree: ";
    Inorder_traversal(root);
    return 0;
}

ผลลัพธ์

Inorder traversal of constructed tree: 10 20 28 40 32 31 30

คุณสมบัติ: ต้นไม้ที่ได้จะเป็น Max-Heap และ Inorder traversal จะได้ array เดิมกลับมา