/*
Даны две последовательности вещественых чисел, содеpжащие М и К
 элементов (в каждой последовательности могут быть повтоpяющиеся элементы).
 Для этих последовательностей постpоить деpевья поиска и pаспечатать
 полученные  деpевья.
   Напечатать элементы последовательностей в поpядке возpастания, если
 максимальный уpовень деpева пеpвой последовательности больше максимального
 уpовня деpева втоpой последовательности или в поpядке невозpастания в 
 пpотивном случае. 
   Значения М и К указываются пpи выполнении пpогpаммы.
   Пpимеp:
           М=9   5  1  6  3 -1 8  7 10  8        К=6   7  4  2  3  0 -2
           деpево1:                              деpево2:
                        -1                                      -2
                    1                                       0
                        3       уpовень=3               2         уpовень=4
                5                                           3
                    6                               4
                            7                   7
                        8
                            10
           pезультиpующая последовательность:
                   10  8  8  7  7  6  5  4  3  3  2  1  0  -1  -2
*/
/*
 Программа берёт два дерева из фалов tree_1.txt, tree_2.txt
 никакое количество элементов перед самим дерево указывать не надо
*/
#include <iostream>
#include <fstream>
#include <list>

#define DEBUG
#ifdef DEBUG
 #define PAUSE system &#40; "pause" &#41;
 #define PRINT(X) cout << #X"= " << (X) << endl
#elif
 #define PAUSE
 #define PRINT(X)
#endif
using namespace std ;

class Tree {
 struct Node {
  int data ;
  Node* L ;
  Node* R ;
  Node(const int& d):L(0), R(0), data(d) {}
  Node():L(0), R(0), data(-99999) {}
  ~Node() {
   if( L )
    delete L ;
   if( R )
    delete R ;
  }
  void print(ostream& out, int deep=0) {
   if( R )
    R->print(out, deep+1) ;
   for( int i=0 ; i<deep ; i++ )
    out << "   " ;
   out << data << endl ;
   if( L )
    L->print(out, deep+1) ;
  }
 }*root, *target ;
protected:
 static void getList(Node* root, list<int>& l, bool type) {
  if( !type ) {
   if( root->L )
    getList( root->L, l, type ) ;
   l.push_back(root->data) ;
   if( root->R )
    getList( root->R, l, type ) ;
  }
  else {   
   if( root->R )
    getList( root->R, l, type ) ;
   l.push_back(root->data) ;
   if( root->L )
    getList( root->L, l, type ) ;   
  }
 }
public:
 Tree():root(0) {}
 ~Tree() {
  delete root ;
 }
 void add(const int& d) {
  if( !root ) {
   root = new Node(d) ;
   return ;
  }
  Node* ptr(root) ;
  while (1) {
   if( d == ptr->data )
    return ;
   if( d > ptr->data ) {
    if( ptr->L ) {
     ptr = ptr->L ;
     continue ;
    }
    ptr->L = new Node(d) ;
    return ;
   }
   else {
    if( ptr->R ) {
     ptr = ptr->R ;
     continue ;
    }
    ptr->R = new Node(d) ;
    return ;
   }
  }
 }
 friend ostream& operator<<(ostream& out, Tree& tree) {
  tree.root->print(out) ;
  out << endl ;
  return out ;
 }
 void dyPrint( const Tree& tree ) {
  //для начала определим тип вывода
  bool type(false) ; //тип вывода
  Node* ptr(root) ;
  while( ptr->L )
   ptr = ptr->L ;
  Node* ptr1(tree.root) ;
  while( ptr1->L )
   ptr1 = ptr1->L ;
  type = ( ptr->data > ptr1->data ) ? true : false ;
  //если тру, в порядке возрастания, иначе в порядке убывания
  list<int> list1, list2 ;
  getList( root, list1, type ) ;
  getList( tree.root, list2, type ) ;
  if( !type ) {
   for( list<int>::iterator i1=list1.begin(), i2=list2.begin() ; i1!=list1.end() || i2!=list2.end() ; ) {
    if(  i1!=list1.end() && i2!=list2.end() ) {
     if( *i1 > *i2 ) {
      cout << *i1 << ' ' ;
      i1++ ;
     }
     else {
      cout << *i2 << ' ' ;
      i2++ ;
     }
     continue ;
    }
    if( i1!=list1.end() ) {
     cout << *i1 << ' ' ;
     i1++ ;
     continue ;
    }
    if( i2!=list2.end() ) {
     cout << *i2 << ' ' ;
     i2++ ;
     continue ;
    }    
   }
  }
  else {
   for( list<int>::iterator i1=list1.begin(), i2=list2.begin() ; i1!=list1.end() || i2!=list2.end() ; ) {
    if( i1!=list1.end() && i2!=list2.end() ) {
     if( *i1 < *i2 ) {
      cout << *i1 << ' ' ;
      i1++ ;
     }
     else {
      cout << *i2 << ' ' ;
      i2++ ;
     }
     continue ;
    }
    if( i1!=list1.end() ) {
     cout << *i1 << ' ' ;
     i1++ ;
     continue ;
    }
    if( i2!=list2.end() ) {
     cout << *i2 << ' ' ;
     i2++ ;
     continue ;
    }    
   }
  }
 }
 
};

int main ( int argc, char* argv[] ) {
 setlocale ( LC_ALL, "RUSSIAN" ) ;
 
 ifstream in1("tree_1.txt"), in2("tree_2.txt") ;
 if( !in1 && !in2 ) {
  cout << "Не удалось открыть один из входных файлов!" << endl ;
  system&#40;"Pause"&#41; ;
  return 1 ;
 }
 Tree t1, t2 ;
 while( !in1.eof() ) {
  cout << "!in1.eof()" << endl ;
  int x ;
  in1 >> x ;
  t1.add(x) ;
 }
 while( !in2.eof() ) {
  int x ;  
  in2 >> x ;
  t2.add(x) ;
 }
 PRINT(t1) ;
 PRINT(t2) ;
 t1.dyPrint(t2) ;
 cout << endl ;

 system&#40;"Pause"&#41; ;
 return 0 ;
}