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, 2);
  cout << endl;
  list<int>* flat_t = flatten (t);
  print_list (*flat_t);
  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;
}