Tree exercise

trees.cc

/*
 * =====================================================================
 *
 *       Filename:  trees.cc
 *
 *        Version:  1.0
 *        Created:  04/14/2013 11:20:59
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Enrico Franchi (ef), [email protected]
 *         Modified by: <INSERT YOUR NAME HERE>
 *
 * =====================================================================
 */
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <iostream>
#include <deque>
#include <iomanip>
#include <sstream>
#include <string>


typedef int T;

struct tree_node;
typedef tree_node* tree;

struct tree_node {
    T value;
    tree left;
    tree right;
};

tree tree_empty() {
    return NULL;
}

bool tree_is_empty(tree t) {
    return t == NULL;
}

bool tree_is_leaf ( tree t ) {
    return !tree_is_empty(t) &&
        tree_is_empty(t->left) &&
        tree_is_empty(t->right);
}

tree tree_make(tree left, T value, tree right) {
    tree t = new tree_node;
    t->left = left;
    t->right = right;
    t->value = value;
    return t;
}

tree leaf(T value) {
    return tree_make(NULL, value, NULL);
}

void tree_free(tree& t) {
    if(!tree_is_empty(t)) {
        tree_free(t->left);
        tree_free(t->right);
        delete t;
        t = 0;
    }
}

tree tree_copy( tree t ) {
    if (tree_is_empty(t)) {
        return tree_empty();
    } else {
        return tree_make(
               tree_copy(t->left),
               t->value,
               tree_copy(t->right));
    }
}

bool tree_init(tree& t, T value) {
    if (!tree_is_empty(t)) {
        return false;
    } else {
        t = tree_make(NULL, value, NULL);
        return true;
    }
}

bool tree_add_left(tree& t, T value) {
    if(tree_is_empty(t)) {
        return tree_init(t, value);
    } else {
        return tree_init(t->left, value);
    }
}


bool tree_add_right(tree& t, T value) {
    if(tree_is_empty(t)) {
        return tree_init(t, value);
    } else {
        return tree_init(t->right, value);
    }
}

int tree_max_height(tree t) {
    if (tree_is_empty(t)) return 0;
    int lh = tree_max_height(t->left);
    int rh = tree_max_height(t->right);
    return (lh > rh) ? lh + 1: rh + 1;
}

std::string to_s(T val) {
    std::ostringstream ss;
    ss << val;
    return ss.str();
}


/*----------------------------------------------------------------------
 *  tree_print: Use this to print a formatted tree.
 *
 *  Code adapted from:
 *  http://leetcode.com/2010/09/how-to-pretty-print-binary-tree.html
 *--------------------------------------------------------------------*/
void tree_print(tree root, int level, int indent_space, std::ostream& out);

// ignore this. it is hard.
void print_branches(int branch_len, int node_space_len,
        int start_len, int nodes_in_this_level,
        const std::deque<tree>& nodes_queue,
        std::ostream& out) {
    std::deque<tree>::const_iterator iter = nodes_queue.begin();
    for (int i = 0; i < nodes_in_this_level / 2; i++) {
        out << ((i == 0) ? std::setw(start_len-1) : std::setw(node_space_len-2))
            << "" << ((*iter++) ? "/" : " ");
        out << std::setw(2*branch_len+2) << "" << ((*iter++) ? "\\" : " ");
    }
    out << std::endl;
}

// ignore this. it is hard.
void print_nodes(int branch_len, int node_space_len,
        int start_len, int nodes_in_this_level,
        const std::deque<tree>& nodes_queue, std::ostream& out) {
    std::deque<tree>::const_iterator iter = nodes_queue.begin();
    for (int i = 0; i < nodes_in_this_level; i++, iter++) {
        out << ((i == 0) ? std::setw(start_len) : std::setw(node_space_len))
            << "" << ((*iter && (*iter)->left) ? std::setfill('_') : std::setfill(' '));
        out << std::setw(branch_len+2)
            << ((*iter) ? to_s((*iter)->value) : "");
        out << ((*iter && (*iter)->right) ? std::setfill('_') : std::setfill(' '))
            << std::setw(branch_len) << "" << std::setfill(' ');
    }
    out << std::endl;
}

// ignore this. it is hard.
void print_leaves(int indent_space, int level,
        int nodes_in_this_level,
        const std::deque<tree>& nodes_queue, std::ostream& out) {
    std::deque<tree>::const_iterator iter = nodes_queue.begin();
    for (int i = 0; i < nodes_in_this_level; i++, iter++) {
        out << ((i == 0) ? std::setw(indent_space+2) : std::setw(2*level+2))
            << ((*iter) ? to_s((*iter)->value) : "");
    }
    out << std::endl;
}

// ignore this. it is hard. Just use the function
void tree_print(tree root, int level, int indent_space, std::ostream& out) {
    int h = tree_max_height(root);
    int nodes_in_this_level = 1;

    int branch_len = 2*((int)std::pow(2.0,h)-1) - (3-level)*(int)std::pow(2.0,h-1);
    int node_space_len = 2 + (level+1)*(int)pow(2.0,h);
    int start_len = branch_len + (3-level) + indent_space;

    std::deque<tree> nodes_queue;
    nodes_queue.push_back(root);
    for (int r = 1; r < h; r++) {
        print_branches(branch_len, node_space_len,
                       start_len, nodes_in_this_level,
                       nodes_queue, out);
        branch_len = branch_len/2 - 1;
        node_space_len = node_space_len/2 + 1;
        start_len = branch_len + (3-level) + indent_space;
        print_nodes(branch_len, node_space_len,
                    start_len, nodes_in_this_level,
                    nodes_queue, out);

        for (int i = 0; i < nodes_in_this_level; i++) {
            tree curr_node = nodes_queue.front();
            nodes_queue.pop_front();
            if (curr_node) {
                nodes_queue.push_back(curr_node->left);
                nodes_queue.push_back(curr_node->right);
            } else {
                nodes_queue.push_back(NULL);
                nodes_queue.push_back(NULL);
            }
        }
        nodes_in_this_level *= 2;
    }
    print_branches(branch_len, node_space_len,
                   start_len, nodes_in_this_level,
                   nodes_queue, out);
    print_leaves(indent_space, level,
                 nodes_in_this_level, nodes_queue,
                 out);
}



/*
 * ===  FUNCTION  ======================================================
 *         Name:  array_to_tree
 *
 *  Description:
 *
 *  Si vuole costruire un albero binario di N nodi,
 *  realizzato con puntatori ai figli, a partire dal vettore dei padri,
 *  con la convenzione che il primo nodo nel vettore dei padri avente
 *  padre p, `e il figlio sinistro di p.
 * =====================================================================
 */
tree array_to_tree (int ancestor_vector[], size_t ancestor_vector_size)
{
    return 0;
}


/*
 * ===  FUNCTION  ======================================================
 *         Name:  sum_distances
 *  Description:
 *  Progettare un algoritmo ricorsivo che, dato un un albero binario
 *  rappre- sentato con puntatori ai figli, calcoli la somma delle
 *  distanze dei suoi nodi dalla radice. Valutare la complessit`a in
 *  tempo e in spazio dell’algoritmo proposto.
 * =====================================================================
 */
unsigned int
sum_distances ( tree t, unsigned int level )
{
    return 0;
}


/*
 * ===  FUNCTION  =====================================================
 *         Name:  verify_max_heap
 *  Description:
 *
 *  Progettare un algoritmo che, preso in ingresso un albero binario T ,
 *  realiz- zato con puntatori ai figli e i cui nodi contengono chiavi
 *  intere, verifichi che le chiavi nei nodi soddisfano la propriet`a
 *  (di valore) di heap di massimo.
 * =====================================================================
 */
bool
verify_max_heap ( tree t )
{
    return false;
}


/*
 * ===  FUNCTION  ======================================================
 *         Name:  dedup
 *  Description:
 *
 *  Si progetti un algoritmo che, dato un albero binario T , realizzato
 *  con puntatori ai figli e i cui nodi contengono interi, cancella
 *  ogni foglia contenente un elemento uguale a quello del padre.
 * =====================================================================
 */
void
dedup ( tree t )
{
    return;
}

/* 1. Implementare array_to_tree
 * 2. Provarla accuratamente
 * 3. Usarla per costruire facilmente alberi
 * 4. Implementare sum_distances e provarla accuratamente
 * 5. Implementare verify_max_heap e provarla accuratamente
 * 6. Implementare dedup e provarla accuratamente
 */
int main() {
    tree root = tree_make(
            tree_make(tree_make(leaf(5), 10, leaf(15)),
                      20,
                      tree_make(NULL, 25, leaf(28))),
            30,
            tree_make(leaf(35),
                      40,
                      tree_make(leaf(41), 50, NULL)));

    std::cout << "Tree pretty print with level=1 and indent_space=0\n\n";
    // Output to console
    tree_print(root, 1, 0, std::cout);

    tree t2 = tree_copy(root);
    tree_print(t2, 1, 0, std::cout);

    tree_free(root);
    tree_free(t2);
    /* std::cout << root << std::endl; */

    return 0;
}