#include<iostream>
using namespace std;
 
struct node {
    node *p;
    node *l;
    node *r;
    int val;
};
 
void insert(node *&root, int x, node *p = NULL) {  //dodawawanie elementu
    if (root == NULL) {
        root = new node;
        root->val = x;
        root->l = root->r = NULL;
        root->p = p;
        cout << "wstawiamy: " << root->val << endl;
    }
    else if (x < root->val) {
        insert(root->l, x, root);
    }
    else {
        insert(root->r, x, root);
    }
}
 
void inorder(node *&root) {  //przeszukiwanie (ciag niemalejacy)
    if (root != NULL) {
        inorder(root->l);
        cout << root->val << " ";
        inorder(root->r);
    }
}
 
node* search_rec(node *&root, int x) { //wyszukiwanie rekurencyjne
    if (root != NULL) {
        if (x == root->val) {
            cout << "wartosc znaleziona: " << root->val << endl;
            return root;
        }
        else if (x < root->val) {
            search_rec(root->l, x);
        }
        else {
            search_rec(root->r, x);
        }
    }
   
}
 
 
node* min(node *root) { //najmniejsza wartosc
    if (root != NULL) {
        while (root->l) {
            root = root->l;
        }
 
        //cout << "minimalna wartosc to: " << root->val << endl;
        return root;
    }
}
 
node* max(node *root) {  //najwieksza wartosc
    if (root != NULL) {
        while (root->r) {
            root = root->r;
        }
 
        //cout << "maksymalna wartosc to: " << root->val << endl;
        return root;
    }
 
}
 
node* prev(node *root, int liczba) { //znajdowanie poprzednika
    root = search_rec(root, liczba);
    if (root->l != NULL) {
        cout << "poprzednik to: " << (max(root->l))->val << endl;
        return max(root->l);
    }
    else {
        while (root->p) {
            if (root->p->r == root) {
                cout << "poprzednik to: " << root->p->val << endl;
                return root->p;
            }
            else root = root->p;
        }
        cout << "nie ma poprzednika " << endl;
        return 0;
    }
}
 
int counter(node *&root) {
    int i = 0;
    if (root == NULL) {
        return i;
    }
    else{
        i = 1;
        if (root->l) {
            i = i + counter(root->l);
        }
        if (root->r) {
            i = i + counter(root->r);
        }
    }
    return i;
}
 
float avg1(node *&root) {
    float average = 0;
    //average = root->val;
    if (root != NULL) {
            average = root->val;
            if (root->l) {
                average = average + avg1(root->l);
            }
            if (root->r) {
                average = average + avg1(root->r);
            }
    }
    return average;
}
 
float avg2(node *&root) {
    float i = float(counter(root));
    float average = (avg1(root)) / i;
    return average;
}
 
void deleaves(node *&root) {
    if (root) {
        if ((root->l || root->r) == NULL) {
            if (root->p->l == root) {
                root->p->l = NULL;
            }
            else if (root->p->r == root) {
                root->p->r = NULL;
            }
            delete root;
        }
        else {
            deleaves(root->l);
            deleaves(root->r);
        }
    }
}
 
node* del(node *root, int x)
{
    if (root==NULL) return root;
    else if (x < root->val)
        root->l = del(root->l, x);
   
    else if (x > root->val) {
        root->r = del(root->r, x);
    }
    else{
        if (root->r == NULL && root->l == NULL){
            delete root;
            root = NULL;
        }
        else if (root->r == NULL){
            node *pom = root;
            root = root->l;
            delete pom;
        }
        else if (root->l == NULL){
            node *pom = root;
            root = root->r;
            delete pom;
        }
        else{
            node *pom = prev(root, x);
            root->val = pom->val;
            root->l = del(root->l, pom->val);
        }
    }
    return root;
}
 
 
int main() {
    node *root = NULL;
    node *p = NULL;
    insert(root, 4);
    insert(root, 2);
    insert(root, 14);
    insert(root, 0);
    insert(root, 3);
    insert(root, 11);
    insert(root, 6);
    insert(root, 15);
    insert(root, 7);
    insert(root, 8);
    inorder(root);
    cout << endl;
    del(root, 4);
    inorder(root);
    cout << endl;
    //cout << "srednia: " << avg2(root) << endl;
    //cout << "ilosc: " << counter(root) << endl;
    //max(root);
    //prev(root, 0);
   
    system("PAUSE");
    return 0;
}