daily pastebin goal
7%
SHARE
TWEET

balance_tree.cpp

a guest Mar 19th, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "bintree.h"
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <list>
  5. #include <cassert>
  6.  
  7. using namespace std;
  8. using namespace main_savitch_10;
  9.  
  10. binary_tree_node<int>* create_tree ();
  11. // return: pointer root of binary search tree of integers
  12.  
  13. template <typename T>
  14. list<T>* flatten (const binary_tree_node<T>* t);
  15. // precondition: t is a pointer root of binary search tree
  16. // return: non-null pointer to a sorted list containing the elements of t
  17.  
  18. template <typename T>
  19. binary_tree_node<T>* rebuild_tree (const list<T>& l);
  20. // precondition: l is a sorted list
  21. // returns balanced binary search tree containing the elements of l
  22.  
  23. template <typename T>
  24. void print_list (const list<T>& l);
  25. // postcondition: l has been displayed on standard output
  26.  
  27. template <typename T>
  28. bool is_sorted (const list<T>& l);
  29. // return whether l is sorted in non-decreasing order
  30.  
  31. int main ()
  32. {
  33.   binary_tree_node<int>* t = create_tree ();
  34.   print (t, 2);
  35.   cout << endl;
  36.   list<int>* flat_t = flatten (t);
  37.   print_list (*flat_t);
  38.   cout << endl;
  39.   binary_tree_node<int>* bal_t = rebuild_tree (*flat_t);
  40.   print (bal_t, 2);
  41.   delete t;
  42.   delete bal_t;
  43.   delete flat_t;
  44.   return EXIT_SUCCESS;
  45. }
  46.  
  47. binary_tree_node<int>* create_tree()
  48. {
  49.   binary_tree_node<int>* t1 = new binary_tree_node<int>(20);
  50.   binary_tree_node<int>* t2 = new binary_tree_node<int>(99);
  51.   binary_tree_node<int>* t3 = new binary_tree_node<int>(16, NULL, t1);
  52.   binary_tree_node<int>* t4 = new binary_tree_node<int>(72, NULL, t2);
  53.   binary_tree_node<int>* t5 = new binary_tree_node<int>(56, NULL, t4);
  54.   binary_tree_node<int>* t6 = new binary_tree_node<int>(48, NULL, t5);
  55.   binary_tree_node<int>* t7 = new binary_tree_node<int>(27, t3, t6);
  56.   return t7;
  57. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top