// derevo.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"  
#include <iostream>  
#include<time.h>  
#include<windows.h>  

using namespace std;

struct Node{
    int x;
    Node* left;
    Node * right;
};

struct Tree{
    Node * root;
} Root;

Node* init(int a){
    Node*newNode = new Node;
    newNode->x = a;
    newNode->left = newNode->right = NULL;
    return newNode;
}

void generete(int a){
    Node* current = new Node;
    current = Root.root;
    Node*newNode = new Node;
    newNode = init(a);
    while (true)
    {
       if (current->x > newNode->x){
          if (current->left == NULL){
             current->left = newNode;
             break;
          }
          else{
             current = current->left;
          }
       }
       else if (current->x <= newNode->x){
          if (current->right == NULL){
             current->right = newNode;
             break;
          }
          else{
             current = current->right;
          }
       }
       ///*else  
       //   newNode = init();*/  
    }
}

void prinT(Node* current){
    if (current != NULL){
       cout << "value =" << current->x << endl;
       prinT(current->left);
       prinT(current->right);
    }
}
void bal(int n, int n1, int *mass, Node* current){
    int s = n - n / 2;
     
    if (current == 0){
       current = init(mass[s]);
    }
    else{
       current->x = mass[s];
       current->left = current->right = 0;
    }
    if (n1 / 2 >= 1){
       bal(n1 / 2, n1 / 2, mass, current->left);
       bal(n1, n1 / 2, mass, current->right);
    }
}
/*Node*bal(int n, int n1, int *mass, Node* current){
    int s = n - n / 2;
     
    if (current == 0){
       current = init(mass[s-1]);
    }
    else{
       current->x = mass[s-1];
       current->left = current->right = 0;
    }
    if (n1 / 2 >= 1){
       current->left=bal(n1 / 2, n1 / 2, mass, current->left);
       current->right=bal(n1, n1 / 2, mass, current->right);
    }
    return current;
}*/
int*puzirkovaya(int *arr1,int N){
     
    int g = 0;
    for (int i = 0; i < N-1; i++){
       for (int j = 0; j< (N-1) - i; j++){
          if (arr1[j]>arr1[j + 1]){
             g = arr1[j];
             arr1 [j]= arr1[j + 1];
             arr1[j + 1] = g;

          }
       }
    }
    return arr1;
}

int main()
{
    srand(time(NULL));
     
     
    int n = 0;
    cin >> n;
    int *mass = new int[n];
    int *mass2 = new int[n];
    int randZnach = n * 2;
    for (int i = 0; i < n; i++){
       mass [i]= rand() % randZnach + 1;
       for (int j = 0; j < i; j++){
          if (mass [i]== mass[j]){
             i--;
             break;
          }
           
       }
    }
    for (int i = 0; i < n; i++){
       mass2 [i]= mass[i];
    }
     
    for (int i = 0; i < n; i++){
       if (i == 0){
          Root.root = init(mass[i]);
          continue;
       }
       generete(mass[i]);
    }

     
    //Node* current = new Node;  
    //current = Root.root;  
    prinT(Root.root);
    mass2 = puzirkovaya(mass2, n);
    cout << "----------------------------------" << endl;
    for (int i = 0; i < n; i++){
       cout << mass2 [i]<< " ";
    }
    cout << "----------------------------------" << endl;
    //Root.root->left = Root.root->right = NULL;
    bal(n, n, mass2, Root.root);
    prinT(Root.root);
    system("pause");
    return 0;
}

/*подумати як зробити перебалансіровку дерева

*/