algorytmika 2

#include <iostream>
#include <cmath>
#include <array>

using namespace std;

struct Node {
    Node* parent;
    Node* left_child;
    Node* right_child;
    int v;
    int bf;
    int h;
};

void nodeHeight(Node*&node) {
    if (node) {
        int l_c = 0;
        int r_c = 0;
        if(node->left_child) {
            l_c = node->left_child->h;
        }
        if (node->right_child) {
            r_c = node->right_child->h;
        }
        node->bf = abs(l_c - r_c);
        nodeHeight(node->left_child);
        nodeHeight(node->right_child);
    }
}

int getHeight(Node* &node) {
    if (!node) {
        return 0;
    }
    else {
        int left_h = getHeight(node->left_child);
        int right_h = getHeight(node->right_child);
        if (right_h > left_h) {
            node->h = right_h + 1;
        }
        else {
            node->h = left_h + 1;
        }
    }
}

void printPRE_ORDER(Node* node) {
    if (node) {
        cout << node->v << ":" <<"Bf: "<< node->bf << " " << "My height: " << node->h << endl;
        printPRE_ORDER(node->left_child);
        printPRE_ORDER(node->right_child);
    }
}

void printIN_ORDER(Node* node) {
    if (node) {
        printIN_ORDER(node->left_child);
        cout << node->v << ":" << node->bf << " ";
        printIN_ORDER(node->right_child);
    }
}

void del_node_postorder(Node*&node) {
    if (node->left_child) {
        del_node_postorder(node->left_child);
    }
    if (node->right_child) {
        del_node_postorder(node->right_child);
    }
    delete node;
}

Node* deleteNode(Node*&node, int value) {
    Node* root = node;
    while (node) {
        if (value > node->v) {
            node = node->right_child;
        }
        else if (value < node->v) {
            node = node->left_child;
        }
        else {
            break;
        }
    }
    // sam liść
    if (node->left_child == NULL && node->right_child == NULL) {
        if (node->parent->left_child !=NULL && node->parent->left_child->v == node->v) {
            node->parent->left_child = NULL;
        }
        else {
            node->parent->right_child = NULL;
        }
        delete node;
    }
    // istnieje lewe dziecko
    else if (node->left_child != NULL && node->right_child == NULL) {
        //którym dzieckiem jest node względem swojego rodzica
        if (node->parent->left_child != NULL && node->parent->left_child->v == node->v) {
            node->parent->left_child = node->left_child;
            node->left_child->parent = node->parent;
        }
        else {
            node->parent->right_child = node->left_child;
            node->left_child->parent = node->parent;
        }
        delete node;
    }
    //istnieje prawe dziecko
    else if (node->left_child == NULL && node->right_child != NULL) {
        //którym dzieckiem jest node względem swojego rodzica
        if (node->parent->left_child != NULL && node->parent->left_child->v == node->v) {
            node->parent->left_child = node->right_child;
            node->right_child->parent = node->parent;
        }
        else {
            node->parent->right_child = node->right_child;
            node->right_child->parent = node->parent;
        }
        delete node;
    }
    //posiada dwoje dziecki

    else {
        Node* tmp = node;
        node = node->right_child;
        while (node->left_child) {
            node = node->left_child;
        }
        tmp->v = node->v;
        //TU Kopiuje
        // sam liść
        if (node->left_child == NULL && node->right_child == NULL) {
            if (node->parent->left_child != NULL && node->parent->left_child->v == node->v) {
                node->parent->left_child = NULL;
            }
            else {
                node->parent->right_child = NULL;
            }
            delete node;
        }
        // istnieje lewe dziecko
        else if (node->left_child != NULL && node->right_child == NULL) {
            //którym dzieckiem jest node względem swojego rodzica
            if (node->parent->left_child != NULL && node->parent->left_child->v == node->v) {
                node->parent->left_child = node->left_child;
                node->left_child->parent = node->parent;
            }
            else {
                node->parent->right_child = node->left_child;
                node->left_child->parent = node->parent;
            }
            delete node;
        }
        //istnieje prawe dziecko
        else if (node->left_child == NULL && node->right_child != NULL) {
            //którym dzieckiem jest node względem swojego rodzica
            if (node->parent->left_child != NULL && node->parent->left_child->v == node->v) {
                node->parent->left_child = node->right_child;
                node->right_child->parent = node->parent;
            }
            else {
                node->parent->right_child = node->right_child;
                node->right_child->parent = node->parent;
            }
            delete node;
        }
    }

    return root;
}

Node* bts_search(Node* root) {
    if (root && root->bf <= 1) {
        bts_search(root->left_child);
        bts_search(root->right_child);
    }
    else {
        return root;
    }
}
bool isBalanced(Node* root) {
    if (root && root->bf <= 1) {
        bts_search(root->left_child);
        bts_search(root->right_child);
    }
    else if(root && root->bf > 1){
        return false;
    }
}

void findMax(Node* node, int &max) {
    if (node) {
        max = node->v;
        cout << "Element sciezki: " << max << endl;
        findMax(node->right_child, max);
    }
}
void findMin(Node* node, int& min) {
    if (node) {
        min = node->v;
        cout << "Element sciezki: " << min << endl;
        findMin(node->left_child, min);
    }
}

void insert(Node* &root, int value) {
    Node *node, *parent;
    node = new Node;
    //setting everything to the default settings.
    node->left_child = NULL;
    node->right_child = NULL;
    node->parent = NULL;
    node->v = value;
    node->bf = 0;

    parent = root;
    if(!parent){
        root = node;
    }
    else {
        while (true) {
            //reaching the proper destination of the new node
            if (value <= parent->v) {
                if (!parent->left_child) {
                    parent->left_child = node;
                    break;
                }
                parent = parent->left_child;
            }
            else {
                if (!parent->right_child) {
                    parent->right_child = node;
                    break;
                }
                parent = parent->right_child;
            }
        }

    }
    //after reaching the destination setting the parent for a node
    node->parent = parent;
}

Node* balanceTree(Node*& node) {
    Node* root = node;
    Node* tmp = NULL;
    do {
        tmp = bts_search(node);
        if (tmp) {
            int value, value_child;
            value = tmp->v;
            Node* tmp_1;
            if (tmp->left_child && tmp->right_child) {
                cout << "Mam oba dzieci" << endl;
                if (tmp->left_child->h > tmp->right_child->h) {
                    tmp_1 = tmp->left_child;
                    while (tmp_1->right_child) {
                        tmp_1 = tmp_1->right_child;
                    }
                    value_child = tmp_1->v;
                    root = deleteNode(root, value_child);
                    tmp->v = value_child;
                    insert(root, value);
                }
                else {
                    tmp_1 = tmp->right_child;
                    while (tmp_1->left_child) {
                        tmp_1 = tmp_1->left_child;
                    }
                    value_child = tmp_1->v;
                    root = deleteNode(root, value_child);
                    tmp->v = value_child;
                    insert(root, value);
                }
            }
            else if (tmp->left_child && !tmp->right_child) {
                cout << "Mam lewe dziecko" << endl;
                tmp_1 = tmp->left_child;
                while (tmp_1->right_child) {
                    tmp_1 = tmp_1->right_child;
                }
                value_child = tmp_1->v;
                root = deleteNode(root, value_child);
                tmp->v = value_child;
                insert(root, value);
            }
            else if (!tmp->left_child && tmp->right_child) {
                cout << "Mam prawe dziecko" << endl;
                tmp_1 = tmp->right_child;
                while (tmp_1->left_child) {
                    tmp_1 = tmp_1->left_child;
                }
                value_child = tmp_1->v;
                root = deleteNode(root, value_child);
                tmp->v = value_child;
                insert(root, value);
            }
            else {
                cout << "Bez dzieci" << endl;
            }
            getHeight(root);
            nodeHeight(root);
        }
    } while (tmp != NULL);


    return root;
}

void findElement(int* tab, int first, int last, Node*& root) {
    int index = (last + first) / 2;
    if (last >= first) {
        insert(root, tab[index]);
        findElement(tab, first, index - 1, root);
        findElement(tab, index + 1, last, root);
    }
}
void insert_sort(int* arr, int len) {
    int tmp;
    int j;
    for (int i = 0; i < len - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            tmp = arr[i + 1];
            int j = i;
            while (j >= 0 && arr[j] > tmp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = tmp;
        }
    }
}

int main()
{
    int max_value, min_value;
    int tab[] = {10,3,2,1,6,4,7,20,30,23};
    int n = sizeof(tab) / sizeof(int);
    Node* root = NULL;
    for (int i = 0; i < n; i++) {
        insert(root, tab[i]);
    }
    /*
    //insert_sort(tab, n);
    cout << endl;
    //findElement(tab, 0, n-1, root);
    findMax(root, max_value);
    findMin(root, min_value);
    cout << max_value << " <-MAX\n";
    cout << min_value << " <-MIN\n";
    //findElement1(tab, 0, 8, root);

    //printIN_ORDER(root);
    //del_node_postorder(root);
    //nodeHeight(root);
    getHeight(root);
    nodeHeight(root);
    //cout << endl;

    Node* tmp = bts_search(root);
    cout << tmp->v << endl;

    root = balanceTree(root);
    cout << endl;
    printPRE_ORDER(root);
    */

}