http://kmlinux.fjfi.cvut.cz/~culik/zalg/Tree05.zip

#include "stdafx.h"
 
#include "form.h"
#include "tree.h"
 
#include <string>
using namespace std;
 
const int MAX = 4;
 
struct Item
{
    int cnt; // pocet klicu , 1 <= cnt <= MAX ( obcas MAX+1 )
    int key [MAX + 1]; // key [0] ... key [cnt-1]
    Item * ptr[MAX + 2]; // ptr [0] ... ptr [cnt],  ukazatelu je o jedna vice nez klicu
    Item ();
};
 
Item::Item() 
{
    cnt = 0;
    for (int i = 0; i <= MAX; i++) key[i] = -1;
    for (int i = 0; i <= MAX+1; i++) ptr[i] = nullptr;
}
 
void insert (Item * p, int inx, int new_key, Item * new_ptr)
// vlozit do bloku p
// vlozit na pozici inx , (0 <= inx <= p->cnt)
// vlozit novy klic a za nim novy ukazatel
{
    for (int i = p->cnt - 1; i >= inx; i--)
    {
        p->key[i + 1] = p->key[i]; 
    }
    for (int i = p->cnt; i >= inx + 1; i--)
    {
        p->ptr[i + 1] = p->ptr[i];
    }
    p->key[inx] = new_key;
    p->ptr[inx + 1] = new_ptr;
    p->cnt++;
}
 
void split(Item * p, int a, int & new_key, Item * & new_ptr)
// rozdelit blok p
// v puvodnim bloku p ponechat a klicu
// vysledkem je delici bod new_key
// a novy blok new_ptr
{
    int b = p->cnt-1-a;
    new_key = p->key[a];
    Item * t = new Item;
    new_ptr = t;
    t->cnt = b;
    for (int i = 0; i < b; i++) {
        t->key[i] = p->key[a + 1 + i];
    }
    for (int i = 0; i < b + 1; i++) {
        t->ptr[i] = p->ptr[a + 1 + i];
    }
    for (int i = a; i < p->cnt; i++) {
        p->key[i] = -1;
    }
    for (int i = a + 1; i < p->cnt + 1; i++) {
        p->ptr[i] = nullptr;
    }
    p->cnt = a;
}
 
void store(Item * p, int val)
{
    int i = 0;
    while (i < p->cnt && p->key[i] < val) { i++; }
    // i = 0 ... p->cnt
 
    if (i < p->cnt && val == p->key[i]) { /* duplicita klicu */}
    else {
        Item * u = p->ptr[i]; // vetev kam val patri
        if (u == nullptr)
        {
            // jsem na dne, vkladam do bloku p
            insert(p, i, val, nullptr);
        }
        else
        {
            // je zde dalsi, nizsi vetev
            store(u, val);
            if (u->cnt > MAX) {
                int new_key;
                Item * new_ptr;
                split(u, MAX / 2, new_key, new_ptr);
                insert(p, i, new_key, new_ptr);
 
            }
        }
    }
}
 
void enter (Item * & p, int val)
{
    if (p == nullptr) {
        p = new Item;
        p->cnt = 1; p->ptr[0] = nullptr; p->key[0] = val; p->ptr[1] = nullptr;
    }
    else {
        store(p, val);
        if (p->cnt > MAX) {
                int new_key;
                Item* new_ptr;
                split(p, MAX / 2, new_key, new_ptr);
                Item* r = new Item;
                r->cnt = 1; r->ptr[0] = p; r->key[0] = new_key; r->ptr[1] = new_ptr;
                p = r;
        }
    }
}
 
void display (Item * p)
{
    if (p != nullptr) 
    {
        openBranch("*");
        for (int i = 0; i < p->cnt; i++)
        {
            display(p->ptr[i]);
            addNode(to_string(p->key[i]));
        }
        display(p->ptr[p->cnt]);
        closeBranch();
    }
}
 
void run()
{
    Item * root = nullptr;
    enter(root, 30);
    enter(root, 20);
    enter(root, 25);
    enter(root, 40);
    enter(root, 50);
    for (int i = 1; i <= 20; i++) {
        enter(root, i);
    }
 
    display(root);
 
    print ("Hello");
    status ("O.K.");
}