ibd

#include <iostream>
using namespace std;

// дефинираме тип - указател към структурата node
typedef struct node *po;

// създаване на структурата node
struct node {
    int data;
    po left, right;
};

// алгоритъм за построяване на
// Идеално Балансирано Дърво (ИБД)
po ibd(int n) {

    // условие за дъно на рекурсията
    // броя на оставащите елементи
    // да е по-голям от 0
    if (n>0) {

        // разделяне на елементите
        // на две (ляво и дясно поддърво)
        int nLeft = n/2;
        int nRight = n-nLeft-1;

        // дефиниране на буферна променлива
        // и променлива, чиято стойност бива
        // въвеждана от потребителя
        po buffer = new node;
        int userInput;

        // зареждане на буфера с стойността
        // въведена от потребителя
        cin>>userInput;
        buffer->data=userInput;

        // рекурсивно извикване на същатата функция
        // за построяване на поддърветата
        buffer->left = ibd( nLeft );
        buffer->right = ibd( nRight );

        // връщане на записаната в буфера стойност, на указателя
        return buffer;
    }
    // ако няма повече елементи,
    // за добавяне, връщаме NULL
    return NULL;
}

void print_tab(int n){
    for(int i=0;i<n;i++){
        cout<<"    ";
    }
}
void print_tree(node* n,int tab){
    if(n->right != NULL){
        print_tree(n->right,tab+1);
    }
    print_tab(tab);
    cout<<n->data<<endl;
    if(n->left != NULL){
        print_tree(n->left,tab+1);
    }
}

// функция за ИНФИКСНО разпечатване
// ЛЯВО - КОРЕН - ДЯСНО
void infix(node* n) {
    if(n) {
        infix(n->left);
        cout<< n->data << " ";
        infix(n->right);
    }
}

// функция за ПРЕФИКСНО разпечатване
// КОРЕН - ЛЯВО - ДЯСНО
void prefix(node* n) {
    if(n) {
        cout<< n->data << " ";
        prefix(n->left);
        prefix(n->right);
    }
}

// функция за ПОСТФИКСНО разпечатване
// ЛЯВО - ДЯСНО - КОРЕН
void postfix(node* n) {
    if(n) {
        postfix(n->left);
        postfix(n->right);
        cout<< n->data << " ";
    }
}

// Алгоритъм за търсене в ИБД.
// Ако съществува търсеният елемент се извежда позицията,
// на която се намира.
void search(int x, po loc, int& pos) {

    // Ако съществуват още елементи в ИБД
    if( loc ) {

        pos++; //увеличаваме позицията с 1

        // ако това е търсеният елемент
        // прекратяваме изпълнението
        if(loc->data == x) {
            cout << "found at: " << pos << endl;
            return;
        }

        // ако все още не сме го намерили
        // търсим в лявото и дясното поддървета
        else {
            search(x, loc->left, pos);
            search(x, loc->right, pos);
        }
    }
}

int main () {

    // дефиниране и въвеждане на брой
    // възли в идеално балансираното дърво
    int n;
    cin >> n;

    // дефиниране и създаване на ИБД
    po root = NULL;
    root = ibd(n);

    print_tree(root, 3);

    // принтиране на стойностите
    infix(root);
    cout << endl;
    prefix(root);
    cout << endl;
    postfix(root);
    cout << endl;

    // търсене в ИБД
    int pos = 0;
    search(3, root, pos);

    return EXIT_SUCCESS;
    system("PAUSE");
}