laby AVL 1

// AVLTREE.cpp : Defines the entry point for the console application.
//
// BSTree.cpp: definiuje punkt wejścia dla aplikacji konsolowej.
//

// Drzewo AVL

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>

using namespace std;



struct node {
    node *up;
    node *left;
    node *right;
    int key;
    int bf;
};

void loadFile(node *& root);


void printBT(string sp, string sn, node * root);
node * minBST(node * root);
node * maxBST(node * root);
node * findBST(node * root, int value);
void inorder(node * root);
void saveFile(node *root);
void addNode(node ** root, int value);
node *create(int value);
void deleteNode(node **root, int value);
void removeBST(node * & root, int value);

int _tmain(int argc, _TCHAR* argv[])
{

    node *root = new node;
    root = NULL;
    node *temp = new node;
    temp = NULL;
    int option, value;
    do {
        cout << "1. Add NOde" << endl;
        cout << "2. Load File" << endl;
        cout << "3. Store File" << endl;
        cout << "4. Minimum" << endl;
        cout << "5. Maximum" << endl;
        cout << "6. Find value" << endl;
        cout << "7. InOrder " << endl;
        cout << "8. Usuwanie element" <<endl;
        cout << "10. Print Tree" << endl;
        cout << "\nPodaj opcje: ";
        cin >> option;


        switch (option) {
        case 1:
            cout << "Podaj liczbe: " << endl;
            cin >> value;
            addNode(&root, value);
            cout << "root " << root << "wartość " << root->key;
            break;
        case 2:
            loadFile(root);
            break;
        case 3:
            saveFile(root);
            break;
        case 4:
            cout << "Minimalny element to" << minBST(root)->key << endl;
            break;
        case 5:
            cout << "Maksymalny element to" << maxBST(root)->key << endl;
            break;
        case 6:
            cout << "Podaj liczbe: " << endl;
            cin >> value;
            temp = findBST(root, value);
            if (temp != NULL) {
                cout << "Znaleziony element  " << temp->key << " pod adresem " << temp << endl;
            }
            else cout << "Nie ma takiego elementu";
            break;
        case 7:
            inorder(root);
            break;
        case 8:
            cout << "Podaj liczbe: " << endl;
            cin >> value;
            removeBST(root, value);
            break;
        case 10:
             printBT(" "," " , root);
             break;

        }

        cout << "\n\n";

    } while (option != 0);


    return 0;
}

void addNode(node ** root, int value) {
    node *newNode = create(value);
    node *temp ,*p;
    temp=*root;
    if (*root == NULL) {
        *root = newNode;
    }
    else if (value < temp->key) {
        if (temp->left) {
            addNode(&temp->left, value);
        }
        else {
            newNode->up = temp;
            temp->left = newNode;
        }
    }
    else if (value > temp->key) {
        if (temp->right) {
            addNode(&temp->right, value);
        }
        else {
            newNode->up = temp;
            temp->right = newNode;
        }
    }
    int end=1;
    p=temp;
    temp=newNode;
    // aktualnie p wskazuje na rodzica new Node
    while (!p!=!end){   //xor
        if(p->left==temp) p->bf+=1;
        else if (p->right==temp)p->bf-=1;
        if(p->bf==2 || p->bf==-2) end=0; // gdy nie zgodne wychodzi
        else{
            temp=p;
        p=p->up;
        }

    }
}

void loadFile(node *&root) {
    int idx;
    fstream plik;
    plik.open("AVLdata.txt", ios::in);
    if (plik) {
        while (!plik.eof()) {
            plik >> idx;
            addNode(&root, idx);
        }
        cout << "Plik wczytany" << endl;
    }
    plik.close();
}

// rekurencyjny zapis do pliku IN ORDER
void saveFile(node *root) {
    ofstream plik;
    plik.open("result.txt", ios::out | ios::app);

    if (root->left)
        saveFile(root->left);

    plik << root->key << " ";

    if (root->right)
        saveFile(root->right);

    plik.close();
}

node * minBST(node * root) {
    while (root->left) {
        root = root->left;
    }
    return root;
}

node * maxBST(node * root) {
    while (root->right) {
        root = root->right;
    }
    return root;
}

node * findBST(node * root, int value)
{
    while (root) {
        if (value == root->key)
            return root;
        else if (value < root->key)
            root = root->left;
        else if (value > root->key)
            root = root->right;
    }
    return NULL;
}
 node *create(int value) {
     node *newNode = new node;
     newNode = new node;
     newNode->up = NULL;
     newNode->left = NULL;
     newNode->right = NULL;
     newNode->key = value;
     return newNode;
}

void printBT(string sp, string sn, node * root)
{
    string s;
    string cr, cl, cp;
    cr = cl = cp = "  ";
    cr[0] = 218; cr[1] = 196;
    cl[0] = 192; cl[1] = 196;
    cp[0] = 179;

    if (root)
    {
        s = sp;
        if (sn == cr) s[s.length() - 2] = ' ';
        printBT(s + cp, cr, root->right);

        s = s.substr(0, sp.length() - 2);
        cout << s << sn << root->key <<" "<<root->bf << endl;

        s = sp;
        if (sn == cl) s[s.length() - 2] = ' ';
        printBT(s + cp, cl, root->left);
    }
}

void inorder(node * root) {
    if (root->left)
        inorder(root->left);
    cout << root->key << " ";
    if (root->right)
        inorder(root->right);

}



void removeBST(node * & root, int value)
{
    node *A = findBST(root, value);
    node * B, *C;

    if (A)
    {


        //Jesli A ma obu potomków to B= nastepnik A ( tu zawsze min od A->right)
        //jak ma jednego lub mniej to B=A

        if (A->left && A->right) B = minBST(A->right);
        else B = A;

        // C wskazuje syna B lub NULL
        if (B->left) C = B->left;
        else C = B->right;

        // Jeśli syn B istnieje, to zastąpi C w drzewie dowiąznie up
        if (C) C->up = B->up;

        // B zostaje zastąpione przez C w drzewie
        if (!B->up) root = C;
        else if (B == B->up->left) B->up->left = C;
            else  B->up->right = C;

        // Jeśli B jest następnikiem A, to kopiujemy dane
        if (B != A) A->key = B->key;

        delete B;

    }
}