gentree.h

Go to the documentation of this file.

#ifndef GENTREE_H
#define GENTREE_H

//#include <iostream>
//#include <fstream>
//#include <string>
#include <queue>

using namespace std;

// count the leading space
// int leadingspace(const string &s);
template<class T> struct node {
        // create self as parent as default
        node() : data(), child(0), sibling(0), parent(this) {}

        node(const T& val) : child(0), sibling(0), parent(this) { data=val; }
        // give the name and parent
        node(const T& val, node<T> *p) : child(0), sibling(0) { data=val; parent=p; }

        // copy constructor does not make sense for tree
        //node(const node<T>& n) { data=n.data; child=n.child; sibling=n.sibling; parent=n.parent; } 

        // only the value of the node is needed
        void add_child(const T& chi) { child = new node<T>(chi, this); }
        void add_sibling(const T& sib) { sibling = new node<T>(sib, this->parent); }
        void setData(const T& d) { data = d; }
        node<T>* right() { return sibling; }
        node<T>* down() { return child; }
        vector<T> row(); 
        vector<T> col();

        T data;   // data stored in this node
        node<T> *child;   // left or down (in ACE) child
        node<T> *sibling; // righ sibling
        node<T> *parent;
};
//typedef template<class T> void (*visitFunc)(node<T> *n);

template<class T> vector<T> node<T>::row() { 
        node<T>* ptr = sibling;
        vector<T> tmp;
        while (ptr) { 
                tmp.push_back(ptr->data);
                ptr = ptr->sibling;
        }
        return tmp;
}

template <class T> vector<T> node<T>::col() {
        node<T>* ptr = sibling;
        vector<T> tmp;
        while (ptr) {
                tmp.push_back(ptr->data);
                ptr = ptr->child;
        }
        return tmp;
}

//template<class T> void preorder(node<T> *n, visitFunc vis) {
template<class T> void preorder(node<T> *n, void (*vis)(node<T>*)) {
        if (n) {
                vis(n);
                //cout << n->data << " || ";
                preorder(n->child, vis);
                preorder(n->sibling, vis);
        }
        else {
                vis(0); //cout << endl;
        }
}

//template<class T> void levelorder(node<T> *n, visitFunc vis) {
/* visit the horizontal siblings first
 */
template<class T> void levelorder(node<T> *n, void (*vis)(node<T>*)) {
        queue<node<T>* > nodes_left;
        nodes_left.push(n);
        node<T>* p;

        while (!nodes_left.empty()) {
                p = nodes_left.front();
                //vis(p->parent);   //cout << "parent:" << p->parent->data << endl;
                while (p) {
                        vis(p);  //cout << p->data << " || ";
                        if (p->child) nodes_left.push(p->child);
                        p = p->sibling;
                }
                vis(0);  //cout << endl << endl;
                nodes_left.pop();
        }
}

//template<class T> void postorder(node<T> *n, visitFunc vis) {
template<class T> void postorder(node<T> *n, void (*vis)(node<T>*)) {
        if (n) {
                postorder(n->child, vis);
                postorder(n->sibling, vis);
                vis(n);  //cout << n->data << " || ";
        }
        else {
                vis(0);  //cout << endl;
        }
}

// postorder traversal to delete, the only way of 
// deleting all nodes
template<class T> void deltree(node<T> *n) { 
   if (n) {
       deltree(n->child);
       deltree(n->sibling);
       //cout << "deleting " << n->data << endl;  //debug
       delete n;
   }
}

#endif