Xây dựng cây nhị phân đặc biệt từ duyệt inorder trong C++

Cho mảng arr[] là duyệt inorder của cây. Cây đặc biệt: gốc lớn hơn cả hai con. Xây dựng cây bằng cách chọn phần tử lớn nhất làm gốc, phần bên trái thành cây con trái, bên phải thành cây con phải, lặp đệ quy.

Ví dụ

Input: arr[] = {10, 20, 28, 40, 32, 31, 30}

Output: Cây đặc biệt với inorder như đầu vào.

Ví dụ hoàn chỉnh

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

int total(int arr[], int first, int last);

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;
}

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;
}

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;
}

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 << "Duyệt inorder của cây đặc biệt: ";
    Inorder_traversal(root);
    return 0;
}

Kết quả

Duyệt inorder của cây đặc biệt: 10 20 28 40 32 31 30