Chương trình C++ triển khai cây Cartesian (Cartesian Tree)

Dưới đây là chương trình C++ triển khai cây Cartesian (Cartesian Tree).

Thuật toán

Bắt đầu
  Lớp CarTree khai báo các hàm:
    min() = Tìm chỉ số phần tử nhỏ nhất trong mảng:
      if (arr[i] < min)
        min = arr[i]
        minind = i
    inorder() = Duyệt inorder của cây:
      Nếu cây rỗng thì trả về
      inorder (node->l)
      In gốc là node->d
      inorder (node->r)
Kết thúc

Mã ví dụ

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct nod {
    int d;
    struct nod* l;
    struct nod* r;
};

class CarTree {
public:
    nod *newNode (int);
    int min(int [], int, int);
    nod *buildTree (int [], int, int);
    void inorder (nod* node);
    void show(nod *, int);
    CTree() {}
};

int CarTree::min(int arr[], int s, int e) {
    int i, min = arr[s], minind = s;
    for (i = s + 1; i <= e; i++) {
        if (arr[i] < min) {
            min = arr[i];
            minind = i;
        }
    }
    return minind;
}

nod *CarTree::buildTree (int inorder[], int s, int e) {
    if (s > e)
        return NULL;
    int i = min(inorder, s, e);
    nod *r = newNode(inorder[i]);
    if (s == e)
        return r;
    r->l = buildTree(inorder, s, i - 1);
    r->r = buildTree(inorder, i + 1, e);
    return r;
}

void CarTree::inorder (struct nod* node) {
    if (node == NULL)
        return;
    inorder (node->l);
    cout << node->d << " ";
    inorder (node->r);
}

void CarTree::show(nod *ptr, int level) {
    int i;
    if(ptr == NULL)
        return;
    if (ptr != NULL) {
        show(ptr->r, level + 1);
        cout << endl;
        for (i = 0; i < level; i++)
            cout << " ";
        cout << ptr->d;
        show(ptr->l, level + 1);
    }
}

nod *CarTree::newNode (int d) {
    nod* t = new nod;
    t->d = d;
    t->l = NULL;
    t->r = NULL;
    return t;
}

int main() {
    CarTree ct;
    int i, n;
    cout << "Nhập số phần tử cần chèn: ";
    cin >> n;
    int a[n];
    for (i = 0; i < n; i++) {
        cout << "Nhập phần tử " << i + 1 << " : ";
        cin >> a[i];
    }
    nod *r = ct.buildTree(a, 0, n - 1);
    cout << "Cấu trúc cây Cartesian: " << endl;
    ct.show(r, 1);
    cout << endl;
    cout << "\n Duyệt inorder của cây \n" << endl;
    ct.inorder(r);
    cout << endl;
    return 0;
}

Kết quả đầu ra

Nhập số phần tử cần chèn: 10
Nhập phần tử 1 : 10
Nhập phần tử 2 : 30
Nhập phần tử 3 : 20
Nhập phần tử 4 : 40
Nhập phần tử 5 : 50
Nhập phần tử 6 : 70
Nhập phần tử 7 : 60
Nhập phần tử 8 : 80
Nhập phần tử 9 : 100
Nhập phần tử 10 : 112
Cấu trúc cây Cartesian:
112
100
80
60
70
50
40
20
30
10
Duyệt inorder của cây
10 30 20 40 50 70 60 80 100 112