balance_tree.cpp

#include "bintree.h"
#include <cstdlib>
#include <iostream>
#include <list>
#include <cassert>

using namespace std;
using namespace main_savitch_10;

binary_tree_node<int>* create_tree ();
// return: pointer root of binary search tree of integers

template <typename T>
list<T>* flatten (const binary_tree_node<T>* t);
// precondition: t is a pointer root of binary search tree
// return: non-null pointer to a sorted list containing the elements of t

template <typename T>
binary_tree_node<T>* rebuild_tree (const list<T>& l);
// precondition: l is a sorted list
// returns balanced binary search tree containing the elements of l

template <typename T>
void print_list (const list<T>& l);
// postcondition: l has been displayed on standard output

template <typename T>
bool is_sorted (const list<T>& l);
// return whether l is sorted in non-decreasing order



int main ()
{
  binary_tree_node<int>* t = create_tree ();
  print (t, 0);
  cout << endl;
  list<int> l( 4, 5);
  //list<int>* flat_t = flatten (t);
  print_list (l);
  /*cout << endl;
  binary_tree_node<int>* bal_t = rebuild_tree (*flat_t);
  print (bal_t, 2);
  delete t;
  delete bal_t;
  delete flat_t;*/
  return EXIT_SUCCESS;
}

binary_tree_node<int>* create_tree()
{
  binary_tree_node<int>* t1 = new binary_tree_node<int>(20);
  binary_tree_node<int>* t2 = new binary_tree_node<int>(99);
  binary_tree_node<int>* t3 = new binary_tree_node<int>(16, NULL, t1);
  binary_tree_node<int>* t4 = new binary_tree_node<int>(72, NULL, t2);
  binary_tree_node<int>* t5 = new binary_tree_node<int>(56, NULL, t4);
  binary_tree_node<int>* t6 = new binary_tree_node<int>(48, NULL, t5);
  binary_tree_node<int>* t7 = new binary_tree_node<int>(27, t3, t6);
  return t7;
}




template <typename T>
list<T>* flatten (const binary_tree_node<T>* t){

}

template <typename T>
binary_tree_node<T>* rebuild_tree (const list<T>& l){

}

template <typename T>
void print_list (const list<T>& l){
    cout<< l <<endl;
}

template<typename T>
std::ostream& operator<<(std::ostream& s, const std::list<T>& v) {
    s.put('[');
    char comma[3] = {'\0', ' ', '\0'};
    for (const auto& e : v) {
        s << comma << e;
        comma[0] = ',';
    }
    return s << ']';
}

template <typename T>
bool is_sorted (const list<T>& l){

}