% Binary Trees and Sorting algorithms

Binary Trees

1. Rewrite Program P5.2 with the following changes (use wordFreq.in):

   • the function findOrInsert shall handle properly the case of an empty binary tree
   • the while loop shall not have a conditionnal

2. Rewrite Program P5.3 with the same changes (use passage.in).

3. Rewrite Program P5.7 so as to make it work in PythonTutor:

   • Replace input file by built-in array: 10 15 23 32 41 46 52 59 63 71 84
   • Remove printing functions.
   • Add functions numNodes, height and numLeaves, apply them on the created tree and show their output on the standard output of the program

Sorting

Start from the program at https://goo.gl/LLFVpC.

1. Implement and use the functions selecction_sort and gnome_sort inside of PythonTutor.

2. Modify this program so that, when run on your computer, it generates a PGM file that represent the state of the array after each swapping step, in both sorting functions.

   The Netpbm format is a family of simple image formats. If we use the format PGM (Portable GrayMap), we can visualize arrays as lines of grey pixels.

   Here goes an example of .pgm file:

   P2
   24 7
   15
   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   0  3  3  3  3  0  0  7  7  7  7  0  0 11 11 11 11  0  0 15 15 15 15  0
   0  3  0  0  0  0  0  7  0  0  0  0  0 11  0  0  0  0  0 15  0  0 15  0
   0  3  3  3  0  0  0  7  7  7  0  0  0 11 11 11  0  0  0 15 15 15 15  0
   0  3  0  0  0  0  0  7  0  0  0  0  0 11  0  0  0  0  0 15  0  0  0  0
   0  3  0  0  0  0  0  7  7  7  7  0  0 11 11 11 11  0  0 15  0  0  0  0
   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   

   If we open it with some image viewer and zoom in:

   \

   Let us go through this file’s format:

   • first line “P2” is obligatory and indicates the file type
   • second line indicates the number of columns and lines
   • third line indicates the maximum value that is going to be used
   • then comes the very picture, pixel by pixel

   Each pixel is specified by a value between 0 and the maximum value indicated at line 3. Intermediate values correspond to different shades of grey, from the darkest to the lightest one.

   If $n$ is the size of the arrays we are sorting, how many lines is going to have the image generated by our program? In which case (selection or gnome sort) do we know that quantity beforehand?

   a. Implement a the generation of images PGM inside of the previous program to visualize selection sort.

   To write one line to the PGM file, you can use the function:

   void print_line_pgm(const int a[], const int size, FILE * f ){
       int k;
       for(k=0; k<size; k++){   
          fprintf(f,"%2d ", a[k]);
          if (k<size-1) fprintf(f," ",a[k]);
       }
       fprintf(f,"\n");
   }
   

   Try by raising the value of SIZE to 30, 50, etc.

   \

   b. Add the required code also visualize the execution of gnome_sort.